큐(Queue) 명령 처리 — STL로 O(1)

명령 목록

• push X : 뒤에 X를 넣기
• pop : 맨 앞 원소 출력 후 제거 (없으면 -1)
• size : 원소 개수
• empty : 비었으면 1, 아니면 0
• front : 맨 앞 원소 (없으면 -1)
• back : 맨 뒤 원소 (없으면 -1)

포인트

• std::queue<int> 사용, 각 연산 O(1)
• 비어있을 때 pop/front/back는 -1 출력
• 빠른 입출력: ios::sync_with_stdio(0), cin.tie(0)

시간·공간 복잡도

• 전체 O(n) (명령 n개 × 각 연산 O(1))
• 공간 O(n) (최대 n개 데이터 저장)

코드 (원문)

#include <bits/stdc++.h>
using namespace std;

int n;
queue<int> q;

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

    cin >> n;

    for (int i = 0; i < n; i++) {
        
        string in;
        cin >> in;

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

    return 0;
}

자주 하는 실수

• empty의 출력은 불리언이 아니라 1/0 규약에 맞추기
• 비어있을 때 pop/front/back에서 -1 꼭 출력하기