덱은 double-ended-queue의 약어이다. 스택은 top에서 입, 출력을 하고, 큐는 rear에서 입력, front에서 출력하는 것과 달리, 덱은 front와 rear 양쪽에서 데이터 입, 출력이 가능하다.
파이썬에서는 collections 모듈에서 덱을 제공하고 있어서 직접 덱을 구현할 필요 없이 바로 사용 가능하다.
코드 출처: 파이썬으로 배우는 자료 구조 핵심 원리 - 양태환
from collections import deque
print('*' * 20 + 'Stack' + '*' * 20)
stack = deque()
for i in range(1, 6):
stack.append(i)
print(stack)
for i in range(5):
print(stack.pop())
print('*' * 20 + 'Queue' + '*' * 20)
queue = deque()
for i in range(1, 6):
queue.append(i)
print(queue)
for i in range(5):
print(queue.popleft())
deque의 rear에 데이터를 입력할 때는 append()를 호출하지만, front에 입력할 때는 appendleft()를 호출한다.
또한, rear에서 데이터를 출력할 때는 pop()을 호출하지만, front에서 출력할 때는 popleft()를 호출한다.
이렇게 덱으로 스택과 큐의 특징을 모두 구현할 수 있다.
파이썬에 구현된 deque는 이중 연결 리스트를 이용해서 구현한 것이라 양 끝에 있는 데이터에 접근하는 것은 O(1)이지만, 중간에 위치한 데이터에 접근하는 것은 O(n)이다.
Reference
파이썬으로 배우는 자료 구조 핵심 원리 - 양태환
'Data Structure' 카테고리의 다른 글
[파이썬(Python)] 이진 트리(Binary Tree) (0) | 2023.02.16 |
---|---|
[파이썬(Python)] 트리(Tree) (0) | 2023.02.16 |
[파이썬(Python)] 큐(Queue) (0) | 2023.02.15 |
[파이썬(Python)] 스택(Stack) (0) | 2023.02.15 |
[파이썬(Python)] 연결 리스트(Linked List) (0) | 2023.02.15 |
댓글