코딩테스트 필수 자료구조: 스택, 큐, 그리고 힙(Priority Queue) 완벽 정리

알고리즘의 논리를 다 깨우쳤다 해도 막상 구현에 들어가면 어떤 바구니에 데이터를 담아야 할지 막막할 때가 많죠. 사실 이 부분이 가장 번거로우시죠? 개념은 알겠는데 큐를 써야 할지, 우선순위 큐를 써야 할지 판단하는 게 생각보다 까다롭거든요. 막상 찾아보면 FIFO니 LIFO니 용어가 너무 어려운데요. 오늘은 복잡한 이론은 걷어내고, 2026년 실전 코딩테스트에서 바로 써먹을 수 있는 핵심 자료구조 3종 세트를 아주 쉽게 풀어보겠습니다.
 
저도 처음 공부할 때는 그냥 리스트(List)만 쓰면 다 해결되는 것 아닌가 싶어 고집을 부렸던 기억이 나요. 하지만 데이터가 10만 개, 100만 개로 늘어나면 자료구조 하나 잘못 선택한 대가로 '시간 초과'의 쓴맛을 보게 됩니다. 적재적소에 맞는 도구를 꺼내는 법, 지금 바로 확인해 보시죠.

차곡차곡 쌓고 뒤집기: 스택(Stack)

스택은 마치 '프링글스 통'이나 '쌓여있는 접시'와 같습니다. 가장 마지막에 넣은 감자칩을 가장 먼저 먹어야 하고, 맨 아래에 있는 접시를 꺼내려면 위에 있는 것들을 다 치워야 하죠. 이런 특징 때문에 되돌리기(Ctrl+Z)나 괄호 짝 맞추기 문제에서 단골로 등장합니다.

• 개요: 한쪽 끝에서만 자료를 넣고 뺄 수 있는 후입선출(LIFO) 구조입니다.
• 조건: 데이터의 삽입과 삭제가 빈번하며, 가장 최근에 들어온 데이터의 정보가 중요할 때 사용합니다.
• 주요 활용: 깊이 우선 탐색(DFS), 역순 문자열 만들기, 실행 취소 등.

개인적으로 이 부분이 가장 핵심이라고 생각합니다. 스택 문제를 풀 때 가장 많이 하는 실수가 '비어있는 스택'에서 데이터를 꺼내려고 하는 거예요. 솔직히 말씀드리면, 실전에서 에러가 나면 십중팔구는 스택이 비었는지 확인하는 조건문을 빼먹었을 때입니다. 파이썬이라면 단순히 리스트의 append와 pop만으로도 훌륭한 스택을 만들 수 있습니다.

줄 서서 기다리기: 큐(Queue)

큐는 '맛집 웨이팅 줄'이나 '터널'을 떠올리면 쉽습니다. 먼저 온 사람이 먼저 들어가는 아주 공평한 구조죠. 코딩테스트에서는 순서대로 업무를 처리해야 하거나, 특정 지점에서 퍼져 나가는 탐색을 할 때 필수적입니다.

• 개요: 한쪽에서는 넣고 반대쪽에서는 빼는 선입선출(FIFO) 구조입니다.
• 조건: 순서가 보장되어야 하는 작업 예약이나 네트워크 패킷 처리 등에 쓰입니다.
• 주요 활용: 너비 우선 탐색(BFS), 프로세스 관리, 캐시(Cache) 구현 등.

이건 모르면 손해 보는 꿀팁인데, 파이썬 유저라면 일반 리스트로 큐를 흉내 내지 마세요. list.pop(0)은 시간 복잡도가 $O(N)$이라 데이터가 많아지면 엄청나게 느려집니다. 반드시 collections.deque를 사용해야 $O(1)$의 속도를 보장받을 수 있어요. 이건 실력 차이가 아니라 도구의 차이입니다.

자료구조	입출력 방식	파이썬 추천 라이브러리	실전 핵심 용도
스택(Stack)	LIFO (후입선출)	list	DFS, 재귀, 괄호 검사
큐(Queue)	FIFO (선입선출)	collections.deque	BFS, 순차 처리
힙(Heap)	우선순위 기반	heapq	최솟값/최댓값 즉시 추출

급한 사람 먼저!: 우선순위 큐와 힙(Heap)

모든 데이터가 줄 선 순서대로 처리되지는 않죠? 응급실처럼 '가장 급한 사람'부터 처리해야 할 때가 있습니다. 이때 사용하는 게 힙입니다. 넣은 순서와 상관없이 우리가 정한 기준(작은 값 혹은 큰 값)에 따라 가장 우선순위가 높은 녀석이 튀어나옵니다.

• 개요: 완전 이진트리를 기반으로 하며, 최댓값이나 최솟값을 빠르게 찾기 위해 고안되었습니다.
• 주의사항: 힙은 전체를 정렬해주지 않습니다. 오직 '루트 노드'에 최우선 데이터가 있는 것뿐이에요. 전체 정렬이 필요하다면 그냥 .sort()를 쓰는 게 맞습니다.
• 팁: 파이썬의 heapq는 최소 힙(Min-Heap) 기준입니다. 최대 힙이 필요하다면 값에 마이너스(-)를 붙여서 넣었다가 뺄 때 다시 마이너스를 붙이는 기술이 필요하죠.

저도 처음엔 헷갈렸던 부분인데, 힙에 데이터를 넣고 뺄 때마다 내부적으로 트리가 재구성됩니다. 이 과정의 시간 복잡도는 $O(\log N)$이에요. 즉, 아무리 많은 데이터가 있어도 최솟값을 찾는 데 눈 깜짝할 새면 충분하다는 뜻입니다. 하지만 힙을 남용해서 매번 모든 데이터를 다 정렬하려고 하면 오히려 프로그램이 무거워질 수 있으니 조심해야 합니다.

실전에서 흔히 하는 실수와 대처법

이 자료구조들이 무조건 정답은 아닙니다. 상황에 맞지 않게 쓰면 오히려 코드가 복잡해지고 속도가 느려지는 역효과가 날 수 있어요.

• 스택의 함정: 재귀 함수가 너무 깊어지면 스택 오버플로우가 발생합니다. 2026년 기준 대부분의 온라인 저지는 스택 제한을 넉넉히 주지만, 여전히 직접 스택을 구현해서 푸는 게 안전할 때가 있습니다.
• 힙의 함정: 중간에 있는 데이터를 삭제하거나 검색해야 한다면 힙은 최악의 선택입니다. 힙은 오직 '맨 위'만 쳐다보는 녀석이니까요. 이런 상황에선 해시(Hash)나 균형 이진 탐색 트리를 고려해야 합니다.
• 최신 기준: 최근 카카오나 현대자동차 등 주요 기업 코테 분석 자료에 따르면, 자료구조 2개를 혼합해서 쓰는(예: 큐 안에 힙을 넣는 등) 변형 문제가 자주 출제되고 있습니다. 기본기를 익혔다면 반드시 응용 문제를 풀어보세요.

솔직히 말씀드리면, 자료구조 선택의 8할은 "데이터의 크기"를 보는 눈에서 결정됩니다. 문제에서 주어진 N의 범위를 보고 "아, 이건 매번 정렬하면 안 되겠구나, 힙을 써야겠네"라고 판단하는 흐름이 중요해요. 여러분은 문제를 읽자마자 어떤 바구니를 꺼낼지 바로 감이 오시나요?

결국 자료구조 공부의 핵심은 이론 암기가 아니라, 각 도구가 가진 '강점'과 '한계'를 명확히 아는 데 있는 것 같습니다. 스택은 뒤를 돌아볼 때, 큐는 앞을 향해 나갈 때, 힙은 가장 중요한 것을 골라낼 때 빛을 발하죠.
 
제 생각에는 문법을 외우는 것보다 "이 상황에서 리스트를 쓰면 왜 느릴까?"를 스스로 고민해 보는 과정이 훨씬 중요해 보여요. 2026년의 코딩테스트는 단순 구현보다 효율성을 훨씬 엄격하게 따지기 때문입니다. 오늘 알려드린 deque와 heapq 활용법만 손에 익혀도, 효율성 테스트에서 'Fail' 문구를 볼 확률이 절반 이상 줄어들 거라 확신합니다.

코딩테스트 시간 초과 해결사: 효율적인 정렬 알고리즘과 이진 탐색 응용법