[Python] 데크(Deque) 개념과 활용

데크(Deque)란?

큐(queue)는 선입선출(FIFO) 방식으로 작동하며, 스택(Stack)은 후입선출(LIFO) 방식으로 작동한다. 큐와 스택이 합쳐져 양방향에서 Push와 Pop을 할 수 있는 자료구조가 데크(Deque)이다. 앞, 뒤 방향에서 요소(element)를 추가하거나 제거할 수 있다. 큐와 스택은 반대쪽에 존재하는 요소를 Pop 하려면 O(n)의 시간이 필요하지만, 데크를 사용하면 어느 방향이든 O(1)의 시간으로 연산을 수행할 수 있다.

스택(Stack)과 큐(Queue) 작동 방식

데크(Deque) 작동 방식

파이썬 라이브러리 deque

파이썬에서는 데크를 라이브러리로 사용할 수 있다. 아래의 공식문서에서 자세한 설명과 예시를 확인해 볼 수 있다. 여기에는 알고리즘 문제를 해결할 때 필요한 연산을 정리하려고 한다.

collections — Container datatypes

deque 선언

from collections import deque

deq = deque()

deque 연산

# 왼쪽에 요소 추가
deq.appendleft(10)

# 오른쪽에 요소 추가
deq.append(0)

# 왼쪽 요소 제거 및 반환
deq.popleft()

# 오른쪽 요소 제거 및 반환
deq.pop()

# 해당 인덱스에 요소 삽입
deq.insert(3)

# 해당 요소를 찾아 삭제
deq.remove(30)

deque 인덱스 접근

데크도 리스트처럼 인덱스로 접근과 값 변경이 가능하다.

q = deque('hello')
q[2] = 'o'
print(q)

# result
>> deque(['h', 'e', 'o', 'l', 'o'])

Reference

https://velog.io/@dltmdrl1244/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EB%9D%BC%EC%9D%B4%EB%B8%8C%EB%9F%AC%EB%A6%AC-deque

https://velog.io/@oeueoo/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Stack-Queue

https://chaewonkong.github.io/posts/python-deque.html