[Python] Stack, Queue 기본, module 사용 정리

2 분 소요

🙆‍♂️ import 🙇‍♂️

[자료구조][파이썬/Python] 큐(Queue)[몽구의 우당탕탕 개발 공부]

Stack

Python에서 내장 Module에는 stack만을 지원하는 기능은 없지만, 기본 Python 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는 List를 이용해 구현할 경우 dequeue를 실행 할 때 시간 복잡도가 O(1)이 아닌 O(N)이 걸리는 문제가 발생한다.

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

 0x01    0x02     0x03

[  1  ] - [  2  ] - [  3  ]

 0x01    0x02    0x03

[Null] - [  2  ] - [  3  ]

 0x01    0x02    0x03

[  2  ] - [  3  ] - [  ?  ]

양방향 연결 리스트로 Queue를 구현하면 dequeue를 실행 할 때 시간 복잡도가 O(1)이 될 수 있지만, Queue 중간 요소를 수정, 삭제, 삽입하는 경우 List로 구현한 Queue가 더 성능이 뛰어나다.

그래서 Python 내장 Module로 Queue를 지원하는 Queue Module이 있지만, 이는 Thread환경을 위해 만들어져있어 일반적인 상황에서 사용은 권장되지 않는다.

그래서** 보통 Collections의 deque Module을 사용**한다.

collections.deque

collections.deque의 deque는 double ended queue의 약자로, 양방향 연결리스트(Doubly Linked List)로 구성되어 있다.

from collections import deque

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

# <class 'collections.deque'>

deque.append : enqueue 기능 수행

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 객체 append 연장

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

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]

Gillog