스택(Stack)과 큐(Queue)

탐색 - 많은 양의 데이터 중 원하는 데이터를 찾는 것

 

DFS와 BFS를 제대로 이해하려면 기본 자료구조인 스택과 큐에 대해 이해가 뒷받침 되어 있어야 한다.

 

자료구조 - 데이터를 표현하고 관리하고 처리하기 위한 구조

 

스택과 큐는 자료구조의 기초 개념이며 두개의 핵심적인 함수로 구성된다.

• 삽입(Push) : 데이터를 삽입한다.
• 삭제(Pop) : 데이터를 삭제한다.

참고:

오버플로 : 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할때 발생(저장공간을 벗어나 데이터가 넘쳐흐를 때 발생)

언더플로 : 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 데이터가 전혀 없는 상태

 

스택(Stack)

스택은 박스 쌓기에 비유할 수 있다. 박스는 아래에서 위로부터 쌓는다 박스를 치우기 위해서는 위에있는 박스를 먼저 내려야 한다. 이러한 구조를 선입후출(First In Last Out)구조 또는 후입 선출(Last In First Out)구조라고 한다.

ex) 설거지를 할 때 접시를 밑에서 부터 위로 쌓고 설거지를 할때는 위에 쌓인 접시부터 닦는다.

 

파이썬에서 스택을 이용할 때에는 별도의 라이브러리 사용을 하지 않고 기본 리스트의 메서드인 append()와 pop() 메서드를 이용하면 스택 자료구조와 동일하게 동작한다.

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

pop() 메서드는 리스트의 가장 뒤쪽에서 데이터를 꺼내옴

 

큐(Queue)

큐는 대기 줄에 비유할 수 있다. 드라이브 스루(Drive-thru)를 이용하게 되면 먼저 줄은 선 차량이 먼저 주문을 받고 먼저 나가게 된다. 이러한 구조를 선입선출(First In First Out)구조라고 한다.

 

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

deque 라이브러리는 스택과 큐의 장점을 모두 채택했으며 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이면서 queue 라이브러리를 이용하는 것 보다 더 간단하게 사용할 수 있다.