스택과 큐 (Stack and Queue)

한 줄 정의: 스택은 나중에 넣은 자료를 먼저 꺼내는(LIFO) 자료구조이고, 큐는 먼저 넣은 자료를 먼저 꺼내는(FIFO) 자료구조입니다.

쉽게 풀면

스택은 식당에서 쌓아둔 접시 더미와 같습니다. 접시를 씻어서 맨 위에 하나씩 올려두고(넣기), 쓸 때도 맨 위에 있는 것부터 가져다 씁니다(꺼내기). 즉 가장 나중에 넣은 것이 가장 먼저 나옵니다. 반면 큐는 매표소 줄서기와 같습니다. 먼저 줄을 선 사람이 먼저 표를 사고 나가며, 새로 온 사람은 줄 맨 뒤에 서야 합니다. 즉 가장 먼저 들어온 것이 가장 먼저 나옵니다. 이 두 자료구조는 데이터를 "어떤 순서로 넣고 뺄지"를 규칙화한 것으로, 프로그램 안에서 데이터를 임시로 저장하고 관리할 때 널리 쓰입니다.

왜 중요한가

스택과 큐는 컴퓨터과학에서 가장 기본적인 자료구조이면서도, 탐색 알고리즘, 컴파일러의 구문 분석, 운영체제의 작업 스케줄링, 네트워크 패킷 처리 등 훨씬 복잡한 시스템의 밑바탕을 이룹니다. 논문에서 새로운 알고리즘이나 시스템을 제안할 때, 내부 동작을 설명하는 과정에서 "이 부분은 스택으로, 저 부분은 큐로 처리한다"는 식으로 구조를 명시하는 경우가 많아, 이 개념을 정확히 이해하지 못하면 알고리즘의 시간 복잡도나 처리 순서를 제대로 따라가기 어렵습니다.

논문에서는 이렇게 쓰입니다

"깊이 우선 탐색(DFS)은 스택(stack) 구조를, 너비 우선 탐색(BFS)은 큐(queue) 구조를 이용해 방문할 노드의 순서를 관리한다."

이 문장은 그래프나 트리를 탐색하는 알고리즘이 내부적으로 어떤 자료구조를 사용해 "다음에 방문할 노드"의 순서를 정하는지를 설명하고 있습니다. 자료구조와 알고리즘을 다루는 논문의 배경 설명에서 이런 식으로 스택과 큐가 함께 언급되는 경우가 많습니다.

"제안하는 컴파일러의 구문 분석기는 연산자 우선순위를 처리하기 위해 스택(stack)에 토큰을 push하고, 규칙에 맞는 조건이 만족되면 pop하여 축약(reduce)한다."

프로그래밍 언어와 컴파일러 분야의 논문에서는 구문 분석 과정에서 스택을 활용해 토큰의 순서와 우선순위를 관리하는 방식을 설명할 때 이런 표현이 자주 등장합니다.

"네트워크 시뮬레이션에서 각 라우터는 도착한 패킷을 큐(queue)에 저장하고 선입선출(FIFO) 방식으로 순차 전송함으로써 처리 지연을 모델링하였다."

네트워크나 시스템 시뮬레이션 논문에서는 자원 경쟁이나 처리 지연을 표현하기 위해 큐를 활용한 대기열 모델을 제시하는 경우가 흔합니다.

조금 더 깊게 보면

스택과 큐는 배열이나 연결 리스트로 구현할 수 있으며, 어떤 방식을 택하느냐에 따라 삽입·삭제 연산의 효율이 달라질 수 있습니다. 큐를 변형한 구조로는 양쪽 끝에서 삽입과 삭제가 모두 가능한 덱(deque), 우선순위에 따라 꺼내는 순서가 정해지는 우선순위 큐(priority queue) 등이 있으며, 이런 변형들은 알고리즘 논문에서 상황에 맞게 선택적으로 사용됩니다. 또한 재귀 호출이나 함수 호출 정보를 관리하는 콜 스택(call stack)처럼, 스택과 큐의 개념은 프로그래밍 언어의 실행 모델을 이해하는 데도 이어집니다.

주의할 점

스택과 큐는 이름이 비슷해 보여도 데이터가 나오는 순서가 정반대라는 점을 혼동하면 안 됩니다. 또한 함수가 자기 자신을 호출하는 재귀 호출도 내부적으로는 스택 구조로 호출 정보를 쌓아 처리되므로, 제어구조의 반복을 재귀로 구현할 때 이 원리를 함께 이해해두면 좋습니다.