큐 개념

큐의 추상자료형

void QueueInit(Queue *pq)

• 큐의 초기화를 진행한다.
• 큐 생성후 제일 먼저 호출 되어야 하는 함수이다.

int QIsEmpty(Queue *pq)

• 큐가 빈 경우 1, 그렇지 않은 경우 0을 반환한다.

void Enqueue(Queue *pq, Data data)

• 큐에 데이터를 저장한다. 매개변수 data로 전달된 값을 저장한다.

Data Dequeue(Queue *pq)

• 저장순서가 가장 앞선 데이터를 삭제한다.
• 삭제된 데이터는 반환된다.
• 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

Data QPeek(Queue *pq)

• 저장순서가 가장 앞선 데이터를 반환하되 삭제하지 않는다.
• 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야한다.

큐는 선입선출, 먼저 넣은 자료가 먼저 나오는 형태의 자료구조이다. 예를 들어 맛집의 줄을 생각할 수 있다. 먼저 줄은 선 사람이 가장 먼저 음식을 먹을 수 있다. 큐중에서 원형큐는 배열을 사용 해서 구현 하였을 경우 사용을 생각해 볼 수 있다.

원형의 통에 data를 삽입하는 것이다. 이렇게 구성하는 이유는 배열을 사용하였을 때, 앞에서 넣고 뒤에서 빼기때문에 배열이 가득 차지 않아도 배열의 길이를 넘어서 데이터를 삽입 하지 못하는 경우를 해결하고자 이런식으로 구성한다.

typedef struct _cQueue
{
    int front;
    int rear;
    Data queArr[QUE_LEN];
} cQueue;

위에서 front와 rear는 변수 명에서 알수 있듯이 배열의 머리와 꼬리를 가르킨다. 큐의 경우 뒤에서 빼기 떄문에 rear변수를 통해서 삭제하고, 앞에서 부터 값을 넣기 떄문에 front를 사용해서 값을 삽입한다.

값이 꽉차면 rear + 1 = front가 된다. 만약 값을 전부 삭제해 비어있다면?.

rear + 1 = front가 된다.

이것을 해결하기 위한 방법중 하나는 배열중 하나를 비워 사용하지 않는 것이다.

비워져 있을 경우 rear == front, 가득 차있을 경우 rear + 1 = front가 된다. 이러한 개념을 바탕으로 원형큐를 구현한다.

void EnQueue(Queue *pq, Data data)
{
    if (NextPosIdx(pq->rear) == pq->front)
        exit(1);
    pq->rear = NextPosIdx(pq->rear);
    pq->queArr[pq->rear] = data;
}

Data DeQueue(Queue *pq)
{
    if (QIsEmpty(pq))
        exit(1);
    pq->front = NextPosIdx(pq->front);
    Data dData = pq->queArr[pq->front];

    return dData;
}

NextPosIdx()은 배열의 길이를 넘었을 경우 0을, 아니면 다음 위치를 반환한다.

 

원형 큐 코드: https://boiling-fowl-6d6.notion.site/CircularQueue-5e8b296f563e44088dd9d27376fadc87

노드 기반 큐 코드: https://boiling-fowl-6d6.notion.site/Queue-5c05c1cd15bf4815ae6de230640d3980