덱 · 알고리즘 노트

개념

덱은 앞과 뒤 양쪽 끝에서 원소를 삽입·삭제하는 자료구조입니다. 앞쪽 끝을 front, 뒤쪽 끝을 back이라고 합니다.

앞에 원소 추가

앞에서부터 $20,30,40,50,60$ 이 들어 있는 덱입니다. front는 $20$ , back은 $60$ 입니다.

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

앞쪽에 $10$ 을 넣으면 $20$ 앞에 들어가고, $10$ 이 새로운 front가 됩니다.

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

뒤에 원소 추가

앞에서부터 $10,20,30,40,50,60$ 이 들어 있는 덱에 $70$ 을 추가합니다.

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

뒤쪽에 $70$ 을 넣으면 $60$ 뒤에 들어가고, $70$ 이 새로운 back이 됩니다.

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

앞에서 원소 삭제

앞에서부터 $10,20,30,40,50,60,70$ 이 들어 있는 덱에서 앞쪽 원소를 꺼냅니다.

▲ [그림 5] 덱의 앞쪽 원소 제거 — 연산 전

front에 있던 $10$ 이 제거되고, $20$ 이 새로운 front가 됩니다.

▲ [그림 6] 덱의 앞쪽 원소 제거 — 연산 후

뒤에서 원소 삭제

앞에서부터 $20,30,40,50,60,70$ 이 들어 있는 덱에서 뒤쪽 원소를 꺼냅니다.

▲ [그림 7] 덱의 뒤쪽 원소 제거 — 연산 전

back에 있던 $70$ 이 제거되고, $60$ 이 새로운 back이 됩니다.

▲ [그림 8] 덱의 뒤쪽 원소 제거 — 연산 후

언어별 사용법

동작	C++ `deque`	Java `ArrayDeque`	Python `collections.deque`
앞에 넣기	`push_front(x)`	`addFirst(x)`	`appendleft(x)`
뒤에 넣기	`push_back(x)`	`addLast(x)`	`append(x)`
앞에서 꺼내기	`pop_front()`	`removeFirst()`	`popleft()`
뒤에서 꺼내기	`pop_back()`	`removeLast()`	`pop()`

양 끝 연산은 $O(1)$ 또는 분할 상환 $O(1)$ 이며, 공간복잡도는 $O(N)$ 입니다.

예제

문제

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

명령	동작
`push_front x`	맨 앞에 $x$ 를 추가한다.
`push_back x`	맨 뒤에 $x$ 를 추가한다.
`front`	맨 앞 값을 출력한다. 빈 덱이면 `EMPTY`를 출력한다.
`back`	맨 뒤 값을 출력한다. 빈 덱이면 `EMPTY`를 출력한다.
`pop_front`	맨 앞 값을 출력하고 제거한다. 빈 덱이면 `EMPTY`를 출력한다.
`pop_back`	맨 뒤 값을 출력하고 제거한다. 빈 덱이면 `EMPTY`를 출력한다.
`size`	원소 수를 출력한다.

입력

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

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

출력

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

예제 코드

C++20

#include <iostream>
#include <string>
#include <deque>

using namespace std;

int main() {
    int q, i, x;
    deque<int> dq;
    string op;

    cin >> q;

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

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

            dq.push_front(x);
        }
        else if (op == "push_back") {
            cin >> x;

            dq.push_back(x);
        }
        else if (op == "size") cout << dq.size() << '\n';
        else if (dq.empty()) cout << "EMPTY\n";
        else if (op == "front") cout << dq.front() << '\n';
        else if (op == "back") cout << dq.back() << '\n';
        else if (op == "pop_front") {
            cout << dq.front() << '\n';
            dq.pop_front();
        }
        else {
            cout << dq.back() << '\n';
            dq.pop_back();
        }
    }
}

Java 17

import java.util.*;

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

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

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

            if (op.equals("push_front")) dq.addFirst(in.nextInt());
            else if (op.equals("push_back")) dq.addLast(in.nextInt());
            else if (op.equals("size")) System.out.println(dq.size());
            else if (dq.isEmpty()) System.out.println("EMPTY");
            else if (op.equals("front")) System.out.println(dq.peekFirst());
            else if (op.equals("back")) System.out.println(dq.peekLast());
            else if (op.equals("pop_front")) System.out.println(dq.removeFirst());
            else System.out.println(dq.removeLast());
        }
    }
}

Python 3

from collections import deque

q = int(input())
dq = deque()

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

    if op == "push_front":
        dq.appendleft(int(cmd[1]))
    elif op == "push_back":
        dq.append(int(cmd[1]))
    elif op == "size":
        print(len(dq))
    elif not dq:
        print("EMPTY")
    elif op == "front":
        print(dq[0])
    elif op == "back":
        print(dq[-1])
    elif op == "pop_front":
        print(dq.popleft())
    else:
        print(dq.pop())

1.1.5 Deque

개념