Queue

큐의 성질

1. FIFO(First In First Out), 선입선출의 구조
2. 원소의 추가가 O(1)
3. 원소의 제거가 O(1)
4. 제일 앞/뒤의 원소 확인이 O(1)
5. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능

큐

큐도 스택과 마찬가지로 구현하는 것은 거저먹기입니다.
큐가 비었을 때 front나 back을 아무런 경계 없이 사용하면 원하는 결과가 나오지 않을 수 있습니다.

큐 https://github.com/Geniemo/PracticalAlgo/blob/master/Queue.cpp

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

const int MX = 1000005;
int dat[MX];
int head = 0, tail = 0; // head는 가장 앞에 있는 원소의 인덱스, tail은 가장 뒤에 있는 원소의 인덱스 + 1

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

void pop() {
    head = (head + 1) % MX;
}

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

int back() {
    return dat[(tail == 0 ? MX - 1 : tail - 1)];
}

bool isEmpty() {
    return head == tail;
}

void test() {
    push(1);
    push(2);
    push(3);
    while (!isEmpty()) {
        cout << front() << " ";
        pop();
    }
}

int main(void) {
    test();
    return 0;
}

활용 예제

백준 1158번 https://www.acmicpc.net/problem/1158

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

const int MX = 5005;
int dat[MX];
int head = 0, tail = 0; // head는 가장 앞에 있는 원소의 인덱스, tail은 가장 뒤에 있는 원소의 인덱스 + 1

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

void pop() {
    head = (head + 1) % MX;
}

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

int back() {
    return dat[(tail == 0 ? MX - 1 : tail - 1)];
}

bool isEmpty() {
    return head == tail;
}

int N, K;
int idx;
int seq[5000];

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N >> K;
    for (int i = 1; i <= N; i++)
        push(i);
    
    while (!isEmpty()) {
        for (int i = 0; i < K - 1; i++) {
            int tmp = front();
            pop();
            push(tmp);
        }
        seq[idx++] = front();
        pop();
    }

    cout << "<";
    for (int i = 0; i < N - 1; i++)
        cout << seq[i] << ", ";
    cout << seq[N - 1] << ">";
    return 0;
}