큐

: 한 쪽 끝에서 원소를 넣고 반대 쪽 끝에서 원소를 뺄 수 있는 자료구조; FIFO(First In First Out)

1. 성질

1. 원소의 추가 O(1)
2. 원소의 제거 O(1)
3. 제일 앞/뒤 원소 확인 O(1)
4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

2. 구현

배열과 연결리스트로 구현 가능하지만 여기서는 배열로 구현함
연결리스트의 push, pop, front와 back 연산 구현

push: tail에 원소를 넣고 tail을 증가시킨다.
pop: head를 증가시킨다.
front: head의 원소를 반환한다.
back: tail-1의 원소를 반환한다.

#include <iostream>
using namespace std;

const int MX = 1000005;
int dat[MX];
int head = 0, tail = 0;

void push(int x){
    dat[tail++] = x;
}

void pop(){
    head++;
}

int front(){
    return dat[head];
}

int back(){
    return dat[tail-1];
}

queue를 줄서기로 생각하면 기억하기 쉽다.
줄의 가장 앞을 head로 가리키고, 줄의 끝은 tail로 가리킨다. 주의 할점은 tail은 마지막 원소가 아닌 마지막 원소의 한 칸 뒤이다.

위와 같은 큐는 원소의 추가/제거가 반복될수록 배열의 인덱스가 뒤로 밀리게 된다. 따라서 앞의 공간이 많더라도 추가할 수 없는 문제가 생겨 공간이 낭비 될 수있다. 이 문제를 해결하기 위해 원형큐를 사용한다.
원형큐를 구현하기 위해서는 head에서 -1을 하면 마지막 원소가 있는 번지로, tail에서 1이 더해지면 다시 0번지로 오도록 작성한다.

코딩 테스트에서는 push할 데이터의 개수가 정해져 있으므로, 큐를 구현해야 한다면 배열의 크기를 데이터의 개수보다 크게 잡아 선형큐를 사용하면 된다.

3. STL queue

front: 맨 앞 원소를 반환한다. (head가 가리키는 원소 반환)
back: 맨 뒤 원소를 반환한다. (tail-1이 가리키는 원소 반환)
pop: 맨 앞 원소를 제거한다. (head가 가리키는 원소 제거)
push: 맨 뒤에 원소를 추가한다. (tail에 원소를 추가)

주의
queue가 비었을 때 front, back과 pop 호출시 런타임 에러 발생

보통 큐는 BFS와 Flood Fill을 할 때 사용하고 주로 STL Queue를 사용한다.

4. 연습문제

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

i) STL queue를 사용하여 풀이

#include <iostream>
#include <queue>
using namespace std;

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

    int n;
    queue<int> q;
    cin >> n;
    while(n--) {
        string op;
        cin >> op;
        if(op == "push") {
            int a;
            cin >> a;
            q.push(a);
        }
        else if(op == "pop") {
            if(q.empty()) {
                cout << "-1" << '\n';
            }
            else {
                cout << q.front() << '\n';
                q.pop();
            }
        }
        else if(op == "size")   cout <<q.size() << '\n';
        else if(op == "empty")  cout << int(q.empty()) << '\n';
        else if(op == "front")  {
            if(q.empty())   cout << "-1" << '\n';
            else {
                cout << q.front() << '\n';
            }
        }
        else {
            if(q.empty())   cout << "-1" << '\n';
            else
                cout << q.back() << '\n';
        }
    }

}

ii) 큐를 배열로 구현하여 풀이

#include <iostream>
using namespace std;
const int MX = 1000005;
int dat[MX];
int head = 0, tail = 0;

void push(int x) {
    dat[tail++] = x;
}

void pop() {
    head++;
}

int front() {
    return dat[head];
}

int back() {
    return dat[tail-1];
}

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

    int n;
    cin >> n;
    while(n--) {
        string op;
        cin >> op;
        if(op == "push") {
            int a;
            cin >> a;
            push(a);
        }
        else if(op == "pop") {
            if(head == tail) {
                cout << "-1" << '\n';
            }
            else {
                cout << front() << '\n';
                pop();
            }
        }
        else if(op == "size")   cout << tail-head << '\n';
        else if(op == "empty")  cout << int(head == tail) << '\n';
        else if(op == "front")  {
            if(head == tail)   cout << "-1" << '\n';
            else {
                cout << front() << '\n';
            }
        }
        else {
            if(head== tail)   cout << "-1" << '\n';
            else
                cout << back() << '\n';
        }
    }

}

front, back or pop 연산시 empty인지 확인해주는 작업이 필요하다.
tail - head가 큐의 size이다.
head == tail일 때 큐는 비어있다.

참고 자료: https://blog.encrypted.gg/934