Aidengoldkr – Tech Blog

지난 포스트 Stack에 이은 큐 (Queue) 자료구조에 대해 알아보자, 큐는 스택과 반대로, FIFO(First-In-First-Out), 후입 선출 LILO(Last-In-Last-Out) 규칙을 따른다. 예를 들어, 웨이팅 줄이 대표적이다.

 

큐를 이용하는 명령어는 크게 6가지가 있는데

• push X: 정수 X를 큐에 넣는다.
• size: 큐에 들어있는 값 개수를 출력한다.
• front: 큐의 가장 앞에 있는 값을 출력한다. 
• back: 큐의 가장 뒤에 있는 값을 출력한다. 
• empty: 큐가 비어있는지 판단한다.
• pop: 큐에서 가장 앞에 있는 값을 빼고, 그 값을 출력한다. 

C 기준으로 큐도 구현하는 방법이 크게 두가지 있는데,

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int main() {
    int N;
    cin >> N;
    
    queue<int> q;
    string cmd;
    
    while (N!=0) {
        cin >> cmd;
        
        if (cmd == "push") {
            int x;
            cin >> x;
            q.push(x);
        }
        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() ? 1 : 0) << '\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';
        }
        N--;
    }
}

queue 내장 함수를 사용하는 방법과

 

#include <iostream>
#include <string>
using namespace std;

int queue[2000000];
int top = 0, btm = 0;

void push(int n) {
    queue[top++] = n;
}

void pop() {
    if (btm == top) {
        cout << -1 << '\n';
    } else {
        cout << queue[btm++] << '\n';
    }
}

void size() {
    cout << top - btm << '\n';
}

void empty() {
    cout << (btm == top ? 1 : 0) << '\n';
}

void front() {
    if (btm == top) cout << -1 << '\n';
    else cout << queue[btm] << '\n';
}

void back() {
    if (btm == top) cout << -1 << '\n';
    else cout << queue[top - 1] << '\n';
}

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

    int a, n;
    string cm;
    cin >> a;

    while (a--) {
        cin >> cm;
        if (cm == "push") {
            cin >> n;
            push(n);
        } else if (cm == "pop") pop();
        else if (cm == "size") size();
        else if (cm == "empty") empty();
        else if (cm == "front") front();
        else if (cm == "back") back();
    }
}

직접 모든 명령어를 array로 구현하는 방법이 있다