이번엔 단일 연결리스트를 이용해서 Queue를 구현해보았다.

Queue의 특징

Queue는 Stack과 반대로 가장 먼저 들어온 데이터가 가장 먼저 나가는 FIFO구조를 가진 것이 대표적인 특징이다.
(출처 : https://techarticle.co.in/2023/06/understanding-queue-fifo-data-structure.html)

주요 연산

push(Enqueue) : 큐의 맨 뒤(rear)에 새로운 원소를 삽입하는 연산.

pop(Dequeue) : 큐의 맨 앞(front)에 있는 원소를 제거하는 연산.

empty : 큐가 비어있는지를 확인하는 연산.

구현 내용

단일 연결 리스트(Singly Linked List)를 이용하여 구현하였다.
front와 rear 포인터로 구성하였고,

front : 큐의 맨 앞 노드를 가리킴.

rear : 큐의 맨 뒤 노드를 가리킴.

코드

#include <iostream>

using namespace std;

#define MAX 100

template<typename T>
class Node
{
public:

    Node<T>* Next;
    T data;

    Node() : Next(nullptr), data(T()) {}
    Node(T Indata) : Next(nullptr), data(Indata) {}
};

template<typename T>
class Queue
{
public:

    Node<T>* front;
    Node<T>* rear;
    
    Queue() : front(nullptr), rear(nullptr) {}
    ~Queue()
    {
        while (!empty())
        {
            pop();
        }
    }
    void push(const T& value);
    void pop();
    bool empty();
    
};

template<typename T>
void Queue<T>::push(const T& value)
{
    Node<T>* newnode = new Node<T>(value);

    if (empty())
    {
        front = newnode;
        rear = newnode;
    }
    else
    {
        rear->Next = newnode;
        rear = newnode;
    }
}

template<typename T>
void Queue<T>::pop()
{
    if (empty())
    {
        cout << "IsEmpty" << endl;
    }
    else
    {
		    // 1개만 있을 때.
        if (front == rear)
        {
			Node<T>* temp = front;
            front = nullptr;
            rear = nullptr;
            delete temp;
        }
        else
        {
            Node<T>* temp = front;
            front = front->Next;
            
            delete temp;
        }
    }
}

template<typename T>
bool Queue<T>::empty()
{
    return front == nullptr && rear == nullptr;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    Queue<int> q;
    q.push(3);
    q.push(6);
    q.push(9);
    q.push(12);
    q.pop();
    
    while (!q.empty())
    {
        cout << q.front->data << endl;
        q.pop();
    }
}