[Data Structure] 스택(Stack) / 큐(Queue)

스택(Stack) / 큐(Queue)

스택과 큐는 모두 데이터를 임시 저장할 때 사용하는 자료구조이다.

 

깃허브

스택: https://github.com/PSLeon24/DataStructure-Algorithms/blob/main/%5BData%20Structure%5D%20Stack.ipynb

큐: https://github.com/PSLeon24/DataStructure-Algorithms/blob/main/%5BData%20Structure%5D%20Queue.ipynb

 

스택(Stack)

먼저, 스택은 가장 마지막에 들어온 값이 가장 먼저 나가는 후입선출(LIFO: Last In First Out) 구조로서 예로는 함수의 호출과 반환하는 과정이 있다. 예시로는 프링글스를 생각해보자.

스택에 데이터를 넣는 작업을 푸시(push)라고 하며, 스택에서 데이터를 꺼내는 작업을 팝(pop)이라 한다. 그리고 푸시하고 팝이 이루어지는 스택의 맨 윗부분이 탑(top)이고 아랫부분은 바텀(bottom)이다.

 

큐(Queue)

하지만 스택과는 다르게 가장 먼저 넣은 데이터가 가장 먼저 꺼내지는 선입선출(FIFO: First In First Out) 구조로서 예로는 은행에서 줄을 서 먼저 표를 뽑은 사람부터 은행 업무를 처리하는 것이 큐의 예시에 해당한다. 큐에서 데이터를 추가하는 작업은 인큐(enqueue)라고 하고 꺼내는 작업을 디큐(dequeue)라고 한다. 또 데이터가 나오는 쪽은 프런트(front), 넣는 쪽이 리어(rear)이다.

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

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

 

스택의 경우 데이터가 추가되고 꺼내지는 곳이 탑 밖에 없기 때문에 데이터의 추가 및 삭제 시 탑의 값만 1씩 증가되거나 감소된다. 하지만 큐의 경우 데이터가 추가될 때는 리어값이 1 증가하고 삭제될 때는 프런트값이 1 증가된다.

 

큐 자료구조에 인큐와 디큐를 반복하다 보면 정해져 있는 큐의 크기를 초과하게 되는데 이렇게 큐의 용량이 가득 차면 더 이상 자료를 추가할 수 없게 된다.

 

이를 극복하기 위해 링 버퍼(원형 큐) 등장

 

링 버퍼: 가장 마지막에 저장된 자료 다음에는 가장 처음에 저장된 자료가 오게 되어있는 구조