[Python] 스텍, 큐, 덱(Stack, Queue, Deque) module 사용 정리

스택 Stack

Python에서 내장 Module에는 Stack만을 지원하는 기능은 없지만, 기본 List 자료구조를 이용하면 아주 간단하게 Stack을 사용할 수 있습니다.

stack = [0, 1, 2]

print(stack)

stack.append(3)

print(stack)

stack.pop()

print(stack)

'''
[0, 1, 2]
[0, 1, 2, 3]
[0, 1, 2]
'''

---

큐 Queue

Python에서 Queue는  dequeue로 구현하면 시간 복잡도가 O(1)이 걸리지만 List로 구현하면 O(N)이 걸립니다.

 

아래와 같이 앞에서 추출한 데이터의 주소에 이전 데이터들을 이전하는 작업이 동반되어 시간 복잡도가 증가하는 것입니다.

양방향 연결 리스트(Deque)로 Deque를 구현하면 Deque를 실행할 때 시간 복잡도가 O(1)이 될 수 있습니다.

하지만, Queue 중간 요소를 수정, 삭제, 삽입하는 경우 List로 구현한 Queue가 더 성능이 뛰어납니다.

 

그래서 파이썬 내장 Queue 모듈이 있지만, 이것은 Thread 환경을 위해 만들어 져 있어서 일반적인 상황에서 사용은 권장되지 않습니다.

 

그래서 보통 Collections의 deque 모듈을 사용합니다.

 

덱 Deque

collections.deque의 deque는 양방향 연결리스트로 구성되어 있습니다.

from collections import deque

d = deque()
print(type(d))

# <class 'collections.deque'>

 

deque.append : 오른쪽에 데이터를 삽입

from collections import deque

d = deque()

for i in range(5):
    d.append(i)
print(d)

# deque([0, 1, 2, 3, 4])

 

deque.appendleft : 왼쪽에 데이터 삽입

from collections import deque

d = deque()
for i in range(5):
    d.append(i)

d.appendleft(10)
print(d)

# deque([10, 0, 1, 2, 3, 4])

 

deque.insert : Queue 중간에 데이터 삽입

from collections import deque

d = deque()
for i in range(5):
    d.append(i)

d.insert(4, 11)
print(d)

# deque([0, 1, 2, 3, 11, 4])

 

deque.extend, deque.extendleft : Queue 오른쪽, 왼쪽에 iterable 객체  연장

from collections import deque

d = deque()
for i in range(5):
    d.append(i)
    
d.extend([0, 0, 0])
print(d)
d.extendleft([0, 0, 0])
print(d)

# deque([0, 1, 2, 3, 11, 4, 0, 0, 0])
# deque([0, 0, 0, 0, 1, 2, 3, 11, 4, 0, 0, 0])

 

deque.popleft : 왼쪽 데이터 제거 후 return

from collections import deque

d = deque()
for i in range(5):
    d.append(i)

print(d.popleft())

# 0

 

deque.pop : 오른쪽 데이터 제거 후 return

from collections import deque

d = deque()
for i in range(5):
    d.append(i)

print(d.pop())

# 4

 

deque.index : 특정 값의 인덱스를 반환

from collections import deque

d = deque()
for i in range(5):
    d.append(i)

print(d.index(1))

# 1

 

deque.remove : 지정 값을 큐에서 삭제

from collections import deque

d = deque()
for i in range(5):
    d.append(i)

d.remove(1)
print(d)

# deque([0, 2, 3, 4])

 

deque.reverse : 큐 내용 반전

from collections import deque

d = deque()
for i in range(5):
    d.append(i)

d.reverse()
print(d)

# deque([4, 3, 2, 1, 0])

 

 

deque.rotate() : 맨 뒤의 값을 pop한 후 앞에 삽입

from collections import deque

d = deque()
for i in range(5):
    d.append(i)

d.rotate()
print(d)

# deque([4, 0, 1, 2, 3])

 

deque.rotate(-1) : 맨 앞의 값을 pop한 후 앞에 삽입

from collections import deque

d = deque()
for i in range(5):
    d.append(i)

d.rotate(-1)
print(d)

# deque([1, 2, 3, 4, 0])

 

 

list(deque) : deque 역시 list로 사용할 수 있다.

from collections import deque

d = deque()
for i in range(5):
    d.append(i)

list(d)

print(d)

# [0, 1, 2, 3, 4]