[Python] 덱(Deque) 사용 방법 정리

 

 

 

 

 

 

🌈 파이썬 덱(Deque) 사용 방법

덱(Deque)이란 double-ended queue를 줄여서 표현한 것으로 양방향으로 넣고 뺄 수 있다.

따라서 deque은 스택과 큐의 특성을 모두 갖고 있으며, 둘을 조합한 형태의 자료구조로 이해하면 된다.

 

* 리스트(List)에 비해 deque이 가지는 이점은 수행 속도이며, list는 O(n)의 속도 deque는 O(1)의 속도를 보인다. 

 

 

 

 

👨‍💻 deque의 메서드 정리

Method	Explanation
deque.append(item)	오른쪽 끝에 새로운 원소를 삽입한다.
deque.appendleft(item)	왼쪽 끝에 새로운 원소를 삽입한다.
deque.pop()	오른쪽 끝의 원소를 제거 후 반환한다.
deque.popleft()	왼쪽 끝의 원소를 제거 후 반환한다.
deque.extend(array)	주어진 array 배열을 순환하며 오른쪽에 추가한다
deque.extendleft(array)	주어진 array 배열을 순환하며 왼쪽에 추가한다.
deque.insert(n, item)	n번 index에 원소를 추가한다.
deque.remove(item)	입력한 원소를 삭제한다. 같은 원소가 있을 경우 왼쪽부터 삭제된다.
deque.rotate(n)	n만큼 원소의 위치를 회전한다. (양수 : 시계방향, 음수 : 반시계 방향)
deque.clear()	모든 원소를 제거한다.
deque.reverse()	원소의 위치를 좌우 반전시킨다.

 

 

 

 

1️⃣ 초기화

deque(iterable, [, maxlen])를 사용해 초기화한다.

from collections import deque

# 비어있는 큐 만들기
deque = deque()

# 원소가 있는 큐 만들기
deque = deque([1, 2, 3])

# 큐 최대 길이 명시하기(원소를 maxlen보다 더 많이 넣으면 maxlen이 자동 갱신됨)
deque = deque(maxlen=5)

 

 

 

 

2️⃣ append( ), appednleft( )

큐(Queue)는 선입선출로써 배열의 왼쪽(index 0)에 새로운 값이 입력되고, 오른쪽 끝의 값부터 반환한다.

따라서 덱(Deque)에서 왼쪽에 값을 입력할 때는 appendleft( ) 메서드를 사용한다.

 

- 왼쪽 끝에 새로운 값을 추가: appendleft()

- 오른쪽 끝에 새로운 값을 추가: append()

from collections import deque

deque = deque()
deque.append(3)
deque.append(6)
deque.append(9)
deque.append(12)
print(deque) # deque([3, 6, 9, 12])

deque = deque()
deque.appendleft(3)
deque.appendleft(6)
deque.appendleft(9)
deque.appendleft(12)
print(deque) # deque([12, 9, 6, 3])

 

 

 

 

3️⃣ pop( ), popleft( )

큐(Queue)는 선입선출로써 배열의 왼쪽(index 0)에 새로운 값이 입력되고, 오른쪽 끝의 값부터 반환한다.

따라서 덱(Deque)에서 왼쪽에 값을 출력할 때는 popleft() 메서드를 사용한다.

 

- 왼쪽 끝의 값을 반환: popleft()

- 오른쪽 끝의 값을 반환: pop()

from collections import deque

deque = deque([1,2,3])
while deque:
    print(deque.popleft())

# 1
# 2
# 3

deque = deque([1,2,3])
while deque:
    print(deque.pop())

# 3
# 2
# 1

 

 

 

 

4️⃣ extend( ), extendleft( )

왼쪽에 값을 추가할 때 주의해야 할 점은 밑의 예시와 같이 'maI'를 입력하였으나 'm'부터 값이 추가되어

결과는 역순으로 들어간 것처럼 보인다.

 

- 왼쪽 끝에 값을 추가: extendleft()

- 오른쪽 끝에 값을 추가: extend()

from collections import deque

deque = deque(['I','a', 'm'])
deque.extend('Jinny') # 오른쪽끝에 'J', 'i', 'n', 'n', 'y' 추가

deque = deque(['J', 'i', 'n', 'n', 'y'])
deque.extendleft('maI') # 왼쪽끝에 'I', 'a', 'm'  추가
deque(['I', 'a', 'm', 'J', 'i', 'n', 'n', 'y'])

 

 

 

 

5️⃣ insert( ), remove( )

덱(Deque)은 리스트처럼 중간에 값을 입력, 수정, 삭제할 수 있다.

새 항목을 입력하거나 기본 항목을 삭제할 때는 insert() 메서드와 remove() 메서드를 사용한다.

dq = deque('love')
dq.insert(0, 'K') # 첫번째 항목에 'K'를 추가
deque(['K', 'l', 'o', 'v', 'e'])         

dq.insert(100, 'K') # 100번째 항목(없으니까 가장 큰 쪽에)에 'K' 추가
deque(['K', 'l', 'o', 'v', 'e', 'K'])  
dq.remove('K') # 'K'항목 삭제

deque(['l', 'o', 'v', 'e', 'K']) # 같은 항목이 있을때 지우면 왼쪽부터 삭제됨.
dq.remove('K')
deque(['l', 'o', 'v', 'e']) # 오른쪽에 있는 'K'삭제

 

 

 

 

6️⃣ rotate( )

메서드에 음수 값을 넣게 된다면 왼쪽으로 회전하고, 양수 값을 전달할 시 오른쪽으로 회전한다.

from collections import deque

test = [1, 2, 3, 4, 5, 6, 7, 8, 9]
test = deque(test)
test.rotate(-2) # [8, 9, 1, 2, 3, 4, 5, 6, 7]

test = [1, 2, 3, 4, 5, 6, 7, 8, 9]
test = deque(test)
test.rotate(-2) # [3, 4, 5, 6, 7, 8, 9, 1, 2]

 

 

 

 

7️⃣ clear( )

덱에 있는 모든 원소를 제거한다.

from collections import deque

deque = deque([1,2,3]) # deque([1, 2, 3])
deque.clear() # deque([])