C/C++ 큐(Queue) (2)- 연결 리스트로 구현, 클래스 구현

개요

연결 리스트로 큐를 구현해보고, C++ 클래스로 변환해보자. 연결 리스트는 구현이 매우 쉽다. 일반 배열로 하는 것과 다르게 실제로 데이터를 입력하면 공간을 할당하고 데이터를 출력하면 데이터의 메모리 할당을 해제하면 되어 훨씬 직관적이다.

연결 리스트 큐 구현 Node

struct Node
{
    int data;
    Node* next;
}* front = NULL, *rear = NULL;

front의 위치를 연결 리스트의 맨 앞, rear를 맨 뒤로 설정하여 front를 통해 데이터가 출력되고, rear를 통해 데이터가 들어간다.

enqueue함수-데이터 입력 함수

void enqueue(int x)
{
    Node* t;
    t = new Node;

    if (t == NULL)
        printf("Queue is Full\n");
    else{
        t->data = x;
        t->next = NULL;
        if (front == NULL)
            front = rear = t;
        else
        {
            rear->next = t;
            rear = t;
        }
    }
}

새로운 노드를 할당하고, 할당이 되지 않는다면(t=NULL) 메모리에 할당할 공간이 없다는 것이기에 큐가 꽉 찼다고 판단한다. 그게 아니라면 데이터를 넣고, rear의 다음에 노드를 연결하고 rear를 해당 노드로 옮긴다.

dequeue함수-데이터 출력 함수

int dequeue()
{
    int x = -1;
    Node* t = NULL;

    if (front == NULL)
        printf("Queue is Empty\n");
    else
    {
        x = front->data;
        t = front;
        front = front->next;
        delete t;
    }

    return x;
}

front가 NULL이라면 연결 리스트가 없다는 뜻이기에 비었다고 본다. 그게 아니라면 front의 데이터를 출력하고, front의 메모리를 해제하고, next 노드로 front를 옮긴다. 일반 배열에서는 front가 데이터의 시작의 앞 인덱스를 나타냈지만, 연결 리스트에서는 front가 맨 앞 데이터를 나타낸다는 차이가 있다.

Class 활용 큐 구현

로직은 같으므로 코드만 첨부하겠다. 클래스에 size, front, rear, Q를 모두 넣어 함수 인자로 큐 구조체를 주지 않아도 되는 점이 좋다.

#include <stdio.h>

class Queue
{
    private:
        int size;
        int front;
        int rear;
        int* Q;
    public:
        Queue(int size);
        void enqueue(int x);
        int dequeue();
        void display();
        ~Queue();
};

Queue::Queue(int size)
{
    size = size;
    Q = new int[size];
    front = rear = -1;
}

void Queue::enqueue(int x)
{
    if (rear == size - 1)
        printf("Queue is Full\n");
    else
    {
        rear++;
        Q[rear] = x;
    }
}

int Queue::dequeue()
{
    int x = -1;
    if (front == rear)
    {
        printf("Queue is Empty\n");
    }
    else
    {
        front++;
        x = Q[front];
    }
    return x;
}

void Queue::display()
{
    int i;
    for (i = front + 1; i <= rear; i++)
    {
        printf("%d ", Q[i]);
    }
    printf("\n");
}

추가::Dequeue(Double Enabled Queue)

Dequeue는 front와 rear을 통해 모두 데이터를 입력할 수 있고, 뺄 수 있는 양방향 큐이다. 일반 큐가 front는 오직 데이터 출력, rear이 오직 데이터 입력 구멍이라고 하면, Dequeue는 front를 통해서도 데이터를 넣고, 뺄 수 있고, rear에서도 가능하다. 이 또한, 코드를 보면 쉽게 이해할 수 있기에 코드만 첨부한다.

#include <stdio.h>

struct Queue
{
    int size;
    int front;
    int rear;
    int* Q;
};

void create(Queue *q,int x)
{
    q->size = x;
    q->front = q->rear = -1;
    q->Q = new int[q->size];

}

void enqueueRear(Queue *q, int x)
{
    if (q->rear == q->size - 1)
        printf("Queue is Full\n");
    else
    {
        q->rear++;
        q->Q[q->rear] = x;
    }
}

void enqueueFront(Queue *q, int x)
{
    if (q->front == -1)
        printf("Queue through Front is Impossible\n");
    else
    {
        q->Q[q->front] = x;
        q->front--;
    }
}

int dequeueRear(Queue *q)
{
    int x = -1;

    if (q->rear == -1)
        printf("Queue through Rear is Impossible\n");
    else
    {
        x = q->Q[q->rear] = x;
        q->rear--;
    }

    return x;
}

int dequeueFront(Queue *q)
{
    int x = -1;

    if (q->front == q->size - 1)
        printf("Queue through Front is Impossible\n");
    else
    {
        q->front++;
        x = q->Q[q->front];
    }

    return x;
}

void Display(Queue *q)
{
    for (int i = q->front + 1; i <= q->rear; i++)
        printf("%d ", q->Q[i]);
    printf("\n");
}

int main()
{
    Queue *q;
    create(q, 5);

    enqueueRear(q, 1);
    enqueueRear(q, 2);
    enqueueRear(q, 3);
    enqueueRear(q, 4);
    enqueueRear(q, 5);
    enqueueRear(q, 6);
    dequeueFront(q);
    enqueueFront(q, 7);
    Display(q);

    dequeueFront(q);
    Display(q);
    dequeueRear(q);
    Display(q);
}

마무리

클래스와 연결 리스트로 구현해 보았다. 연결 리스트로 구현했을 때, 훨씬 직관적인 구현이 가능했음을 알 수 있다. 여담으로, 스택은 FILO 형태로 처음 들어간 데이터가 제일 늦게 나오지만 스택을 두 개 사용하면 처음 들어간 데이터가 그 다음 스택으로 제일 늦게 들어갔다가 마지막에는 제일 먼저 나오므로 FIFO를 간접적으로 구현 가능하다.