Python(파이썬) 알고리즘 자료구조 기초 (스택, 큐)

---

자료구조(Data Structure)란 '데이터를 표현하고 관리하고 처리하기 위한 구조'이다.

오늘은 그중 기초인 스택과 큐에 대해 알아보자.

 

스택과 큐는 다음의 두 핵심적인 함수로 구성된다.

• 삽입(push) : 데이터를 삽입한다.
• 삭제(pop) : 데이터를 삭제한다.

이 외에도 오버플로(특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생)와

언더플로(특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행할 때 발생)도 고민해봐야 하는 문제이다.

 

스택

스택은 쉽게 도넛 쌓기에 비유할 수 있다. 도넛을 아래부터 차곡차곡 쌓는다고 하면 그 도넛을 먹을 때는 가장 위에 있는 도넛을 먹을 것이다. 이러한 구조를 선입 후출(First In Last Out)이라고 한다. 

 

큐

큐는 대기줄에 비유할 수 있다. 우리가 흔히 줄을 설 때 먼저 온 사람이 먼저 들어가게 된다. 이러한 구조를 선입 선출(First In First Out)이라고 한다.

 

 

이를 그림으로 표현하면 다음과 같다.

 

 

출처 http://russell.ballestrini.net

 

---

 

 

스택을 파이썬 코드로 표현하면 다음과 같다.

# 스택 구현 예제 
stack = []

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]) #최상단 원소부터 출력

파이썬에서 스택을 이용할 때는 별도의 라이브러리를 사용할 필요가 없다.

기본 리스트에서 append( ) 메서드는 리스트의 가장 뒤쪽에 데이터를 삽입하고 

pop( ) 메소드는 리스트의 가장 뒤쪽에서 데이터를 꺼내기 때문에 스택의 원리와 동일하게 작동한다.

 

 

---

 

 

다음으로 큐를 파이썬 코드로 표현하면 다음과 같다.

# 큐 구현 예제 , 파이썬에서 큐를 구현할 때는 덱을 이용한다.
from collections import deque
queue = deque()

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue) #먼저 들어온 순서대로 출력
queue.reverse()
print(queue) #나중에 들어온 순서대로 출력

파이썬에서 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용하면 좋다. 

deque는 스택과 큐의 장점을 모두 채택한 것인데 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이다.