큐 (리스트를 이용한 구현)

지난 포스팅에서는 배열을 이용하여 큐를 구현해보았다. 이번 장에서는 리스트를 이용하여 큐를 구현해볼 예정인데 큐는 배열을 사용하였을 경우 front를 기반으로 한 칸씩 이동하며 데이터를 삭제하였다. 포인터를 이용할 경우에는 front가 비어있을 경우 큐가 비었다고 볼 수 있다. 아래의 그림은 최초의 큐 형태이다.

최초의 큐 형태

① 데이터 삽입을 보자. 첫 번째 노드가 추가가 될 경우 Front와 Rear는 첫 번째 노드를 가리키게 되며 두 번째 노드의 추가로부터는 Rear가 새로운 노드를 가리키게 추가함으로써 데이터 삽입이 완료가 된다.

Enqueue 연산을 통한 데이터의 삽입이다. 데이터가 추가가 될때마다 Rear는 가장 최근에 생성한 노드를 가리키게 됨 

② 데이터의 삭제를 보자. 삭제할 노드를 임시 변수에 저장해둔 후 Front를 다음 위치를 가리키게 해준다. 그 이후 임시 변수에 담아두었던 노드를 삭제한 후 데이터를 반환한다.

Dequeue 연산을 통한 데이터의 삭제이다. 데이터를 삭제할 경우 Front는 다음 위치의 노드를 가리키게 됨

삭제 시 한 가지 알아둬야할 작업이 있다. 아래의 그림을 보자. C를 Dequeue 함수로 삭제하였을 경우 Front는 C의 nextNode인 nullptr을 가리키게되지만 Rear의 경우에는 삭제된 C의 포인터를 가지게 된다. 여기에서는 Rear를 참조하는 함수가 없기 때문에 문제가 발생되지 않는다.

Dequeue 연산으로 Rear가 삭제된 포인터를 가리키고 있는 그림

개념에 대해 알아보았으니 코드를 이용하여 구현해보자.

#include <iostream>
 
using namespace std;
 
// 노드 구조체
typedef struct node
{
    // 생성자
    node() : data(0), nextNode(nullptr) {}
 
    // 데이터
    int data;
 
    // 다음 노드를 가리키는 포인터
    node* nextNode;
}NODE;
 
// 큐 구조체
typedef struct queue
{
    // 생성자
    queue() : front(nullptr), rear(nullptr) {}
 
    NODE* front;
    NODE* rear;
}QUEUE;
 
bool IsEmpty(QUEUE* queue)
{
    // 비어있을 경우 true를 반환
    if (queue->front == nullptr)
        return true;
 
    return false;
}
 
void Enqueue(QUEUE* queue, int data)
{
    // rear를 한칸 이동한 후 데이터 저장
    NODE* newNode = new NODE;
    newNode->data;
    newNode->nextNode = nullptr;
 
    // 첫 번째 노드 추가일 경우
    if (IsEmpty(queue))
    {
        // front와 rear가 새 노드를 가리키게 함
        queue->front = newNode;
        queue->rear = newNode;
    }
    // 두 번째 노드 이후 추가일 경우
    else
    {
        // 마지막 노드를 새로 생성한 노드를 가리키게함
        queue->rear->nextNode = newNode;
 
        // rear가 새로운 노드를 가리키게함
        queue->rear = newNode;
    }
}
 
int Dequeue(QUEUE* queue)
{
    if (IsEmpty(queue))
    {
        cout << "큐가 비어있습니다." << endl;
        return 0;
    }
 
    // 삭제할 노드를 임시 변수에 저장
    NODE* deleteNode = queue->front;
    int data = deleteNode->data;
 
    // 프론트를 다음 위치를 가리키게한 후 노드 삭제
    queue->front = queue->front->nextNode;
    delete deleteNode;
 
    // 삭제한 데이터를 반환
    return data;
}
 
int Peek(QUEUE* queue)
{
    if (IsEmpty(queue))
    {
        cout << "큐가 비어있습니다." << endl;
        return 0;
    }
 
    // front 위치를 반환
    return queue->front->data;
}
 
int main()
{
    // 큐 생성
    QUEUE newQueue;
 
    // 데이터 삽입
    for (int i = 0; i < 5; ++i)
    {
        Enqueue(&newQueue, i);
    }
 
    // 데이터 검색
    cout << Peek(&newQueue) << endl;
 
    // 데이터가 존재하지 않을 때까지 루프문 순회
    while (IsEmpty(&newQueue) == false)
    {
        // 데이터 출력
        cout << Dequeue(&newQueue) << endl;
    }
}