Chap07. 큐, 배열 기반의 원형 큐

큐의 ADT

큐도 스택과 마찬가지로 ADT가 거의 정형화되어 있다. 할 수 있는 일이 거의 비슷하기 때문.

 

void QueueInit(Queue *pq);

- 큐의 초기화

- 큐 생성 후 제일 먼저 호출되어야함 

 

int QIsEmpty(Queue *pq);

- 큐가 빈 경우 TRUE, 그렇지 않은 경우 FALSE 반환

 

void Enqueue(Queue *pq Data data);

- 큐에 매개변수 data로 전달된 데이터 저장. 

 

Data Dequeue(Queue *pq);

- 저장순서가 가장 앞선 데이터 삭제 

- 삭제된 데이터는 반환 

- 이 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야함 

 

Data QPeek(Queue *pq);

- 저장순서가 가장 앞선 데이터 반환하되 삭제 하지 않음.

- 이 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야함 

 

 

---

큐의 배열 기반 구현 : 원형 큐 

큐의 머리를 가르키는 포인터 F (Front), 큐의 꼬리를 가르키는 포인터 R (Rear)이 있다고 생각해보자.

큐는 선입선출, 뒤로 넣고 앞으로 빼는 자료구조이기 때문에 큐에 데이터를 넣는 Enqueue 연산 시에는 큐의 뒤에 데이터를 넣고 R을 오른쪽으로 한칸 이동하면 될것이다.

그런데 Dequeue 연산 시, 큐의 머리에서 데이터를 빼낸 후에 반환할 데이터 즉 큐의 가장 top에 있는 데이터를 배열의 첫부분에 위치 시키는 방식으로 구현한다고 하면, Dequeue 연산을 할때마다 큐에 존재하는 모든 데이터를 한칸씩 왼쪽으로 땡겨야한다. (Dequeue의 시간복잡도가 O(N)이 된다). 

 

따라서 이런 방법을 취하지 않고 Dequeue를 할때 머리를 가르키는 F를 오른쪽으로 1칸씩 이동하는 방식을 취하게 되는데, 이럴 경우 R이 큐의 끝을 가르키고 있는 상황이 오면 Enqueue 시에 데이터를 더이상 저장할 공간이 없다 (R을 오른쪽으로 이동시킬수 없다.)

 

이 문제의 해결방법이 바로 원형 큐 이다. 

R이 큐의 꼬리를 가르킬때 데이터가 더 Enqueue 되게 되면, R을 배열의 첫부분을 가르키도록 하는 것이다. F도 마찬가지다. 

 

이런 원형 큐에도 문제가 남아있는데 바로 F와 R의 위치만으로는 큐의 상태를 알수가 없다는 것이다.

F와 R이 원형으로 계속 돌기때문에 큐가 꽉찬 상태에서도 큐가 비어있는 상태에서도 F가 R보다 한 칸 앞 선 위치를 가르킨다.

이에 대한 해결책은 배열에 데이터를 꽉 채우지 않고 한칸을 남기는 것이다.

그러면 큐가 empty인 상황에서는 F,R이 동일한 위치를 가르키고, 큐가 full인 상황에서는 F가 R보다 한 칸 앞선 위치를 가르키게 된다. 

 

---

원형 큐 구현 

 

CircularQueue.h

/*
 * 배열 기반 원형 큐 구현
 */
#ifndef CHAP07_CIRCULARQUEUE_H
#define CHAP07_CIRCULARQUEUE_H

#define TRUE 1
#define FALSE 0

#define QUE_LEN 100
typedef int Data;

typedef struct _cQueue
{
    int front;
    int rear;
    Data queArr[QUE_LEN];
} CQueue; // Circular Queue
typedef CQueue Queue;

void QueueInit(Queue *pq);
int QIsEmpty(Queue *pq);

void Enqueue(Queue *pq, Data data);
Data Dequeue(Queue *pq);
Data QPeek(Queue *pq);

#endif //CHAP07_CIRCULARQUEUE_H

CircularQueue.c

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

// 최초에 큐 텅빈 경우 front와 rear는 동일한 위치 가르킴
void QueueInit(Queue *pq)
{
    pq->front = 0;
    pq->rear = 0;
}

int QIsEmpty(Queue *pq)
{
    // front, rear 동일한 위치 가르킨다면 큐가 비어있음
    if(pq->front == pq->rear) return TRUE;
    else return FALSE;
}

int NextPosIdx(int pos)
{
    // 원형으로 돌기위함
    if(pos == QUE_LEN-1) return 0;
    else return pos+1;
}

void Enqueue(Queue *pq, Data data)
{
    // 큐의 꼬리가 큐의 머리에 한 칸 앞서있다 = 큐가 꽉찼다
    if(NextPosIdx(pq->rear) == pq->front)
    {
        printf("Queue is full");
        exit(-1);
    }

    pq->rear = NextPosIdx(pq->rear);
    pq->queArr[pq->rear] = data;
}

Data Dequeue(Queue *pq)
{
    if(QIsEmpty(pq))
    {
        printf("Queue is full");
        exit(-1);
    }

    pq->front = NextPosIdx(pq->front);
    return pq->queArr[pq->front];
}

Data QPeek(Queue *pq)
{
    if(QIsEmpty(pq))
    {
        printf("Queue is full");
        exit(-1);
    }

    // F는 항상 빈 공간 가르키고 있다. peek을 위해서는 다음칸의 데이터를 리턴해줘야함
    return pq->queArr[NextPosIdx(pq->front)];
}

CircularQueueMain.c

#include <stdio.h>
#include "CircularQueue.h"

int main()
{
    Queue q;
    QueueInit(&q);

    // data enqueue
    Enqueue(&q, 1);
    Enqueue(&q, 2);
    Enqueue(&q, 3);
    Enqueue(&q, 4);
    Enqueue(&q, 5);

    // data dequeue
    while(!QIsEmpty(&q))
    {
        printf("%d ", Dequeue(&q));
    }
}