[자료구조] 큐(queue) 란? - 컴도리돌이

 

큐(queue)란?

큐(queue)는 스택과 다르게 먼저 들어온 데이터가 먼저 나가는 자료구조로 선입선출(FIFO : First-in First-out) 방식으로 삽입과 삭제는 FIFO 순서로 따릅니다~ 삽입은 큐(queue)의 후단에서, 삭제는 전단에서 이루어져요!

 

 

큐(queue)의 연산

큐(queue)의 연산

-init() : 큐를 초기화한다.

-enqueue(e) : 주어진 요소 e를 큐의 맨 뒤에 추가한다.

-dequeue() : 큐가 비어있지 않으면 맨 앞 요소를 삭제하고 반환한다.

-is_empty() : 큐가 비어있으면 true를 아니면 false를 반환한다.

-peek() : 큐가 비어있지 않으면 맨 앞 요소를 삭제하지 않고 반환한다.

-is_full() : 큐가 가득 차 있으면 true을 아니면 false을 반환한다.

-size() : 큐의 모든 요소들의 개수를 반환한다.

 

큐(queue)를 구현하는 방법

 

배열로 구현한 큐(queue) - 원형 큐(circle queue) 

원형큐의 삽입과 삭제 연산 예

원형 큐 공백상태, 포화 상태

 

원형 큐를 위한 데이터는 배열 data []와 front, rear를 전역 변수로 설정해야 해요, 배열로 표현하는 것은 거의 비효율적이어서 잘 쓰이지는 않지만, 간단하게 코딩할 수 있습니다~ 삽입과 삭제 연산에서 rear과 front를 전체 사이즈로 나눠줘야 하는데 그 이유는 선형 큐(queue)와 한 바퀴를 돌 경우 다시 인덱스가 0이 될 경우를 대비해서 항상 전체 사이즈로 나눠줘야 해요!

 

원형 큐의 단순한 연산들

배열로 구현한 원형 큐

 

연결리스트로 구현한 큐(queue)

연결리스트로 구현한 큐(queue) - 삽입(enqueue)

 

1. temp라는 새로 할당한 노드의 값 D를 넣어주고 링크를 NULL로 할당해준다.

2. front와 rear이 비어있을 경우 front와 rear를 p로 설정을 하고, 아닐 경우 rear인 C의 링크를 temp D에 연결시키고 rear를 temp 값을 넣어준다.

 

연결리스트로 구현한 큐(queue) - 삽입(enqueue)

 

연결리스트로 구현한 큐(queue) - 삭제(dequeue)

1. 새로운 temp 노드를 할당해준다.

2. temp를 front로 설정해준다.

3. front를 front의 링크로 설정해주면 A의 값이 사라지는데 이때 front가 NULL값이면 rear 값도 NULL로 설정해주고 새로운 정수 값 e를 temp 링크의 데이터를 넣어주고 temp를 free 시켜준다.

4. return 값을 e로 해준다.

 

연결리스트로 구현한 큐(queue) - 삭제(dequeue)

 

 

#include<stdio.h>
#include<stdlib.h>

typedef int Element;
typedef struct LinkedNode
{
    Element data;
    struct LinkedNode* link;
}Node;


Node* front = NULL;
Node* rear = NULL;

void error(char* str)
{
    fprintf(stderr,"%s\n",str);
    exit(1);
}

int is_empty(){ return front == NULL;}
void init_queue() { front = rear = NULL;}

int size()
{
    Node *p;
    int count = 0;
    for(p = front; p!= NULL; p=p->link) count++;
    return count;
}

void enqueue(Element e)
{
    Node* p = (Node*)malloc(sizeof(Node));
    p->data = e;
    p->link = NULL;

    if(is_empty()) front = rear = p;
    else
    {
        rear->link = p;
        rear = p;
    }
}

Element dequeue()
{
    Node* p;
    Element e;

    if(is_empty())
        error("큐 공백 에러");
    p = front;
    front = front->link;
    if(front == NULL) rear = NULL;
    e = p->data;
    free(p);
    return e;
}

Element peek()
{
    if(is_empty())
        error("스택 공백 에러");
    return front->data;
}

void destroy_dequeue()
{
    while(is_empty()==0)
        dequeue();
}

void print_queue(char* msg)
{
    Node *p;
    printf("%s[%d]= ",msg,size());
    for(p=front; p!= NULL; p = p->link)
        printf("%2d ",p->data);
    printf("\n");
}