[Python] 데크/덱 (deque)

덱 (deque) 이란?

• 큐를 양방향으로 쓸 수 있게 만든 자료구조
• 양 끝 엘리먼트에 대해서 append 와 pop이 가능함
• 스택과 큐를 동시에 사용 가능

사용법

from collections import deque

# 덱 선언
deq = deque()

# 0 ~ 5 까지 덱 추가
for i in range(5) :
	deq.append(i) # [0,1,2,3,4]

# 왼쪽 방향 값 추가
deq.appendleft(2) # [2, 0,1,2,3,4]

# 오른쪽 방향값 추출
pop = deq.pop() # [2, 0,1,2,3]
print(pop) # 4

# 왼쪽 방향값 추출
lpop = deq.popleft() # [0,1,2,3]
print(lpop) # 2

덱 (deque)의 메서드

• deque의 자료구조를 사용하기 위해서는 아래와 같이 선언해줘야 함

from collections import deque

append(x)

• 큐의 뒤로 삽입

queue = deque()
queue.append('b')
# queue = ['b']

queue.append('c')
# queue = ['b', 'c']

appendleft(x)

• 큐의 앞으로 삽입

queue = deque()
queue.append('b')
# queue = ['b']

queue.append('c')
# queue = ['b', 'c']

queue.appendleft('a')
# queue = ['a', 'b', 'c']

clear

• 큐의 모든 요소를 삭제

queue = deque()
queue.append('b')
# queue = ['b']

queue.append('c')
# queue = ['b', 'c']

queue.appendleft('a')
# queue = ['a', 'b', 'c']

queue.clear()
# queue = []

copy

• 얕은 복사

queue = deque()
queue.append('b')
# queue = ['b']

copied_queue = queue.copy()
# copied_queue = ['b']

count(x)

• 큐에서 x와 같은 값의 개수

queue = deque()
queue.append('b')
# queue = ['b']

queue.append('a')
# queue = ['b', 'a']

queue.appendleft('a')
# queue = ['a', 'b', 'a']

print(queue.count('a'))
# 2

extend(iterable)

• iterable 한 값을 파라미터로 넣으면 해당 값들이 하나씩 큐의 오른쪽에 붙음

queue = deque()
queue.append('b')
# queue = ['b']

queue.extend('lft')
# queue = ['b', 'l', 'f', 't']

queue.append('lft')
# queue = ['b', 'l', 'f', 't', 'lft']

extendleft(iterable)

• iterable 한 값을 파라미터로 넣으면 해당 값들이 하나씩 큐의 왼쪽에 붙음

queue = deque()
queue.append('b')
# queue = ['b']

queue.extendleft('lft')
# queue = ['t', 'f', 'l', 'b']

queue.apendleft('lft')
# queue = ['lft', 't', 'f', 'l', 'b']

index(x[, start[, stop]])

• 큐(인덱스 시작 후 및 인덱스 중지 전)에서 x의 위치를 반환
• 첫 번째 일치를 반환하거나 찾을 수 없는 경우 ValueError 발생

a = [1, 2, 1, 2, 1, 2]
print(a.index(2))
# 1

print(a.index(2, 3))
# 3

print(a.index(2, 2, 3))
# ValueError: 2 is not in list

inser(i, x)

• i 위치에 x를 삽입

queue = deque()
queue.append('b')
# queue = ['b']

queue.append('c')
# queue = ['b','c']

queue.insert(0, 'a')
# queue = ['a', 'b', 'c']

pop()

• 큐의 맨 오른쪽의 element를 삭제하고 반환
• element가 없으면, IndexError가 발생한다

queue = deque()
queue.append('b')
# queue = ['b']

queue.append('c')
# queue = ['b', 'c']

poped = queue.pop()
# poped = 'c'

popleft()

• 큐의 맨 왼쪽의 element를 삭제하고 반환
• element가 없으면, IndexError가 발생한다

queue = deque()
queue.append('b')
# queue = ['b']

queue.append('c')
# queue = ['b', 'c']

pop_left = queue.popleft()
# pop_left = 'b'

remove(value)

• 큐에 있는 value 값 중 처음으로 등장한 value를 삭제
• 못 찾으면 ValueError가 발생한다

queue = deque()
queue.append('b')
# queue = ['b']

queue.append('c')
# queue = ['b','c']

queue.append('b')
# queue = ['b', 'c', 'b']

queue.remove('b')
# queue = ['c', 'b']

reverse()

• 큐를 제자리에서 반대로 뒤집음
• 반환값은 없다

queue = deque()
queue.append('c')
# queue = ['c']

queue.append('b')
# queue = ['c', 'b']

queue.append('a')
# queue = ['c', 'b', 'a']

queue.reverse()
# queue = ['a', 'b', 'c']

rotate(n=1)

• n 만큼 오른쪽으로 회전
• n이 음수면 왼쪽으로 회전, 반환값은 없다. 양수면 오른쪽으로 회전

queue = deque()
queue.append('c')
# queue = ['c']

queue.append('b')
# queue = ['c', 'b']

queue.append('a')
# queue = ['c', 'b', 'a']

queue.rotate(1)
# queue = ['a', 'c', 'b']

queue.rotate(-1)
# queue = ['c', 'b', 'a']

maxlen

• 큐 생성시 정했던 큐의 최대 크기
• 정하지 않았다면 None 반환

# 최대 크기를 정했을 때

queue = deque('lft', 3)
print(queue)
# deque(['l', 'f', 't'], maxlen=3)

queue.append('b')
print(queue)
# deque(['f', 't', 'b'], maxlen=3)

queue.append('c')
print(queue)
# deque(['t', 'b', 'c'], maxlen=3)

queue.appendleft('a')
print(queue)
# deque(['a', 't', 'b'], maxlen=3)

print(deque.maxlen)
# 3

# 최대 크기를 정하지 않았을 때

queue = deque('lft', 3)
print(queue)
# deque(['l', 'f', 't'])

queue.append('b')
print(queue)
# deque(['l', 'f', 't', 'b'])

queue.append('c')
print(queue)
# deque(['l', 'f', 't', 'b', 'c'])

queue.appendleft('a')
print(queue)
# deque(['a', 'l', 'f', 't', 'b', 'c'])

print(queue.maxlen)
# None

---

https://docs.python.org/3/library/collections.html#collections.deque