C++ 큐 자료구조

큐 설명

큐는 뒤쪽에 새로운 항목을 삽입하고 앞쪽의 항목을 제거하는 리스트입니다. 이런 리스트가 왜 필요할까요? 알고리즘에서 임시 리스트에 객체를 추가하고 나중에 이 리스트에서 객체를 꺼내려고 하는 경우가 많습니다.

이러한 큐를 가리켜 FIFO라고도 하는데요. 이는 first-in, first-out의 약자로 먼저 들어온 것이 먼저 나간다는 의미를 갖고 있습니다.

큐 문제

출처 : 백준 알고리즘

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 <= N <= 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

ex)

15  
push 1  
push 2  
front  
back  
size  
empty  
pop  
pop  
pop  
size  
empty  
pop  
push 3  
empty  
front

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

ex)

1  
2  
2  
0  
1  
2  
-1  
0  
1  
-1  
0  
3

풀이

#include <iostream>
    
using namespace std;
    
int stack[10000];
int ind = -1;
    
void push(int x) {
    stack[++ind] = x;
}
    
int empty() {
    if (ind < 0) {
        return 1;
    } else {
        return 0;
    }
}
    
void pop()  {
    if (empty() == 1) {
        cout << "-1" << "\n";
    } else {
        cout << stack[0] << "\n";
        
        for(int i=0; i<ind; i++) {
            stack[i] = stack[i+1];
        }
        
        stack[ind--] = 0;
    }
}
 
int main() {
    int n;
    cin >> n;
    
    for (int i = 0; i < n; i++) {
        string command;
        cin >> command;
        
        if ("push" == command) {
            int x; 
            cin >> x;
            push(x);
        } else if ("pop" == command) {
            pop();
        } else if ("empty" == command) {
            cout << empty() << "\n";
        } else if ("back" == command) {
            if (empty() == 1) {
                cout << "-1" << "\n";
            } else {
                cout << stack[ind] << endl;
            }
        } else if ("front" == command) {
            if (empty() == 1) {
                cout << "-1" << "\n";
            } else {
                cout << stack[0] << endl;
            }
        } else if ("size" == command) {
            cout << ind+1 << endl;
        }
    }
    return 0;
}