[C++ STL 만들기] queue 구현

이번에는 여러가지 알고리즘을 사용할 때 꼭 필요한 queue를 구현해보았다. STL의 queue에서 제공하는 priority_queue는 따로 minheap, maxheap으로 따로 구현하도록 하겠다. 우선 구현한 코드는 아래 링크에서 확인할 수 있다.

https://github.com/Seo-sang/Cpp-_Standard_Template_Library/blob/master/myqueue.cpp

GitHub - Seo-sang/Cpp-_Standard_Template_Library: make C++ STL myself

 

queue란?

    queue(큐)는 stack과 같은 기본적인 자료구조로 가장 마지막으로 들어간 원소가 가장 먼저 나오는 LIFO(Last In First Out)인 stack과 다르게 가장 먼저 들어간 원소가 가장 먼저 나오는 FIFO(First In First Out)이다. queue를 그림으로 표현하면 다음과 같다.

그림과 같이 한쪽은 나올 수 만 있는 출구가 있고 다른 한 쪽은 들어갈 수만 있는 입구가 있다. queue안에서 순서는 바뀌지 않는다. 따라서 들어간 순서와 나오는 순서가 똑같다. 큐에 원소를 넣는 것을 'push'라고 하고 원소를 빼는 것을 'pop'이라고 한다. 위 그림은 1부터 6까지 push한 상태에서 1번 pop을 하고 7을 push하려고 하는 상태이다.

 

구현

     큐의 구현은 여러가지로 할 수 있다. 배열로 구현하는 것은 간단하지만  pop을 여러번 하는 경우 배열의 크기는 일정하기 때문에 배열의 앞 부분은 비어있는 상태가 될 수 있다. 또 배열의 크기보다 push를 많이 하는 경우 새로 할당해줘야하는 등의 오버헤드가 있기 때문에 그러한 번거로움을 줄일 수 있는 연결리스트로 구현하였다. 연결 리스트를 이용하여 구현하였기 때문에 이전 글 만들었던 list와 비슷한 부분이 많았다. 우선 각 노드를 나타내는 구조체는 아래와 같다.

struct node {
    T data; //값이 들어가는 변수
    node* next; //다음 노드를 가리키는 포인터

    node(T input) { //생성자
        data = input; //input을 준 경우 input으로 data를 설정
        next = NULL; //다음 노드는 NULL포인터로 설정
    }
    
    node() { //생성자
        data = 0; //input이 없는 경우 0으로 초기화
        next = NULL; //다음 노드는 NULL포인터로 설정
    }
};

STL queue에서 제공하는 대부분의 함수를 구현하였다. iterator가 없기 때문에 굉장히 간단했다. 구현한 메소드로는 empty, size, front, back, push, pop, swap이 있다.

 

실행 결과

1. push, pop 실행 결과

int main() {
    myqueue<int> q1;
    for(int i = 1; i <= 10; i++) //q1에 1부터 10까지 넣음
        q1.push(i);
    
    while(!q1.empty()) { //q1 출력
        cout << q1.front() << ' ';
        q1.pop();
    }
}

위 코드에 대한 실행 결과

2. front, back 실행 결과

int main() {
    myqueue<int> q1;
    for(int i = 1; i <= 10; i++) //q1에 1부터 10까지 넣음
        q1.push(i);
    
    cout << "front : " << q1.front() << "\nback : " << q1.back() << endl; //front, back 출력

    while(!q1.empty()) { //q1 출력
        cout << q1.front() << ' ';
        q1.pop();
    }
}

위 코드에 대한 실행 결과

3. swap 실행 결과

int main() {
    myqueue<int> q1, q2;
    for(int i = 1; i <= 10; i++) //q1에 1부터 10까지 넣음
        q1.push(i);
    
    for(int i = 101; i <= 110; i++) //q2에 101부터 110까지 넣음
        q2.push(i);

    q1.swap(q2); //q1과 q2 swap

    while(!q1.empty()) { //q1 출력
        cout << q1.front() << ' ';
        q1.pop();
    }
    
    cout << endl;

    while(!q2.empty()) { //q2 출력
        cout << q2.front() << ' ';
        q2.pop();
    }
    
}

위 코드에 대한 실행결과

이렇게 간단한 자료구조 queue를 구현해보았다. 우선순위 큐는 따로 minheap과 maxheap으로 구현하도록 하겠다.