스택(Stack)과 큐(Queue) in Python

 

요즘 DFS와 BFS 알고리즘에 대하여 공부하고 있는데 이러한 알고리즘을 이해하기 앞서 

선행으로 알고있어야 하는 자료구조가 있는데 바로 스택(Stack)과 큐(Queue)이다.

 

스택과 큐는 파이썬뿐만 아니라 모든 프로그래밍 언어에서 기본적이고 중요한 자료구조 중 하나이고,

알고리즘을 위해서만이 아니라 여러가지 상황에서 효율적인 해결책을 제공한다.

 

스택과 큐는 기본적으로 데이터를 쌓는 구조에 대한 자료구조이고,

이 두 자료구조는 데이터를 삽입(Push)하는 과정과 삭제(Pop)하는 과정이 핵심이다.

때문에 오늘은 스택과 큐에 대해서 알아보겠다.

---

1. 스택 (Stack)

스택은 쌓다라는 말로 표현이 가능한데, 실제로 스택 자료구조는 박스를 쌓는것과 상당히 유사하다.

박스를 위로 쌓고 다시 내려놓는다고 가정하면 제일 마지막에 쌓은 박스를 가장 먼저 내려놓게 된다.

이처럼 선입후출 혹은 후입선출 구조로 되어있는 자료구조를 스택이라고 한다.

 

Python에서는 대표적으로 list 자료구조가 스택 자료구조이다.

list의 경우 마지막 index에 데이터를 삽입해주는 append() 함수와 마지막 index의 데이터를 제거해주는 pop() 메소드가 존재한다.

 

이를 Python 코드로 구현하자면 아래와 같다.

stack = []

stack.append(1)
stack.append(2)
stack.append(3)

stack.pop() # 3제거

stack.append(4)
stack.append(5)

stack.pop() # 5제거

print(stack) # [1,2,4]

 

이와 같이 스택은 데이터를 쌓고(push) 빼는(pop) 동작이 한쪽에서만 일어난다는 특징을 가지며

특별한 라이브러리를 사용할 필요 없이 list를 통해 구현할 수 있다.

---

2. 큐 (Queue)

스택이 한쪽에서만 데이터를 쌓고 빼는 동작이 일어난다면, 반대로 큐는 양방향으로 데이터를 쌓고 빼는 동작이 일어난다.

대표적으로 터널을 생각할 수 있다.

터널에는 차가 순서대로 들어가고 먼저 들어간 차가 먼저 터널을 통과해서 나온다.

큐는 터널처럼 양 방향 입,출구가 모두 뚫려 있는 구조로 인지하면 이해하기 편하다.

 

따라서 큐는 선입선출의 구조를 가지고 "공정한" 자료구조라고 비유된다고 한다.

 

Python에서 큐를 구현하기 위해서는 deque라는 모듈을 따로 사용해야한다.

아래는 Python 코드로 구현한 큐 자료구조이다.

from collecrions import deque

queue = deque()

queue.append(1)
queue.append(2)
queue.append(3)
queue.popleft() # 1 제거
queue.append(4)
queue.popleft() # 2 제거

print(queue) # deque([3,4])

---

이렇게 오늘은 스택(Stack)과 큐(Queue)에 대해 공부해보았다.

두 자료구조는 앞으로 공부해나갈 DFS와 BFS 알고리즘의 핵심에 해당하기 때문에 잘 이해하고 넘어가야겠다.