[Data Structure] 큐(queue)

---

큐

 

 

큐는 선입선출(FIFO, first in first out) 방식으로 동작하는 자료구조이다. 즉 가장 먼저 삽입된 데이터가 가장 먼저 삭제된다는 뜻이다. 일상에서 흔히 볼 수 있는 줄 서기 상황이 이와 유사하다. 줄을 먼저 선 사람이 먼저 빠져나가는 방식에서 큐의 작동원리를 생각해 볼 수 있다.

즉 데이터 추가는 후열(rear)에서만 일어나고 데이터 삭제는 전열(front)에서만 일어난다. 데이터를 처리할 때 순서를 보장하는 성질이 있는 것이다. 때문에 공정하게 데이터를 처리하는 대기열, 프로세스 스케줄링 등에 사용된다.

 

---

ADT

 

객체 (Object)

• 0 개 이상의 요소들로 구성된 선형 리스트

연산 (Operation)

• create(size) ::= 최대 크기가 size 인 공백 큐를 생성한다.
• init() ::= 큐를 초기화한다.
• is_full() ::= 큐의 원소 개수가 size 와 같다면 true 를, 아니라면 false 를 반환한다.
• is_empty() ::= 큐의 원소 개수가 0 이라면 true 를, 아니라면 false 를 반환한다.
• enqueue(item) ::= 큐가 가득 차 있지 않다면 큐의 맨 뒤에 item 을 추가한다.
• dequeue() ::= 큐가 비어있지 않다면 큐의 가장 앞에 있는 원소를 제거해서 반환한다.
• front() 혹은 peek() ::= 큐가 비어있지 않다면 큐의 가장 앞에 있는 원소를 제거하지 않고 반환한다.
• size() ::= 큐의 원소 개수를 반환한다.

 

---

구현 | C

 

간단하게 C 를 통해 선형 큐를 구현하였다. 아래 코드는 main 함수를 제외한 큐 선언과 큐를 관리하는 코드이다. element 는 임의로 int 로 설정하였다. dequeue 나 front 에서 에러도 임의로 -1 을 반환하도록 하였다.

#include <stdio.h>
#define MAX_QUEUE_SIZE 10

typedef int element;
typedef struct {
    element data[MAX_QUEUE_SIZE];
    int front;
    int rear;
} Queue;

void init_queue(Queue* q) {
    q->front = q->rear = -1;
}

int is_empty(Queue* q) {
    return (q->front == q->rear);
}

int is_full(Queue* q) {
    return (q->rear == MAX_QUEUE_SIZE - 1);
}

void enqueue(Queue* q, element item) {
    if (is_full(q)) {
        printf("Queue is full\n");
        return;
    } else {
        q->data[++(q->rear)] = item;
    }
}

element dequeue(Queue* q) {
    if (is_empty(q)) {
        printf("Queue is empty\n");
        return -1;
    } else {
        return q->data[++(q->front)];
    }
}

element front(Queue* q) {
    if (is_empty(q)) {
        printf("Queue is empty\n");
        return -1;
    } else {
        return q->data[q->front];
    }
}

element rear(Queue* q) {
    if (is_empty(q)) {
        printf("Queue is empty\n");
        return -1;
    } else {
        return q->data[q->rear];
    }
}

int size(Queue* q) {
    return (q->rear - q->front);
}

void display(Queue* q) {
    for (int i = 0; i < MAX_QUEUE_SIZE; i++) {
        if (i > q->front && i <= q->rear) {
            printf("%d\t|", q->data[i]);
        } else {
            printf("\t|");
        }
    }
    printf("\n");
}

main 함수를 구현하고, 예시로 1, 2, 3, 4 를 enqueue 하면서 큐의 데이터를 확인하고, dequeue 로 해당 데이터를 꺼내고 큐의 데이터를 확인해보자. main 함수는 아래와 같다.

int main()
{
    Queue q;
    init_queue(&q);
    enqueue(&q, 1); display(&q);
    enqueue(&q, 2); display(&q);
    enqueue(&q, 3); display(&q);
    enqueue(&q, 4); display(&q);
    dequeue(&q); display(&q);
    dequeue(&q); display(&q);
    dequeue(&q); display(&q);
    dequeue(&q); display(&q);
    return 0;
}

결과는 아래와 같다.

1	|	|	|	|	|	|	|	|	|	|
1	|2	|	|	|	|	|	|	|	|	|
1	|2	|3	|	|	|	|	|	|	|	|
1	|2	|3	|4	|	|	|	|	|	|	|
	|2	|3	|4	|	|	|	|	|	|	|
	|	|3	|4	|	|	|	|	|	|	|
	|	|	|4	|	|	|	|	|	|	|
	|	|	|	|	|	|	|	|	|	|

enqueue 로 넣은 순서대로 데이터가 삭제되는 것을 확인할 수 있다.

 

C 에서는 따로 queue 라이브러리가 존재하지 않지만, C++, Java 등에서는 별도의 라이브러리가 존재하고, Python 에서는 list 가 대체 가능하며, 라이브러리를 활용할 수도 있다.

백준의 큐(링크)를 활용하여 큐를 구현하고 연습해볼 수 있다.