Stack(스택), Queue(큐) 자료구조 [이코테 - 나동빈]

DFS(깊이 우선 탐색), BFS(너비 우선 탐색) 알고리즘에 대하여 알기 전에 먼저 알아두어야 할 자료구조가 있다.

 

오늘의 주제인 Stack(스택), Queue(큐)이다.

 

두 주제를 알기전에 간단한 용어에 대하여 정리하자.

 

- Push(삽입) : 자료구조에 데이터를 삽입한다.

- Pop(삭제) : 자료구조에서 데이터를 삭제한다.

- Overflow(오버플로) : 스택, 큐와 같은 자료구조가 수용할 수 있는 데이터의 크기가 이미 가득찬 상태에서 삽입하려 할 때 발생한다.

- Underflow(언더플로) : Overflow와 반대로 데이터가 전혀 들어있지 않은데 데이터를 삭제하려 하려 할때 발생한다.

---

Stack(스택)

Stack은 그림과 같이 위에서 부터 차곡차곡 쌓아 놓는 형태 이다.

그래서 아래에 있는 데이터를 빼기 위해서는 반드시 위에 있는 자료부터 빼야 한다.

즉 선입후출(Fisrt In Last Out -FILO)구조 혹은 후입선출(Last In First Out)구조라고 한다.

#스택 예제
stack = []

stack.append(54)
stack.append(65)
stack.append(83)
stack.pop()
stack.append(57)

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

파이썬에서 Stack은 리스트에서 append()함수로 pop()함수로 동일하게 동작할 수 있다.

- append() : 가장 뒤쪽에 데이터를 삽입

- pop() :  가장 뒤쪽에 데이터를 삭제

두 가지 함수의 동작방식 때문에 가능하다.

---

Queue(큐)

큐는 Stack과는 다르게 선입선출(Fisrt In Fisrt Out)구조로 '공정한'자료구조라고 비유된다.

그림과 같이 먼저 들어간 데이터는 먼저 나가기 때문이다.

#큐 예제
#큐를 구현하기 위해는 deque 라이브러리 사용
from collections import deque
queue = deque()

queue.append(53) 
queue.append(37) 
queue.append(29) 
queue.popleft() 
queue.append(22)  

#출력
print(queue) #먼저 들어온 순서대로 출력

#다음 출력을 위해 역순으로 바꾸기
queue.reverse()
print(queue) #나중에 들어온 순서대로 출력

큐는 collections 모듈의 deque를 사용할 수 있다.

-append() : deque의 오른쪽 끝에 데이터를 삽입한다.

-appendleft() : deque의 왼쪽 끝에 데이터를 삽입한다.

-popleft() : deque의 왼쪽 끝에 데이터를 제거한다.

-pop() : 오른쪽 끝에 데이터를 제거

두 함수를 사용하여 큐를 만들 수있고, 함수를 적절하게 이용하면 스택도 사용할 수 있다.

- deque는 스택과 큐의 장점을 모두 채택하였으며 queue 라이브러리를 이용하는 것보다 간단하다.

- 리스트 자료형에 비하여 속도도 빠르다.