[자료구조] 스택(Stack)과 큐(Queue) 파이썬으로 구현하기

스택(Stack)과 큐(Queue)는 데이터를 임시 저장하기 위해 사용하는 자료구조이며, 데이터를 입력하고 출력하는 방향이 정해져 있다는 점이 서로 비슷하다. 

 

스택(Stack)

스택은 선입후출(FILO) 방식을 따르는 자료구조이다. 선입후출(FILO)은 First In , Last Out   말그대로 먼저 들어온 데이터가 나중에 나가는 방식인데 박스 쌓기에 비유할 수 있다. 흔히 박스는 아래에서부터 위로 차곡차곡 쌓고 박스를 치울 때는 위에 있는 박스부터 내리는 것과 같다. 

 

파이썬에서 스택을 이용할 때는 별도의 라이브러리를 사용할 필요가 없이 리스트 자료형을 사용하여 스택을 구현한다.

append() 메소드는 리스트의 가장 뒤쪽에 데이터를 삽입하고, pop() 메소드는 리스트의 가장 뒤쪽에서 데이터를 꺼내기 때문이다.

 

stack = []

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

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

 

큐(Queue)

큐는 선입선출(FIFO) 방식을 따르는 자료구조이다. 선입선출(FIFO)은 First In, First Out 말그대로 먼저 들어온 데이터가 먼저 나가는 방식인데 대기 줄에 비유할 수 있다. 흔히 우리가 놀이기구 줄을 설 때 먼저 온 사람이 먼저 타는 것과 같다.

 

파이썬에서 큐를 이용할 때는 3가지 방법으로 구현이 가능하다.

 

1. 리스트 자료형 사용

리스트를 사용하면 큐에 데이터를 넣는 enqueue를 append() 메소드, 데이터를 빼는 dequeue를 pop(0)로 구현할 수 있다.

다만 리스트의 pop(0)은 O(n)의 시간복잡도를 가지기 때문에 큐를 구현할 때는 더 효율적인 방법을 사용한다. 

 

2. Queue 사용

queue 모듈의 Queue는 데이터를 단방향에서 추가하고 제거할 수 있는 자료구조이다. 

enqueue를 위해서는 put() 메소드를 , dequeue를 위해서는 get() 메소드를 사용한다.

get() 메소드는 리스트의 pop()과 다르게 시간복잡도가 O(1)이므로 리스트보다 더 효율이 좋다.

 

3. deque 클래스 사용

collections 모듈의 deque는 double - ended queue의 약자로 데이터를 양방향에서 추가하고 제거할 수 있는 자료구조이다.

deque는 양방향이기 때문에 append(), pop()과 더불어 appendleft(), popleft() 메소드가 있어 각각 맨 앞에 데이터를 삽입하거나 맨 앞에서 제거할 수 있다. appendleft(), popleft() 메소드는 각각 시간복잡도가 O(1)이기 때문에 리스트보다 더 효율적이다.

 

일반적으로는 양방향을 지원하고 효율이 좋은 deque를 이용하여 큐를 구현한다.

 

from collections import deque

queue = deque()
# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue)

 

---

참고자료: 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 지음(한빛미디어)