
스택(Stack)과 큐(Queue): 개발자가 줄을 서는 방법
프링글스 통(Stack)과 맛집 대기 줄(Queue). 가장 기초적인 자료구조지만, 이걸 모르면 재귀 함수도 메시지 큐도 이해할 수 없습니다.

프링글스 통(Stack)과 맛집 대기 줄(Queue). 가장 기초적인 자료구조지만, 이걸 모르면 재귀 함수도 메시지 큐도 이해할 수 없습니다.
내 서버는 왜 걸핏하면 뻗을까? OS가 한정된 메모리를 쪼개 쓰는 처절한 사투. 단편화(Fragmentation)와의 전쟁.

로버트 C. 마틴(Uncle Bob)이 제안한 클린 아키텍처의 핵심은 무엇일까요? 양파 껍질 같은 계층 구조와 의존성 규칙(Dependency Rule)을 통해 프레임워크와 UI로부터 독립적인 소프트웨어를 만드는 방법을 정리합니다.

미로를 탈출하는 두 가지 방법. 넓게 퍼져나갈 것인가(BFS), 한 우물만 팔 것인가(DFS). 최단 경로는 누가 찾을까?

이름부터 빠릅니다. 피벗(Pivot)을 기준으로 나누고 또 나누는 분할 정복 알고리즘. 왜 최악엔 느린데도 가장 많이 쓰일까요?

코딩 공부를 시작하고 나서 한 달쯤 됐을 때, 나는 스택(Stack)과 큐(Queue)라는 개념을 처음 접했다. 그런데 솔직히 말하면 처음엔 이해가 잘 안 됐다.
"그냥 배열(Array) 쓰면 안 돼? 왜 굳이 스택이랑 큐를 따로 배워야 하는 거지?"
배열에 push도 있고 pop도 있고 shift도 있는데, 굳이 스택이니 큐니 하는 개념을 왜 배우는지 와닿지 않았다. 하지만 시간이 지나고 나서야 깨달았다. 스택과 큐는 단순히 "데이터를 담는 통"이 아니라, "데이터를 어떤 순서로 꺼내는가"에 대한 철학이었다는 것을.
그리고 그 철학이 없으면 재귀 함수도, 이벤트 루프도, 메시지 큐도 이해할 수 없다. 웹 브라우저의 뒤로 가기 버튼도, BFS/DFS 알고리즘도 동작하지 않는다. 이 글은 내가 스택과 큐를 이해하고, 받아들이고, 결국 "아, 이거였구나"라고 깨달은 과정을 정리해본다.
우리가 데이터를 저장하는 방법은 크게 두 가지 상황이 있습니다.
이 두 가지 상황을 해결하기 위해 만든 도구가 바로 스택(Stack)과 큐(Queue)입니다. 너무 기본적이라고요? 하지만 이 두 녀석이 없으면 운영체제도, 인터넷 브라우저도, 여러분이 쓰는 카카오톡도 동작하지 않습니다.
스택은 '쌓아 올린다'는 뜻입니다. 가장 완벽한 비유는 프링글스 감자칩 통입니다.
이것을 전문 용어로 LIFO (Last In, First Out - 후입선출)라고 합니다. "나중에 온 놈이 제일 먼저 나간다"는 조금 불공평한 세상이죠.
1. 실행 취소 (Ctrl + Z) 방금 쓴 글자를 지우고 싶습니다. '가장 마지막에(Last)' 쓴 글자가 '가장 먼저(First)' 지워져야겠죠? 그래서 모든 편집기의 히스토리는 스택으로 저장됩니다.
2. 브라우저 뒤로 가기 웹 서핑을 하다가 뒤로 가기 버튼을 누릅니다. '가장 최근에(Last)' 방문한 페이지가 '가장 먼저(First)' 나옵니다.
3. 함수 호출 스택 (Call Stack)
개발자가 Stack Overflow 에러를 만나는 그곳입니다.
함수 A가 B를 부르고, B가 C를 부르면 컴퓨터는 "C 끝내고 B로 가고, B 끝내고 A로 가야지"라고 적어둡니다. 이 순서가 바로 스택입니다. 재귀 함수(Recursion)를 잘못 짜면 이 스택 통이 꽉 차서 터지는 게 Stack Overflow입니다.
// 자바스크립트에서의 스택
const stack = [];
stack.push("A"); // 넣기
stack.push("B");
console.log(stack.pop()); // 꺼내기 -> "B" (나중에 넣은 게 먼저 나옴)
나는 처음 재귀 함수를 배우고 나서 신이 났다. "함수가 자기 자신을 부를 수 있다고? 이거 완전 신박한데?" 그리고 팩토리얼(Factorial)을 계산하는 함수를 짰다.
function factorial(n) {
return n * factorial(n - 1);
}
console.log(factorial(5)); // 엥? Maximum call stack size exceeded???
응? 왜 에러가 나지? 그제야 나는 종료 조건(Base Case)을 까먹었다는 걸 깨달았다. 재귀 함수는 끝없이 자기 자신을 부르다가 결국 콜 스택(Call Stack)을 꽉 채워버렸다. 프링글스 통에 감자칩을 무한정 쌓다가 통이 터진 것과 똑같은 상황이었다.
// 올바른 재귀 함수
function factorial(n) {
if (n === 0 || n === 1) return 1; // Base Case: 종료 조건
return n * factorial(n - 1);
}
console.log(factorial(5)); // 120
이때 나는 스택이 단순히 "데이터 넣고 빼는 통"이 아니라, 함수 호출의 순서를 관리하는 메커니즘이라는 걸 받아들였다.
자바스크립트는 배열로 스택을 간단히 만들 수 있지만, 진짜 스택의 원리를 이해하려면 클래스로 직접 구현해보는 게 좋다.
class Stack {
constructor() {
this.items = [];
}
push(element) {
this.items.push(element);
}
pop() {
if (this.isEmpty()) {
return "Stack is empty";
}
return this.items.pop();
}
peek() {
// 맨 위의 요소를 제거하지 않고 확인만
if (this.isEmpty()) {
return "Stack is empty";
}
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
clear() {
this.items = [];
}
print() {
console.log(this.items.toString());
}
}
// 사용 예시
const stack = new Stack();
stack.push("First");
stack.push("Second");
stack.push("Third");
console.log(stack.peek()); // "Third"
console.log(stack.pop()); // "Third"
console.log(stack.size()); // 2
스택의 가장 대표적인 문제가 "괄호가 올바르게 닫혔는지 검사하는 것"이다. LeetCode의 Valid Parentheses 문제다.
function isValid(s) {
const stack = [];
const pairs = {
')': '(',
'}': '{',
']': '['
};
for (let char of s) {
if (char === '(' || char === '{' || char === '[') {
stack.push(char); // 여는 괄호는 스택에 넣기
} else {
// 닫는 괄호가 나왔을 때
if (stack.length === 0 || stack.pop() !== pairs[char]) {
return false; // 짝이 안 맞음
}
}
}
return stack.length === 0; // 스택이 비어있어야 올바른 괄호
}
console.log(isValid("()")); // true
console.log(isValid("()[]{}")); // true
console.log(isValid("(]")); // false
console.log(isValid("([)]")); // false
console.log(isValid("{[]}")); // true
여는 괄호는 스택에 넣고, 닫는 괄호가 나오면 스택에서 꺼내서 짝이 맞는지 확인한다. 프링글스 통에 감자칩을 넣었다가 빼는 것과 똑같다. 이 문제를 풀고 나서 나는 "아, 스택이 이렇게 쓰이는구나"라는 걸 깊게 이해했다.
큐는 '줄을 서다'라는 뜻입니다. 지극히 공평한 세상입니다.
이것을 FIFO (First In, First Out - 선입선출)라고 합니다. 톨게이트를 지나가는 차들, 맛집 앞에 늘어선 줄을 생각하면 됩니다.
1. 프린터 인쇄 대기열 김 대리가 100장짜리 보고서를 인쇄 눌렀습니다. 1초 뒤에 이 부장이 1장짜리를 인쇄 눌렀습니다. 당연히 김 대리의 100장이 다 나올 때까지 이 부장 것은 대기해야 합니다. 순서가 보장되어야 하니까요.
2. 백엔드의 구세주: 메시지 큐 (Kafka, RabbitMQ) 주문이 폭주하는 쇼핑몰 서버를 생각해 봅시다. 1초에 1만 명이 결제를 누르면 DB가 터집니다. 이때 서버는 결제 요청을 바로 처리하지 않고 큐(Queue)에 일단 쌓아둡니다. (줄을 세웁니다) 그리고 뒤에 있는 처리 서버(Worker)가 자기 능력만큼 하나씩 꺼내서 차근차근 처리합니다.
이 구조 덕분에 서버가 터지지 않고 버틸 수 있습니다. 이를 비동기 처리(Asynchronous Processing)의 핵심이라고 부릅니다.
// 자바스크립트에서의 큐 (배열 활용)
const queue = [];
queue.push("User1"); // 줄 서기
queue.push("User2");
console.log(queue.shift()); // 입장 -> "User1" (먼저 온 놈이 먼저 나감)
// 주의: shift()는 성능이 느립니다(O(n)). 실제로는 Linked List로 된 큐를 써야 합니다.
나는 큐를 처음 배웠을 때 자바스크립트 배열의 shift()를 썼다. 맨 앞에서 빼면 되니까 간단하잖아? 그런데 알고리즘 문제를 풀다가 "Time Limit Exceeded" 에러를 만났다.
왜 시간 초과가 나지? 그제야 나는 shift()의 동작 원리를 찾아봤다.
shift()는 맨 앞의 요소를 제거한다.반면 push()는 맨 뒤에 추가만 하면 되니까 O(1) (매우 빠름)이다. 결국 배열로 큐를 만들면 shift() 때문에 성능이 개판이 된다는 걸 깨달았다.
성능 문제를 해결하려면 Linked List (연결 리스트)로 큐를 만들어야 한다. 맨 앞과 맨 뒤를 포인터로 관리하면 enqueue도 dequeue도 O(1)에 처리할 수 있다.
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class Queue {
constructor() {
this.front = null; // 맨 앞 (dequeue할 곳)
this.rear = null; // 맨 뒤 (enqueue할 곳)
this.size = 0;
}
enqueue(value) {
const newNode = new Node(value);
if (this.isEmpty()) {
this.front = newNode;
this.rear = newNode;
} else {
this.rear.next = newNode; // 기존 맨 뒤의 다음을 새 노드로
this.rear = newNode; // 맨 뒤를 새 노드로 업데이트
}
this.size++;
}
dequeue() {
if (this.isEmpty()) {
return "Queue is empty";
}
const removed = this.front.value;
this.front = this.front.next; // 맨 앞을 다음 노드로 이동
this.size--;
if (this.size === 0) {
this.rear = null; // 큐가 비면 rear도 null
}
return removed;
}
peek() {
if (this.isEmpty()) {
return "Queue is empty";
}
return this.front.value;
}
isEmpty() {
return this.size === 0;
}
getSize() {
return this.size;
}
print() {
if (this.isEmpty()) {
console.log("Queue is empty");
return;
}
let current = this.front;
const values = [];
while (current) {
values.push(current.value);
current = current.next;
}
console.log(values.join(" <- "));
}
}
// 사용 예시
const queue = new Queue();
queue.enqueue("First");
queue.enqueue("Second");
queue.enqueue("Third");
queue.print(); // First <- Second <- Third
console.log(queue.dequeue()); // "First"
console.log(queue.peek()); // "Second"
console.log(queue.getSize()); // 2
이제 enqueue와 dequeue 모두 O(1)이다. 데이터가 100만 개여도 성능 저하가 없다. 이 구현을 이해하고 나서 나는 "큐는 배열이 아니라 연결 리스트로 만들어야 한다"는 것을 몸으로 받아들였다.
여기서 진짜 핵심이 나온다. 자바스크립트의 이벤트 루프(Event Loop)는 스택과 큐를 동시에 사용하는 완벽한 예시다.
자바스크립트 엔진은 함수를 실행할 때 Call Stack에 쌓는다. LIFO 방식이다.
function first() {
console.log("First");
second();
}
function second() {
console.log("Second");
third();
}
function third() {
console.log("Third");
}
first();
실행 순서:
first() 실행 → Call Stack에 first pushconsole.log("First") 실행 후 second() 호출 → Call Stack에 second pushconsole.log("Second") 실행 후 third() 호출 → Call Stack에 third pushconsole.log("Third") 실행 후 third 종료 → Call Stack에서 third popsecond 종료 → Call Stack에서 second popfirst 종료 → Call Stack에서 first pop스택(Stack)이다. 프링글스 통처럼 쌓이고 빠진다.
비동기 함수(setTimeout, fetch, 이벤트 리스너 등)는 완료되면 Callback Queue에 들어간다. FIFO 방식이다.
console.log("Start");
setTimeout(() => {
console.log("Timeout 1");
}, 0);
setTimeout(() => {
console.log("Timeout 2");
}, 0);
console.log("End");
실행 결과:
Start
End
Timeout 1
Timeout 2
왜 이렇게 나올까?
console.log("Start") 실행 (Call Stack)setTimeout은 비동기 → Web API로 넘어감console.log("End") 실행 (Call Stack)Timeout 1 실행, Timeout 2 실행큐(Queue)다. 먼저 들어간 콜백이 먼저 실행된다.
Promise는 Callback Queue가 아니라 Microtask Queue에 들어간다. 우선순위가 더 높다.
console.log("Start");
setTimeout(() => {
console.log("Timeout");
}, 0);
Promise.resolve().then(() => {
console.log("Promise");
});
console.log("End");
실행 결과:
Start
End
Promise
Timeout
왜? Microtask Queue가 Callback Queue보다 먼저 처리되기 때문이다.
이 구조를 이해하고 나서 나는 "아, 자바스크립트는 스택 하나와 큐 두 개로 돌아가는구나"라는 걸 완전히 이해했다. 이벤트 루프는 스택과 큐의 완벽한 실제 예시다.
자료구조를 배우면 반드시 만나는 알고리즘이 있다. BFS (Breadth-First Search, 너비 우선 탐색)와 DFS (Depth-First Search, 깊이 우선 탐색)다.
function dfs(graph, start) {
const stack = [start];
const visited = new Set();
while (stack.length > 0) {
const node = stack.pop(); // Stack에서 꺼냄 (LIFO)
if (visited.has(node)) continue;
console.log(node); // 방문
visited.add(node);
// 이웃 노드들을 스택에 추가 (나중에 넣은 게 먼저 탐색됨)
for (const neighbor of graph[node].reverse()) {
if (!visited.has(neighbor)) {
stack.push(neighbor);
}
}
}
}
const graph = {
A: ['B', 'C'],
B: ['D', 'E'],
C: ['F'],
D: [],
E: [],
F: []
};
dfs(graph, 'A'); // A B D E C F (깊이 우선)
function bfs(graph, start) {
const queue = [start];
const visited = new Set();
while (queue.length > 0) {
const node = queue.shift(); // Queue에서 꺼냄 (FIFO)
if (visited.has(node)) continue;
console.log(node); // 방문
visited.add(node);
// 이웃 노드들을 큐에 추가 (먼저 넣은 게 먼저 탐색됨)
for (const neighbor of graph[node]) {
if (!visited.has(neighbor)) {
queue.push(neighbor);
}
}
}
}
bfs(graph, 'A'); // A B C D E F (너비 우선)
DFS는 프링글스 통처럼 깊게 파고들고, BFS는 맛집 줄처럼 넓게 퍼진다. 이 차이를 이해하고 나서 나는 "스택과 큐가 알고리즘의 근간이구나"라는 걸 깊게 받아들였다.
양쪽 끝에서 넣고 뺄 수 있는 큐다. 스택 + 큐의 하이브리드다.
class Deque {
constructor() {
this.items = [];
}
addFront(element) {
this.items.unshift(element);
}
addRear(element) {
this.items.push(element);
}
removeFront() {
return this.items.shift();
}
removeRear() {
return this.items.pop();
}
peekFront() {
return this.items[0];
}
peekRear() {
return this.items[this.items.length - 1];
}
isEmpty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
}
일반 큐와 달리, 우선순위가 높은 요소가 먼저 나온다. 병원 응급실을 생각하면 된다. 먼저 온 사람보다 위급한 환자가 먼저 치료받는다.
class PriorityQueue {
constructor() {
this.items = [];
}
enqueue(element, priority) {
const queueElement = { element, priority };
let added = false;
for (let i = 0; i < this.items.length; i++) {
if (queueElement.priority < this.items[i].priority) {
this.items.splice(i, 0, queueElement);
added = true;
break;
}
}
if (!added) {
this.items.push(queueElement);
}
}
dequeue() {
return this.items.shift();
}
front() {
return this.items[0];
}
isEmpty() {
return this.items.length === 0;
}
size() {
return this.items.length;
}
}
// 사용 예시
const pq = new PriorityQueue();
pq.enqueue("Task A", 2);
pq.enqueue("Task B", 1); // 우선순위가 더 높음
pq.enqueue("Task C", 3);
console.log(pq.dequeue()); // Task B (우선순위 1)
console.log(pq.dequeue()); // Task A (우선순위 2)
고정 크기의 큐에서 공간을 재활용한다. 배열의 끝에 도달하면 다시 처음으로 돌아간다.
class CircularQueue {
constructor(size) {
this.items = new Array(size);
this.size = size;
this.front = -1;
this.rear = -1;
}
enqueue(element) {
if ((this.rear + 1) % this.size === this.front) {
console.log("Queue is full");
return;
}
if (this.front === -1) this.front = 0;
this.rear = (this.rear + 1) % this.size;
this.items[this.rear] = element;
}
dequeue() {
if (this.front === -1) {
console.log("Queue is empty");
return;
}
const removed = this.items[this.front];
if (this.front === this.rear) {
this.front = -1;
this.rear = -1;
} else {
this.front = (this.front + 1) % this.size;
}
return removed;
}
isFull() {
return (this.rear + 1) % this.size === this.front;
}
isEmpty() {
return this.front === -1;
}
}
Q1. 스택과 큐의 차이는 무엇인가요? A. 스택은 LIFO (후입선출), 큐는 FIFO (선입선출)입니다. 스택은 가장 나중에 넣은 것이 먼저 나오고, 큐는 가장 먼저 넣은 것이 먼저 나옵니다.
Q2. 자바스크립트 배열로 큐를 만들 때 성능 문제가 생기는 이유는?
A. shift() 메서드는 맨 앞의 요소를 제거한 뒤 나머지 모든 요소를 한 칸씩 앞으로 당기기 때문에 O(n) 시간 복잡도를 가집니다. 연결 리스트로 구현하면 O(1)로 개선할 수 있습니다.
Q3. 재귀 함수와 스택의 관계는? A. 재귀 함수는 내부적으로 Call Stack을 사용합니다. 함수가 자기 자신을 호출할 때마다 스택에 쌓이고, 종료 조건에 도달하면 역순으로 pop됩니다. 종료 조건이 없으면 Stack Overflow가 발생합니다.
Q4. BFS와 DFS의 차이는? A. DFS는 스택(또는 재귀)을 사용하여 깊이 우선으로 탐색하고, BFS는 큐를 사용하여 너비 우선으로 탐색합니다. BFS는 최단 경로 찾기에 유리하고, DFS는 모든 경로 탐색에 유리합니다.
Q5. Priority Queue는 언제 사용하나요? A. 우선순위가 있는 작업 스케줄링, 다익스트라 알고리즘 같은 최단 경로 찾기, 허프만 코딩 같은 압축 알고리즘 등에서 사용됩니다.
Q6. 자바스크립트 이벤트 루프에서 Microtask Queue와 Callback Queue의 차이는? A. Microtask Queue는 Promise, queueMicrotask 등이 들어가고, Callback Queue는 setTimeout, setInterval, DOM 이벤트 등이 들어갑니다. Event Loop는 Call Stack이 비면 Microtask Queue를 먼저 확인하고, 그 다음 Callback Queue를 확인합니다.
1. 메시지 큐 시스템 (Kafka, RabbitMQ) 대규모 트래픽을 처리할 때 메시지 큐는 필수다. 주문, 결제, 알림 등을 큐에 넣고 워커가 순서대로 처리한다.
2. 브라우저 히스토리 관리 뒤로 가기/앞으로 가기 버튼은 두 개의 스택으로 구현된다. 현재 페이지 스택과 앞으로 가기 스택.
3. Redux의 미들웨어 Redux Thunk, Saga 같은 미들웨어는 액션을 큐에 넣고 순서대로 처리한다.
4. CPU 스케줄링 운영체제는 프로세스를 큐에 넣고 우선순위에 따라 처리한다. Round Robin, Priority Scheduling 등이 모두 큐 기반이다.
가끔 인생을 생각해 봅니다. 우리가 쌓아온 경험과 지식은 스택에 가깝습니다. 가장 최근에 배운 지식을 가장 먼저 써먹으니까요. (어릴 때 배운 미적분은 스택 저 밑바닥에 박혀서 꺼내지질 않죠.)
반면 우리가 기다리는 기회들은 큐처럼 옵니다. 조급해하지 않고 줄을 서서 준비하고 있으면, 언젠가 내 차례(Pop)가 오기 마련입니다.
여러분의 코드는 지금 데이터를 쌓고 있나요(Stack), 아니면 줄 세우고 있나요(Queue)? 상황에 맞는 도구를 꺼내는 것이 개발자의 능력입니다.
처음엔 "배열 쓰면 안 돼?"라고 생각했던 나는, 이제 스택과 큐가 데이터 구조의 철학이라는 것을 완전히 받아들였다. 그리고 이 철학이 재귀 함수, 이벤트 루프, 메시지 큐, BFS/DFS까지 모든 곳에 스며들어 있다는 것을 이해했다. 결국 이거였다. 스택과 큐는 단순한 통이 아니라, 컴퓨터가 데이터를 다루는 두 가지 근본적인 방식이었다.