[기초] 큐

큐 는 순서가 있는 자료구조이다. 

C++ STL 의 queue 를 사용하자.

각 연산은 O(1) 만에 연산되며, 구현 시 이렇게 되어야 한다.

queue 는 배열 혹은 linked list 로 구현 가능하다.

c++ 의 vector 나 python 의 list 로 queue 를 구현하면 안된다.

vector 의 pop 연산은 모든 배열의 값을 하나 밀기 때문에 pop 이 O(N) 이 걸리므로, 정의와 다르다.

Queue 구현 (강의)

#include <iostream>
#include <string>
using namespace std;
struct Queue {
    int data[10000];
    int begin, end;
    Queue() {
        begin = 0;
        end = 0;
    }
    void push(int num) {
        data[end] = num;
        end += 1;
    }
    bool empty() {
        if (begin == end) {
            return true;
        } else {
            return false;
        }
    }
    int size() {
        return end - begin;
    }
    int front() {
        return data[begin];
    }
    int back() {
        return data[end-1];
    }
    int pop() {
        if (empty()) {
            return -1;
        }
        begin += 1;
        return data[begin-1];
    }
};
int main() {
    int n;
    cin >> n;

    Queue q;

    while (n--) {
        string cmd;
        cin >> cmd;
        if (cmd == "push") {
            int num;
            cin >> num;
            q.push(num);
        } else if (cmd == "pop") {
            if (q.empty()) {
                cout << -1 << '\n';
            } else {
                cout << q.front() << '\n';
                q.pop();
            }
        } else if (cmd == "size") {
            cout << q.size() << '\n';
        } else if (cmd == "empty") {
            cout << q.empty() << '\n';
        } else if (cmd == "front") {
            if (q.empty()) {
                cout << -1 << '\n';
            } else {
                cout << q.front() << '\n';
            }
        } else if (cmd == "back") {
            if (q.empty()) {
                cout << -1 << '\n';
            } else {
                cout << q.back() << '\n';
            }
        }
    }

    return 0;
}

덱(Double-ended queue)

덱은 BFS 에서 많이 쓴다.

C++ STL 에 구현되어 있다. deque

덱은 스택과 큐, 둘 다로 사용 가능하다.