큐

큐(Queue)

큐는 앞과 뒤가 모두 열려있는 원통과 같다. 먼저 넣은 값이 먼저 나오는 FIFO방식을 따른다.

큐는 먼저 들어오는 값을 먼저 처리해야하는 BFS, 레벨 순회 등에서 사용할 수 있다.

C++에서는 큐 자료형이 존재하기 때문에 헤더파일 하나만 추가하면 바로 사용할 수 있다.

아래는 큐의 멤버 함수 들이다.

c++

#include <queue> // queue 헤더 파일 필요

queue<자료형> 큐 이름;
queue<int> q;  // 선언

q.push(value); // 큐에 갑 삽입
q.pop();  // 큐의 맨 앞에 있는 값을 삭제
q.size();  // 큐의 크기 반환
q.empty();  // 큐가 비어있다면 참, 아니라면 거짓을 반환
q.swap(& other queue);  // 다른 큐와 내부 데이터를 교환

queue와 함께 쓰이는 pair 자료형도 간략하게 소개하겠다.

pair는 중괄호로 묶인 두 값을 하나의 변수로 하는 자료형이다.

두 값이 함께 다니기 때문에 좌표를 pair로 설정하면 편하게 좌표끼리 연산할 수 있다.

아래는 C++에서 사용하는 방법이다.

c++

#include <utility> // pair가 들어있는 헤더파일

pair<자료형,자료형> pair 이름;
pair<int,int> p;

p.first // pair의 첫 번째 변수 접근
p.second // pair의 두 번째 변수 접근

p = {x,y} // p에 값 대입
p = make_pair(x,y)  // 윗줄과 같음


//큐와 함께 사용

queue<pair<int,int>> = q;
q.push({x,y});

예시) 백준 #10845 큐

c++

#include <iostream>
#include <queue>
using namespace std;
int main() {

    queue<int> q;
    int n;
    cin>>n;

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

        if( s == "push") {
            int a;
            cin>>a;
            q.push(a);
        } else if( s == "front") {
            cout<<((q.empty()) ? -1 : q.front())<<endl;
        } else if( s == "back") {
            cout<<((q.empty()) ? -1 : q.back())<<endl;
        } else if( s == "size") {   
            cout<<q.size()<<endl;
        } else if( s == "empty") {
            if(q.empty()) cout<<1<<endl;
            else cout<<0<<endl;
        } else if( s == "pop") {
            if(q.empty()) cout<<-1<<endl;
            else {
                cout<<q.front()<<endl;
                q.pop();
            }
        }
    }
}

큐를 선언하고 사용하는 기본 문제이다.