[자료구조] 스택(Stack)과 큐(Queue) - 파이썬(Python)

스택(Stack)

• 나중에 넣은 데이터를 먼저 빼는 후입선출(LIFO - Last In First Out) 구조
• ex) 박스 쌓기, 트럭에 물건 넣기
• 파이썬 기본 리스트에서 append()와 pop() 메서드를 사용하여 구현

스택 자료구조

stack = []

stack.append(1) # stack: [1]
stack.append(2) # stack: [1, 2]
stack.append(3) # stack: [1, 2, 3]
stack.append(4) # stack: [1, 2, 3, 4]

stack.pop() # stack: [1, 2, 3]
stack.pop() # stack: [1, 2]
stack.append(3) # stack: [1, 2, 3]
stack.pop() # stack: [1, 2]

 

 

 

큐(Queue)

• 먼저 넣은 데이터를 먼저 빼는 선입선출(FIFO - First In First Out) 구조
•  ex) 입장 대기줄
• 파이썬 collections 모듈에서 제공하는 deque 자료구조를 사용하여 구현

※ deque는 스택과 큐의 장점을 모두 채택한 자료구조로 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 사용하는 것보다 간단하다.

큐 자료구조

from collections import deque

queue = deque()

queue.append(1) # queue: [1]
queue.append(2) # queue: [1, 2]
queue.append(3) # queue: [1, 2, 3]
queue.append(4) # queue: [1, 2, 3, 4]

queue.popleft() # queue: [2, 3, 4]
queue.popleft() # queue: [3, 4]
queue.append(5) # queue: [3, 4, 5]
queue.popleft() # queue: [4, 5]