큐(Queue)

큐가 뭐에요

큐는 가장 먼저 넣은 값이 가장 먼저 빠져나오는 FIFO(First-In-First-Out)의 자료구조입니다. 큐에 push 연산을 하면 원소가 추가되고, pop 연산을 하면 가장 먼저 넣은 원소가 삭제됩니다. 그 외에도 size(큐의 크기), front(가장 앞에 있는 원소), back(가장 뒤에 있는 원소), empty(비었는지) 연산이 있습니다.

참고로 큐는 나중에 BFS에서 나오니 꼭 알아두세요.

구현은 어케 해요

구현은 스택과 마찬가지로 연결 리스트를 통해 구현할 수도 있고, STL 내장 기능을 사용하는 방법이 있습니다.

특별히 STL을 사용할 수 없는 환경이 아니라면 STL 내장 큐를 사용하는 것이 훨씬 편합니다.

queue<자료형> 이름;과 같은 방식으로 선언해서 push(원소), pop(), front(), back(), empty(), size() 같은 함수를 사용할 수 있습니다.

(사용 예시)

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

int main() {
    queue<int> Q;
    Q.push(1);
    Q.push(2);
    Q.push(3);
    Q.pop();
    cout<<Q.size()<<" "<<Q.empty()<<" "<<Q.front()<<" "<<Q.back();
    return 0;
}

예시 1

https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

풀이

문제에서 시키는 것을 큐를 통해서 구현하면 됩니다.

1. 우선 큐에 1부터 N까지의 수를 모두 넣습니다.

2. K-1개의 수를 pop하고 다시 push한 다음 가장 앞에 있는 수를 출력하고, 그 수를 pop합니다.

3. 이 과정을 N번 반복하면 됩니다.

소스코드

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

int N, K;
queue<int> Q;

int main(void) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>K;
    for(int i=1; i<=N; i++) Q.push(i);
    cout<<"<";
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=(K-1)%(N-i+1); j++) {
            Q.push(Q.front());
            Q.pop();
        }
        cout<<Q.front();
        Q.pop();
        if(i!=N) cout<<", ";
    }
    cout<<">";
    return 0;
}

예시 2

https://www.acmicpc.net/problem/2164

2164번: 카드2

풀이

마찬가지로 문제에서 하라는 것을 큐를 통해 구현하면 됩니다.

소스코드

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

int N;
queue<int> Q;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N;
    for(int i=1; i<=N; i++) Q.push(i);
    for(int i=1; i<N; i++) {
        Q.pop();
        Q.push(Q.front()); Q.pop();
    }
    cout<<Q.front();
    return 0;
}

예시 3

https://www.acmicpc.net/problem/13335

13335번: 트럭

풀이

이 문제를 푸는 방법은 굉장히 다양하지만, 그중 큐를 사용한 방법을 소개하겠습니다.

다리의 각 칸에 있는 트럭을 큐에 저장합니다. 그러면 처음에는 큐에 W개의 0이 들어가 있습니다.

시간이 단위시간만큼 흐르면, 큐의 front 값은 pop되고, 새로운 트럭이 들어오거나 0이 들어옵니다.

이 때 다 들어온 트럭의 인덱스와 현재 하중의 합을 관리하면서 진행시키면 문제를 해결할 수 있습니다.

소스코드

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

const int Nmax=1010;
int N, W, L, ans, A[Nmax];
queue<int> Q;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N>>W>>L;
    for(int i=1; i<=N; i++) cin>>A[i];
    for(int i=1; i<=W; i++) Q.push(0);
    int p=1, sum=0;
    while(true) {
        ans++;
        if(Q.front()==N) break;
        sum-=A[Q.front()]; Q.pop();
        if(p<=N && sum+A[p]<=L) {
            Q.push(p); sum+=A[p++];
        }
        else Q.push(0);
    }
    cout<<ans;
    return 0;
}