Python으로 스택(stack), 큐(queue) 자료구조 구현하기

 

 

 

 

기본적인 자료구조인 스택, 큐를 python으로 구현하는 방법을 정리해보려 한다.

 

 

스택(stack) :

- 먼저 들어온 것이 나중에 나가는 자료구조

- 선입후출(FILO: First In Last Out)

- 박스쌓기로 기억 (먼저 쌓은 박스가 가장 아래에 위치)

- 단순한 list method(append, pop) 사용으로 구현!

 

 

Python으로 스택(stack) 구현

stack = []

stack.append(5)	# 각 연산 시간복잡도 O(1)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop(5)

print(stack)	# 최하단 원소부터 출력, [5, 2, 3, 1]
print(stack[::-1])	# 최상단 원소부터 출력, [1, 3, 2, 5]

위에 있는 그림처럼, 오른쪽에서 왼쪽으로 들어가는 기다란 관을 떠올리면 연상이 쉽다.

 

 

 

 

큐(queue) :

- 먼저 들어온 것이 먼저 나가는 자료구조

- 선입선출(FIFO: First In First Out)

- 입구와 출구가 뚫려있는 터널로 기억 (또는 리그오브레전드 큐(대기열) ㅋㅋ)

- collections 라이브러리의 'deque' 모듈을 사용하여 구현!

 

 

 

Python으로 큐(queue) 구현

from collections import deque

queue = deque()

queue.appned(5)	# 각 연산 시간복잡도 O(1)
queue.appned(2)
queue.appned(3)
queue.appned(7)
queue.popleft()
queue.appned(1)
queue.appned(4)
queue.popleft()

print(queue)	# 먼저 들어온 순서대로 출력, deque([3, 7, 1, 4])
queue.reverse()
print(queue)	# 나중에 들어온 순서대로 나열, deque([4, 1, 7, 3])

(reverse를 하지 않은 기준으로)

오른쪽에서 왼쪽으로 향하는 터널을 생각하면 연상이 쉽다.

 

단순 리스트로 큐를 구현하게 되면,

pop() 메서드에 index를 입력하고,

해당 인덱스 값을 반환한 후 조정하는 과정에서

O(k)의 시간복잡도가 발생하므로,

큐는 deque 모듈을 사용하는 것이 좋다.

 

 

 

 

 

 

 

참고 자료 :

https://www.youtube.com/watch?v=7C9RgOcvkvo