[자료구조] 스택(Stack)과 큐(Queue)

Stack과 Queue를 학습하기 전에

한 기업의 직무 면접에서 '스택과 큐를 비교해서 설명해주세요' 라는 질문을 받은 적이 있다. 직무 면접에서 자료구조 질문은 거의 '리스트와 셋, 맵을 비교하고 차이점을 중심으로 설명해주세요' 와 같은 질문은 많이 받았지만, 스택과 큐는 너무 쉽고 기초적인 내용이라서 그런가 단 한 번도 질문을 받은 적이 없었다. 그래서인지 순간적으로 LIFO, FIFO 개념에 혼동이 와 멘탈이 흔들렸던 기억이 있다(다행히 답변은 잘 했었음).

 

스택과 큐는 자료구조를 학습하면서 거의 초반부에 나오는 매우 심플한 자료구조이며, 비슷하면서도 다른 방식으로 동작하기 때문에 함께 묶이곤 한다. 오늘은 스택과 큐에 대해 학습하며 명쾌하게 이해해보도록 하자.

 

스택 (Stack)

스택은 배열, 리스트와 마찬가지로 데이터가 일렬로 늘어선 선형 자료구조이다. 하지만 스택만이 가지는 독특한 점은, 스택은 선형 자료구조의 한 쪽 끝에서만 데이터의 삽입과 삭제가 일어나는 자료구조라는 것이다.

스택

스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 자료구조이다. 개념적으로 보자면 스택은 쌓아올리는 개념으로 이해하는 것이 받아들이기 쉽다. 뷔페 접시를 예시로 들어보자. 우리는 접시 더미의 맨 아래 접시가 아니라 맨 위의 접시를 꺼내어 사용하고, 뷔페 알바생들은 새 접시를 접시 더미의 맨 아래에 두는 게 아니라 맨 위에 둔다. 그래서 스택을 '쌓아올리는 개념' 으로 이해하는 것이 받아들이기 쉽다고 한 것이다.

 

스택 자료구조에는 top이라고 하는 개념이 있다. 이는 데이터 더미의 최상단을 의미한다.

스택 push, pop, top 개념

스택에서의 삽입과 삭제를 push, pop이라고 하는데, push와 pop은 스택의 top에서만 이루어진다. 이러한 구조는 '나중에 삽입된 데이터가 먼저 삭제된다' 라는 특징을 갖게끔 하는데, 이를 우리말로는 후입선출, 영어로는 LIFO (Last In - First Out) 라고 한다. 스택에 가장 먼저 삽입된 데이터는 스택의 최하단에 위치하게 되고, 스택에서의 삽입과 삭제는 최상단인 top에서만 이루어지기 때문에 가장 먼저 삽입된 데이터가 가장 나중에 스택에서 빠져나오게 되고, 가장 나중에 삽입된 데이터가 가장 먼저 스택에서 빠져나오게 되는 것이다.

 

스택은 top에서만 데이터의 삽입(push), 삭제(pop)가 이루어지는 자료구조이다.

따라서 LIFO (Last In - First Out) 라는 특성을 가진다.

 

큐 (Queue)

큐 역시 배열, 리스트, 스택과 마찬가지로 데이터가 일렬로 늘어선 선형 자료구조이다. 하지만 큐가 배열, 리스트, 스택과 다른 차이점은 한 쪽 끝에서 데이터의 삽입이 이루어지고, 또다른 한 쪽 끝에서 데이터의 삭제가 이루어진다는 것이다.

큐

큐는 한 쪽 끝에서 자료를 넣고, 다른 한 쪽 끝에서 자료를 뺄 수 있는 자료구조이다. 개념적으로 보면 큐는 줄, 그러니까 대기열로 이해하는 것이 받아들이기 쉽다 (그래서 롤 할 때도 큐 잡는다는 말이 대기열에 참석해 게임 입장을 기다린다는 표현을 하는 ...). 요새 핫하다는 런던베이글에 줄을 선다고 생각해보자. 새로 도착한 손님은 줄의 맨 끝에 서야하고, 줄의 맨 앞 손님은 가장 먼저 매장에 입장할 수 있는 구조다. 그래서 큐를 줄 (대기열) 로 이해하는 것이 받아들이기 쉽다고 한 것이다.

 

큐 자료구조에는 front와 back이라고 하는 개념이 있다. 이는 자료구조의 맨 앞과 맨 뒤를 의미한다.

큐 enqueue, dequeue, front, back 개념

큐에서의 삽입과 삭제를 enqueue, dequeue라고 하는데, enqueue는 back에서, dequeue는 front에서만 이루어진다. 이러한 구조는 '먼저 삽입된 데이터가 먼저 삭제된다' 라는 특징을 갖게끔 하는데, 이를 우리말로는 선입선출, 영어로는 FIFO (First In - First Out) 라고 한다. 큐에 가장 먼저 삽입된 데이터는 큐의 front, 즉 맨 앞에 위치하게 되고, 큐에서의 삭제는 front에서 이루어지기 때문에 가장 먼저 삽입된 데이터가 가장 먼저 큐에서 빠져나오게 되고, 가장 나중에 삽입된 데이터가 가장 나중에 큐에서 빠져나오게 되는 것이다.

 

큐는 back에서만 데이터의 삽입(enqueue), front에서만 데이터의 삭제(dequeue)가 이루어지는 자료구조이다.

따라서 FIFO (First In - First Out) 라는 특성을 가진다.

 

마무리

사실 스택과 큐만큼 단순하고 명료한 자료구조가 또 있나 싶다. 스택과 큐는 아마 우리 일상의 모습을 본떠 만든 자료구조가 아닐까 ? 하는 생각을 포스트를 작성하며 순간적으로 해보기도 했다. 스택과 큐는 CS를 학습하면서, 프로세스의 메모리 구조 (스택) 라던가 스케줄링 기법 (큐) 과 같은 영역에서 종종 마주하곤 한다. 그만큼 개념적으로 근본이 되는 자료구조 중 하나인 것이다. 스택과 큐에 대한 개념을 단단히 다진다면 분명 학습에 큰 ... 도움이 될 것이라 생각한다.