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(LinkedList를 제외한)보다 속도가 빠르고, 쓰레드 환경에서 안전하기 때문이다. 

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

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

 

덱을 활용하는 문제!!

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

1021번: 회전하는 큐

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

5430번: AC