스택(Stack)과 큐(Queue)란?
스택과 큐는 데이터를 저장하고 관리하는 대표적인 자료구조이다. 이들은 push(삽입) 및 pop(삭제) 연산을 제공하지만, 데이터의 입출력 방식이 다르다.
1. 스택(Stack)
스택은 LIFO(Last In, First Out) 구조를 가지며, 가장 최근에 추가된 요소가 가장 먼저 제거된다. 마치 접시를 쌓아올리고 위에서부터 하나씩 제거하는 방식과 유사하다.
JavaScript 코드:
class Stack {
constructor() {
this.stack = [];
}
push(x) {
this.stack.push(x);
}
pop() {
if (this.isEmpty()) throw new Error("Stack is empty");
return this.stack.pop();
}
isEmpty() {
return this.stack.length === 0;
}
}
시간 복잡도: O(1) (push, pop 연산 모두 상수 시간에 수행됨)
2. 큐(Queue)
큐는 FIFO(First In, First Out) 구조를 가지며, 먼저 추가된 요소가 가장 먼저 제거된다. 이는 마치 은행 창구에서 줄을 서는 방식과 같다.
JavaScript 코드:
class Queue {
constructor() {
this.queue = [];
}
push(x) {
this.queue.push(x);
}
pop() {
if (this.isEmpty()) throw new Error("Queue is empty");
return this.queue.shift();
}
isEmpty() {
return this.queue.length === 0;
}
size() {
return this.queue.length;
}
}
시간 복잡도: O(1) (push 연산), O(n) (shift 연산 → 개선 가능)
효율적인 큐 구현을 위해 이중 연결 리스트 또는 순환 버퍼(Circular Buffer) 를 사용할 수도 있다.
3. 슈퍼마켓 대기열 문제
슈퍼마켓에서 사람들이 줄을 서고, 일정 시간이 지나면 한 명씩 계산을 마치고 나가는 상황을 모델링하는 문제이다.
배열 A는 0과 1로 이루어져 있으며:
- 0 → 새로운 사람이 줄을 섬 (push 연산)
- 1 → 줄 앞의 사람이 계산을 마침 (pop 연산)
이때, 시뮬레이션이 가능하도록 최소 몇 명이 줄을 서 있어야 하는지를 구하는 문제이다.
O(n) 해결법 (큐 크기 추적)
function groceryStore(A) {
let size = 0;
let result = 0;
for (let i = 0; i < A.length; i++) {
if (A[i] === 0) {
size++;
} else {
size--;
}
result = Math.max(result, -size);
}
return result;
}
이 알고리즘은 O(n) 시간 복잡도를 가지며, 최소한 필요한 대기 인원을 구할 수 있다.
반응형
댓글