[6] 큐 (Queue)

큐(Queue)는 스택(Stack)과 다르게 FIFO(First-In-First-Out) 리스트로,

먼저 들어온 원소가 먼저 나가는 자료구조이다.

 

가장 앞쪽(먼저 들어온)의 원소를 가리키는 부분을 front 라고 하고, 

가장 뒤쪽(나중에 들어온)의 원소를 가리키는 부분은 rear라고 한다.

원소를 넣을 땐 add, 뺄 때는 delete 라고 한다.

 

예시를 보면 더 쉽게 이해할 수 있다.

front는 f, rear는 r이라고 표현하였다.

 

큐에 A를 넣으면 다음과 같다.

큐에 B를 넣으면 

rear 는 B가 되고, front는 A가 된다.

 

큐에 C를 넣으면

다음과 같이 C는 rear가 되고, A는 front가 된다.

 

이번에는 delete를 하면

다음과 같이 A는 삭제되어 리턴되고,

B가 front, C는 그대로 rear가 된다.

 

따라서 삽입 하는 경우에는 front는 그대로, rear만 바뀌고,

삭제하는 경우에는 front는 바뀌고, rear는 그대로 유지된다.

 

C언어 코드

큐의 자료구조는 다음과 같이 선언한다.

#define MAX_QUEUE_SIZE 100
typedef struct {
    int key;
    // 다른 필드들
}element;
element queue[MAX_QUEUE_SIZE];
int front = -1;
int rear = -1;

 

큐에 원소를 삽입하는 add 함수

void add(element item) {
    if (rear == MAX_QUEUE_SIZE)
        queueFull();
    queue[++rear] = item;
}

 

큐에서 원소를 삭제하는 delete 함수

element delete() {
    if (front == rear)
        return queueEmpty();
    return queue[++front];
}

queueFull과 queueEmpty 함수는

각각 큐가 가득 차고 큐가 비어있을 때 에러를 출력하도록 하는 함수이다.