[자료구조] 스택, 큐 구현 - 파이썬 deque

스택 구현

stack = []

stack.append(1)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(9)
stack.append(5)
stack.pop()

print(stack)  # [1, 2, 3, 9], 최하단(먼저 들어온) 원소부터 출력 
print(stack[::-1]) # [9, 3, 2, 1], 최상단(나중에 들어온) 원소부터 출력

파이썬의 스택은 별도의 라이브러리를 사용할 필요가 없다. 기본 리스트에서 append()와 pop() 메서드를 사용하면 스택 자료구조와 동일하게 동작한다. 만약 collections라이브러리 사용을 허용하지 않는 코딩 테스트라면 리스트로 간단하게 스택을 구현할 수 있다.

 

스택을 collections에서 제공하는 deque로 구현할 수도 있다. deque(양방향 큐)는 스택과 큐의 장점을 모두 채택한 것으로 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이다.(특히 큐를 구현할 때)대부분의 코딩 테스트에서 collections모듈과 같은 기본 라이브러리 사용을 허용한다.(예외도 있음)

 

from collections import deque

stack = deque()
stack.append(1)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(9)
stack.append(5)
stack.pop()

print(stack)  # deque([1, 2, 3, 9]), 최하단(먼저 들어온) 원소부터 출력
print(stack.reverse()) # 스택 뒤집기 None을 반환한다.
print(stack) # deque([9, 3, 2, 1]),뒤집힌 스택 출력

deque를 사용해도 리스트를 사용할 때 처럼 append()와 pop() 메서드를 사용하면 된다. 다만, 뒤집어서 출력할 때 인덱싱으로 뒤집는 건 불가능하다. reverse() 메서드를 사용하면 되는데 이 메서드는 값을 반환하지 않는 메서드이므로 메서드 사용 후 따로 stack을 출력해야 뒤집힌 값을 확인할 수 있다. 그리고 리스트도 이 함수를 똑같이 제공하므로 인덱싱 하지 않고 이 방법으로 값을 뒤집을 수 있다.

 

큐 구현

from collections import deque

queue = deque()
queue.append(1)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(9)
queue.append(5)
queue.popleft()

print(queue)  # deque([3, 7, 9, 5])
queue.reverse() #큐 뒤집기
print(queue) # deque([5, 9, 7, 3])

 

큐는 deque로 간단하게 구현이 가능한데 스택을 구현할 때와 거의 똑같다. 다만 pop() 대신 popleft()를 해줘야 하는데, popleft()를 해야 가장 먼저 들어온 원소를 뺄 수 있다.

 

deque확장하기

from collections import deque

deque = deque('name')
print(deque) # deque(['n', 'a', 'm', 'e'])
deque.extend('algo')
print(deque) # deque(['n', 'a', 'm', 'e', 'a', 'l', 'g', 'o'])
deque.extendleft('yM') # deque(['M', 'y', 'n', 'a', 'm', 'e', 'a', 'l', 'g', 'o'])
print(deque)

deque는 다음과 같이 append를 사용하지 않아도 확장해서 데이터를 넣을 수 있다. extend는 오른쪽으로 확장해서 데이터를 넣는데 extendleft를 하면 왼쪽으로 확장해서 데이터를 넣는다. 다만 왼쪽부터 값이 들어가기 때문에 예제처럼 순서에 유의해야 한다.

deque를 리스트처럼

deque는 리스트의 insert(), remove() 메서드를 사용할 수 있다. 또, 중간의 값을 인덱스를 사용해서 변경할 수도 있다. 다만, 시작점의 값이나 끝점 값을 빼는데 최적화된 자료구조이므로 중간 데이터의 값을 변경할 땐 리스트보다 느리다.

 

from collections import deque

deque = deque('name')
print(deque) # deque(['n', 'a', 'm', 'e'])
deque[2] = 'M'
print(deque) # deque(['n', 'a', 'M', 'e'])
deque.insert(2,'A') 
print(deque) # deque(['n', 'a', 'A', 'M', 'e'])
deque.remove('a')
print(deque) # deque(['n', 'A', 'M', 'e'])

---

deque 참고 블로그

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

Python - 데크(deque) 언제, 왜 사용해야 하는가?

https://daimhada.tistory.com/56

Python 내장 함수의 시간 복잡도

https://frhyme.github.io/python-lib/python_deque_is_faster_than_lst/

python - collections - deque가 list보다 항상 빠른가?