7. 스택과 큐 (Stacks and Queues) Codility Lesson 한국어 정리본 (JavaScript ver.)

스택(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) 시간 복잡도를 가지며, 최소한 필요한 대기 인원을 구할 수 있다.