Queue

queue는 원소를 순서대로 넣고 가장 먼저 추가한 원소부터 꺼내는 선입선출(FIFO, First In First Out) 자료구조이다.

헤더 파일

queue를 사용하려면 다음 헤더 파일을 포함해야 한다.

#include<queue>

보통 PS에서는 여러 표준 라이브러리를 한 번에 포함하기 위해 다음 헤더 파일을 사용한다.

#include<bits/stdc++.h>

선언

빈 queue는 다음과 같이 선언한다. $O(1)$

queue<int> q;

위 코드는 int 자료형의 원소를 저장하는 queue를 생성한다.

원소 추가와 삭제

맨 뒤에 원소를 추가할 때는 push()를 사용한다. $O(1)$

q.push(10);
q.push(20);
q.push(30);

위 코드를 실행하면 10, 20, 30이 차례대로 저장된다.

가장 먼저 추가한 10이 맨 앞에 위치하고, 가장 나중에 추가한 30이 맨 뒤에 위치한다.

맨 앞 원소를 삭제할 때는 pop()을 사용한다. $O(1)$

q.pop();

위 코드를 실행하면 맨 앞에 있던 10이 삭제된다.

pop()은 원소를 삭제하지만, 삭제한 값을 반환하지는 않는다.

원소 접근

맨 앞 원소와 맨 뒤 원소는 각각 front(), back()으로 확인할 수 있다. $O(1)$

cout << q.front();
cout << q.back();

queue에서는 맨 앞 원소와 맨 뒤 원소에만 접근할 수 있다.

배열이나 vector와 달리 인덱스를 이용해 중간 원소에 직접 접근할 수는 없다.

단, 비어 있는 queue에서 front(), back(), pop()을 호출하면 안 된다.

크기 확인

현재 저장된 원소의 개수는 size()로 확인한다. $O(1)$

cout << q.size();

비어 있는지는 empty()로 확인한다. $O(1)$

if(q.empty()) {
    cout << "empty";
}

empty()는 원소가 하나도 없으면 true, 그렇지 않으면 false를 반환한다.

연습 문제

C++ Queue

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

int main() {
    cin.tie(0)->sync_with_stdio(0);
    queue<int> Q;
    int q; cin >> q;
    while(q--) {
        string s; cin >> s;
        if(s=="push") {
            int x; cin >> x;
            Q.push(x);
        } else if(s=="pop") {
            Q.pop();
        } else if(s=="front") {
            cout << Q.front() << '\n';
        } else if(s=="back") {
            cout << Q.back() << '\n';
        } else {
            cout << Q.size() << '\n';
        }
    }
}