배열과 연결 리스트가 데이터를 '저장하는 방식'에 대한 구조라면, 스택과 큐는 데이터를 '넣고 빼는 순서(Rule)'에 대한 논리적 자료구조입니다. 스택은 프링글스 과자통처럼 가장 늦게 들어간 데이터가 가장 먼저 나오는 LIFO(Last-In-First-Out) 방식이며, 큐는 톨게이트 줄서기처럼 먼저 온 데이터가 먼저 처리되는 FIFO(First-In-First-Out) 방식입니다.
1. 구조 및 동작 원리 (LIFO vs FIFO)
2. 성능 및 특징 요약
특징
스택 (Stack)
큐 (Queue)
처리 규칙
LIFO (Last-In-First-Out)
FIFO (First-In-First-Out)
데이터 추가 연산
Push - 탑(Top) 위치에 추가
Enqueue - 꼬리(Rear) 위치에 추가
데이터 추출 연산
Pop - 탑(Top) 위치에서 제거 및 반환
Dequeue - 머리(Front) 위치에서 제거 및 반환
시간 복잡도 (삽입/삭제)
O(1)
O(1)
💡 실무 지식: 어디에 쓰이나요?
스택(Stack)은 주로 '최근의 상태를 기억하고 되돌릴 때' 사용합니다. 대표적으로 에디터의 '실행 취소(Ctrl+Z)', 웹 브라우저의 '뒤로 가기', 프로그래밍 언어의 함수 호출 스택(Call Stack) 구현에 쓰입니다.
큐(Queue)는 '순서대로 일을 처리해야 할 때' 사용합니다. 인쇄 작업 대기열, 은행 번호표 처리 시스템, 식당의 주문 시스템, 그리고 비동기 데이터 통신에서의 메시지 큐(Message Queue - Kafka, RabbitMQ) 등 순서 보장이 필수인 곳에 쓰입니다.
// 📂 DataStructures.js (JavaScript)
// 자바스크립트는 배열(Array) 자체에 스택과 큐를 위한 내장 메서드가 모두 존재합니다.
// 1. Stack (LIFO)
class Stack {
constructor() {
this.items = [];
}
push(element) {
this.items.push(element); // 배열의 맨 끝에 추가 (O(1))
}
pop() {
return this.items.pop(); // 배열의 맨 끝에서 제거 (O(1))
}
peek() {
return this.items[this.items.length - 1];
}
}
// 2. Queue (FIFO)
class Queue {
constructor() {
this.items = [];
}
enqueue(element) {
this.items.push(element); // 배열의 맨 끝에 추가 (O(1))
}
dequeue() {
// shift()는 O(N)의 시간이 걸리므로 실제로는 연결리스트 기반 큐가 더 효율적입니다.
return this.items.shift(); // 배열의 맨 앞(0번 인덱스)에서 제거
}
}
// 실행 예시
const stack = new Stack();
stack.push("A");
stack.push("B");
console.log("Stack Pop:", stack.pop()); // B 출력
const queue = new Queue();
queue.enqueue("1번 손님");
queue.enqueue("2번 손님");
console.log("Queue Dequeue:", queue.dequeue()); // 1번 손님 출력