[자료구조] 데크(Deque)이해하기

1. Deque의 개념과 구조

Deque(데크)는 double-ended-queue의 줄임말로, 양방향에서 데이터를 처리할 수 있는 queue형 자료구조이다.

아래 그림과 같이, 양방향에서 엘리먼트를 추가, 삭제할 수 있는 양방향 큐라고 생각하면 된다. 

 

2. Deque에 존재하는 메서드 종류 

Python에서 deque는 collections라는 모듈안에 deque클래스로 내장되어있다. 

가장 기본적인 append() 메서드를 수행하면 다음과 같다. 

from collections import deque

deq = deque(['a', 'b', 'c'])
deq.append('d')
print(deq)    # deque(['a', 'b', 'c', 'd'])

기본 append()를 해주면 위의 예제와 같이 가장 오른쪽에 엘리먼트가 삽입된다. 

엘리먼트를 왼쪽 끝에 삽입하고 싶은 경우, appendleft()를 사용하면 된다. 이밖에도 다양한 종류의 메서드가 존재한다. 

 

deque.append(x) : x를 데크의 오른쪽 끝에 삽입한다

deque.appendleft(x) : x를 데크의 왼쪽 끝에 삽입한다

deque.pop() : 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서는 삭제한다

deque.popleft() : 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서는 삭제한다

deque.extend(array) : 배열 array를 순환하면서 데크의 오른쪽에 추가한다

deque.extendleft(array) : 배열 array를 순환하면서 데크의 왼쪽에 추가한다

deque.remove(x) : x를 데크에서 찾아 삭제한다

deque.rotate(num) : 데크를 num만큼 회전한다 (양수면 오른쪽, 음수는 왼쪽으로)

 

3. Deque를 쓰는 이유 

deque는 list보다 속도가 빠르고, 쓰레드 환경에서 안전하기 때문이다. 

pop(0)와 같은 메서드를 수행할 때 리스트의 경우 O(N)연산을 수행하지만 deque는 O(1) 연산을 수행한다.

따라서, push와 pop이 빈번한 알고리즘의 경우, list보다 deque를 사용하는것이 효율적이며 속도가 더 빠르다. 

 

4. 예제를 통해 이해하기 

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

2164번: 카드2

위의 예제는 백준 알고리즘에서 '큐'에 분류되어있는 문제이다. 

가장 앞에위치한 카드는 버리고, 그다음 카드는 가장 마지막으로 옮기는 과정을 반복하는 알고리즘. 

앞뒤에서 자유롭게 카드를 뽑고, 다시 넣는 과정을 구현해야해서 deque를 사용해서 풀이해보았다. 

 

풀이과정

 

양방향 큐를 구현하고, 가장 왼쪽카드를 삭제할때는 popleft(), 왼쪽카드를 뽑아 가장 오른쪽에 넣을때는 popleft()한걸 다시 append해주면 된다. 이 두가지 과정을 deque길이가 1이 될때까지 반복하는것. 

 

전체 코드

from collections import deque
n = int(input())
deq = deque()    # collections.deque 사용

for i in range(n):
    deq.append(i+1)    # [] <- 오른쪽에서 순서대로 삽입
# deque([1, 2, ... , n])
while len(deq) > 1:
    deq.popleft()    # 데크의 왼쪽 끝 원소를 가져오는 동시에 데크에서는 삭제
    deq.append(deq.popleft())    # 데크의 왼쪽 끝 원소를 뽑아서 오른쪽 끝에 삽입
print(deq.pop())    # 데크의 길이가 1 이하인경우 빠져나와 pop() 수행

deq.append(deq.popleft()) 이부분 대신에 deq.rotate(-1)을 해도 같은결과가 나온다. 

rotate(num)은 해당 큐를 num만큼 회전하라는 의미로, -1만큼 왼쪽으로 한칸 큐를 회전시키는것.

가장 왼쪽에 있는 엘리먼트가 가장 오른쪽에 오게되므로, pop + append와 동일하다.