Data Structure in C++ - Queue

본 포스팅 시리즈에서는 모든 프로그래머들이 반드시 알아야 할 가장 기본적인 자료구조를 다룰 예정이다.

앞으로 다룰 내용은 프로그래머에게 기본 소양이며, 본인 스스로 직접 구현할 수 있어야 한다. 

 

| 네 번째 순서는 큐이다. 

큐는 스택과 정 반대되는 특징을 가지고 있다. 마지막으로 들어간 노드가 마지막에 나오는 구조이다. 
FIFO(First In First Out)인 선입선출의 특징을 가지고 있으며, 보통 실제 세상에서 줄 서기와 같이 많은 상황이 큐로 표현될 수 있다.

스택과는 달리 마지막 노드인 top노드만 기억될게 아니라 맨 앞, 맨 뒤가 함께 기억되어야 한다. 

마찬가지로 큐는 가장 유명한 그래프 탐색 방법 중 하나인 BFS에 사용되며, 큐의 구현 방법에 따라 원형 큐 등 다양한 형태로 변환할 수 있다. 

아래는 큐의 구현이다. 

template <typename T>
class Node
{
public:
    T value;
    Node * next;
    Node * previous;

    Node(T value)
    {
        this->value = value;
    }
};

class Queue{
private:
    int size_;
    Node<T> * head_ = nullptr;
    Node<T> * tail_ = nullptr;
public:
    Queue()
    {
        this->size_ = 0;
    }

    void push(T value) {
        if (this->head_ == nullptr) {
            this->head_ = new Node<T>(value);
            this->tail_ = this->head_;
        } else {
            this->tail_->next = new Node<T>(value);
            this->tail_->next->previous = this->tail_;
            this->tail_ = this->tail_->next;
        }
        this->size_ += 1;
    }

    void pop() {
        if (this->head == nullptr) {
            cout << "queue is empty" << endl;
        } else {
            Node<T> *tmp = this->head_;
            this->head_ = this->head_->next;
            delete tmp;

            if(this->head_ == nullptr){
                this->tail_ = this->head_;
            }
            this->size_ -= 1;
        }
    }

    T front() {
        if (this->head == nullptr) {
            cout << "queue is empty" << endl;
        } else {
            return this->head_->value;
        }
    }

    T back() {
        if (this->tail == nullptr) {
            cout << "queue is empty" << endl;
        } else {
            return this->tail_->value;
        }
    }

    bool IsEmpty() {
        return (this->size_ == 0);
    }

    int size() {
        return (this->size_);
    }
}

push는 뒤에 pop은 맨 앞 원소를 가져오게 구현해야 한다. 또한 가장 앞 원소와 가장 뒷 원소를 가져올 수 있는 함수가 각각 구현되어있는 것이 좋다.