큐와 스택은 무엇인가

큐와 스택은 컴퓨터 과학에서 다루는 여러 가지 자료 구조 중에서도 가장 기본적인 것이다. 두 자료 구조는 '자료를 넣는 동작'과 '자료를 빼는 동작'을 할 수 있으며, 들어간 자료가 일렬로 보관된다는 공통점이 있다. 하지만 자료를 넣고 뺄 때 동작하는 방식이 서로 다르다.

큐(Queue)

---

큐는 '줄 서기'에 비유할 수 있다. 택시를 타기 위해서 줄을 서는 과정을 생각해보면 쉽다. 새로 택시 정류장에 도착한 사람은 맨 뒤로 가서 줄을 서고, 택시가 도착하면 그 줄의 맨 앞에 선 사람이 줄을 빠져나가 택시에 탄다. 가장 먼저 줄을 선 사람이 가장 먼저 택시를 타게 된다. 즉 FIFO ( First In First Out ) 선입선출 이라고 불리며, 프로세스 처리, CPU 관리에서 많이 사용된다.

큐에 자료를 한 개 집어넣는 동작을 '인큐(enqueue)'라고 부르고 큐 안에 있는 자료를 한 개 꺼내는 동작을 '디큐(dequeue)'라고 표현한다.

대기열 기다리는 게임 로스트 읍읍...

가장 쉽게 주변에서 예를 들자면 우선 순위가 필요한 대기열 같은 것이 있겠다. 리그 오브 레전드에서 랭크나 노말 게임을 할 때 우리는 '큐를 돌린다'라고 표현한다. 큐를 돌리면 대기열에 들어가고 먼저 대기열에 들어간 사람이 먼저 게임이 잡히게 되는 선입선출의 과정을 가진다.

리스트를 이용해 큐를 구현할 시에 디큐로 맨 앞자리를 날렸을 때 줄에 남은 사람들은 모두 한칸씩 앞으로 이동해야한다. 이렇게 메모리를 재사용하지 않고 다시 만들어서 사용해야한다. 그래서 속도 측면에서 단점을 가지고 있다.

Linear Queue(선형큐)는 이러한 문제점을 보완하기 위하여 Circular Queue(원형 큐)가 등장하게 된다. 원형 큐는 말그대로 선형적인 구조의 리스트가 아니라 원형의 형식으로 자료 구조를 갖는다. 한줄로 서있던 줄을 동그랗게 원형으로 세워놓은 셈이다. 원형 큐에서는 맨 앞의 메모리 공간을 디큐로 날리면 다시 날린 그 자리에 인큐를 하게 함으로써 낭비를 막는다.

스택(Stack)

---

스택은 '접시 또는 책 쌓기'에 비유할 수 있다. 다 먹은 접시를 쌓을 때는 쌓은 접시 맨 위에 올려놓는다. 설거지하려고 접시를 꺼낼 때도 맨 위에 있는 접시부터 꺼낸다. 가장 마지막에 들어간 자료를 가장 먼저 꺼낸다. 즉, 후입선출(Last In First Out) 이라고 불리며, 문서 작업에서 컨트롤 + z 와 같이 이전 상태로 되돌리기, 캐시같은 모습으로 우리 주변에서 쉽게 찾아볼 수 있다.

외우기 쉽지 않다면 탑을 쌓는 것, 나서스가 스택을 쌓는 것, 메자이 스택을 쌓는 것, 이렇게 스택과 함께 따라오는 말인 쌓는다라는 표현과 함께 기억하면 좋다. 쌓는 것은 위에서 부터 쌓아 올리고 덜어낼 때도 젠가가 아닌 이상 위에서 부터 하나씩 덜어낸다.

스택에 자료를 하나 집어넣는 동작을 '푸시(push)'라고 부르고 스택 안에 있는 자료를 하나 꺼내는 동작을 '팝(pop)'이라고 표현한다.