Data Structure 8 - Queue(1)

 앞서 살펴본 스택과 달리 큐는 들어온 순서대로 나간다. 즉, 먼저 들어온 것이 먼저 나가는 First in First Out(FIFO, 선입선출) 구조이다. 흔히 게임이 오픈할 때 발생하는 접속 대기열이나 대전 게임의 상대를 찾는 매칭 등이 큐의 예시이다.

큐는 가장 먼저 들어와 반환되는 데이터를 가리키는 front와 가장 최근에 들어온 데이터를 가리키는 rear 를 가진다. 데이터는 front에서 삭제되고, rear에서 삽입된다.

큐도 배열이나 연결리스트 등으로 구현이 가능하다. 아래는 배열로 구현한 큐 ADT이다.

#include<stdio.h>
#define MAX_SIZE 100
typedef int element;

typedef struct QueueType {
    int queue[MAX_SIZE];
    int front;
    int rear;
}QueueType;

int is_empty(QueueType* q) {
    return (q->front == q->rear); // 공백상태에서는 front와 rear가 같은 곳을 가리킴.
}

int is_full(QueueType* q) {
    return ((q->rear + 1) % MAX_SIZE == q->front);//rear가 front 보다 한칸 더 뒤에 있는지 확인. front가 옮겨지므로 나머지 연산 사용.
}

void enqueue(QueueType* q, element item) { // 삽입함수
    if (is_full(q)) error("큐가 포화상태입니다.");
    q->rear = (q->rear + 1) % MAX_SIZE;
    q->queue[q->rear] = item; // 삽입은 항상 맨 뒤에
}

void dequeue(QueueType* q) {
    if (is_empty(q)) error("큐가 공백 상태입니다.");
    q->front = (q->front + 1) % MAX_SIZE;
    return q->queue[q->front]; // 삭제는 항상 맨 앞에
}

큐의 배열 구현에서 특이한 점은, 일렬이 아니라 원형으로 생각한다는 점이다. 일반적인 배열은 메모리 공간이 정해져 있으므로 front와 rear를 반복적으로 움직이기 어렵다. 따라서 개념적으로 배열의 처음과 끝을 서로 이어붙여 원형 배열을 만들면 삽입/삭제 되는 데이터에 따라 front와 rear를 옮기기가 더 쉬워진다. 

단, 이 경우 큐의 공백 상태와 포화 상태를 구분할 수 없으므로 나머지 연산을 사용해 front가 rear보다 한칸 앞에 있으면 포화 상태로 구분한다. (공백 상태면 front와 rear가 가리키는 것이 동일) 따라서 원형 배열 큐에서는 항상 한 칸 이상이 비어 있다.