큐 (Queue)

큐란?

큐의 enqueue 와 dequeue

Queue 자료구조는 배열로도 구현할 수 있고, 연결 리스트로도 간단하게 구현할 수 있다. 위 이미지와 같이 Queue는 먼저 들어온 요소가 먼저 나올 수 있는 선입선출(FIFO, First In First Out)의 자료구조이다.

Queue에는 값을 넣을수 있는 enqueue와 값을 꺼낼 수 있는 dequeue를 구현한다.

이는 대략적으로 아래와 같은 구조를 가진다.

//노드
class Node<T> is
    T data
    Node<T> next
    
//연결 리스트
class Queue<T> is
    Node<T> front
    Node<T> rear
    int size
    
    method is_empty(): boolean
    method peek(): T
    method enqueue(T item)
    method dequeue(): T

큐의 필수기능 구현

값 추가 (enqueue)

method enqueue(T item) is
    Node<T> newNode = new Node<>(item)
    if is_empty() then
        front = newNode // 큐가 비어있다면 새로운 노드로 front를 설정
    else
        rear.next = newNode //요소가 있다면, rear의 다음 노드로 설정
    rear = newNode
    size++

값 제거 (dequeue)

method dequeue(): T is
    if is_empty() then
        throw EmptyQueueException
    T item = front.data // front의 데이터를 가져온다.
    front = front.next // front를 다음 노드로 설정
    
    // front가 null이면 rear도 null로 설정
    if (front == null) then
        rear = null
    
    size--
    return item

공백 확인 (is_empty)

method is_empty(): boolean is
    return size == 0

값 확인 (peek)

method peek(): T is
    if is_empty() then
        throw EmptyQueueException
    return front.data

큐의 구현

using namespace std;

template <typename T>
class Queue {
private:
    struct Node {
        T data;
        Node *next;
        explicit Node(const T &data): data(data), next(nullptr) {}
    };  
    Node *front;
    Node *rear;
    size_t size;

public:
    Queue(): front(nullptr), rear(nullptr), size(0) {}
    ~Queue() {
        while (!is_empty()) {
            dequeue();
        }
    }
    bool is_empty() const {
        return size == 0;
    }
    void enqueue(T data) {
        Node *newNode = new Node(data);
        if (is_empty()) {
            front = newNode;
        } else {
            rear->next = newNode;
        }
        rear = newNode;
        size++;
    }
    T dequeue() {
        if (is_empty()) throw underflow_error("Queue is empty!");
        Node* temp = front;
        front = front->next;
        T data = temp->data;
        delete temp;

        if (front == nullptr) rear = nullptr;

        size--;
        return data;
    }
    T peek() const {
        if (is_empty()) throw underflow_error("Queue is empty!");
        return front->data;
    }
    friend ostream& operator<<(ostream& os, const Queue& q) {
        os << "[";
        Node* temp = q.front;
        while (temp != nullptr) {
            os << temp->data;
            if (temp->next != nullptr) os << ", ";
            temp = temp->next;
        }

        os << "]";
        return os;
    }
};