큐 · 알고리즘 노트

개념

큐는 먼저 삽입한 원소를 먼저 제거하는 선입선출(FIFO) 자료구조입니다. 뒤쪽에 원소를 삽입하고 앞쪽에서 원소를 제거합니다.

뒤에 원소 추가

앞에서부터 $10,20,30,40,50$ 이 들어 있는 큐에 $60$ 을 추가합니다. 앞쪽 끝을 front, 뒤쪽 끝을 back이라고 합니다.

▲ [그림 1] 큐의 뒤쪽 원소 추가 — 연산 전

$60$ 은 back에 있는 $50$ 뒤에 들어갑니다. 새 원소 $60$ 이 back이 됩니다.

▲ [그림 2] 큐의 뒤쪽 원소 추가 — 연산 후

앞에서 원소 삭제

$10,20,30,40,50,60$ 을 차례로 넣은 큐에서 원소를 하나 꺼냅니다.

▲ [그림 3] 큐의 원소 제거 — 연산 전

가장 먼저 넣은 $10$ 이 제거되고, 다음에 넣은 $20$ 이 새로운 front가 됩니다.

▲ [그림 4] 큐의 원소 제거 — 연산 후

언어별 사용법

동작	C++ `queue`	Java `ArrayDeque`	Python `collections.deque`
뒤에 넣기	`q.push(x)`	`q.offerLast(x)`	`q.append(x)`
앞 읽기	`q.front()`	`q.peekFirst()`	`q[0]`
앞에서 꺼내기	`q.pop()`	`q.pollFirst()`	`q.popleft()`
크기	`q.size()`	`q.size()`	`len(q)`

삽입·삭제는 $O(1)$ 또는 내부 배열 확장에 따른 분할 상환 $O(1)$ 입니다. 공간복잡도는 $O(N)$ 입니다.

Python의 list.pop(0)은 $O(N)$ 이므로 큐에는 deque를 사용합니다.

예제

문제

처음에 비어 있는 큐에 다음 명령을 순서대로 수행하여라.

명령	동작
`push x`	맨 뒤에 $x$ 를 추가한다.
`front`	맨 앞 값을 출력한다. 빈 큐이면 `EMPTY`를 출력한다.
`pop`	맨 앞 값을 출력하고 제거한다. 빈 큐이면 `EMPTY`를 출력한다.
`size`	원소 수를 출력한다.

입력

첫째 줄에 명령 수 $N$ 가 주어진다. $1\le N\le10\,000$ 이다.

다음 $N$ 개 줄에 위 표의 형식으로 명령이 하나씩 주어진다. 명령과 인자는 공백을 사이에 두고 주어진다. 추가할 값 $x$ 의 범위는 $1\le x<10\,000$ 이다.

출력

출력이 필요한 명령의 결과를 한 줄에 하나씩 출력한다.

예제 코드

C++20

#include <iostream>
#include <string>
#include <queue>

using namespace std;

int main() {
    int n, i, x;
    queue<int> q;
    string op;

    cin >> n;

    for (i = 0; i < n; ++i) {
        cin >> op;

        if (op == "push") {
            cin >> x;

            q.push(x);
        }
        else if (op == "size") cout << q.size() << '\n';
        else if (q.empty()) cout << "EMPTY\n";
        else if (op == "front") cout << q.front() << '\n';
        else {
            cout << q.front() << '\n';
            q.pop();
        }
    }
}

Java 17

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in;
        int n, i;
        ArrayDeque<Integer> q;
        String op;

        in = new Scanner(System.in);
        n = in.nextInt();

        q = new ArrayDeque<>();
        for (i = 0; i < n; ++i) {
            op = in.next();

            if (op.equals("push")) q.offerLast(in.nextInt());
            else if (op.equals("size")) System.out.println(q.size());
            else if (q.isEmpty()) System.out.println("EMPTY");
            else if (op.equals("front")) System.out.println(q.peekFirst());
            else System.out.println(q.pollFirst());
        }
    }
}

Python 3

from collections import deque

n = int(input())
q = deque()

for _ in range(n):
    cmd = input().split()
    op = cmd[0]

    if op == "push":
        q.append(int(cmd[1]))
    elif op == "size":
        print(len(q))
    elif not q:
        print("EMPTY")
    elif op == "front":
        print(q[0])
    else:
        print(q.popleft())

1.1.4 Queue

개념

뒤에 원소 추가

앞에서 원소 삭제

언어별 사용법

예제

문제

입력

출력

예제 입력

예제 출력

예제 코드