Stack

// JavaScript 스택 구현 예제

class Stack {
    constructor() {
        this.items = [];
    }

    // 스택의 top에 요소 추가 - O(1)
    push(item) {
        this.items.push(item);
        return this;  // 메서드 체이닝 지원
    }

    // 스택의 top에서 요소 제거 및 반환 - O(1)
    pop() {
        if (this.isEmpty()) {
            throw new Error("빈 스택에서 pop 시도");
        }
        return this.items.pop();
    }

    // top 요소 확인 (제거 없음) - O(1)
    peek() {
        if (this.isEmpty()) {
            throw new Error("빈 스택에서 peek 시도");
        }
        return this.items[this.items.length - 1];
    }

    // 스택이 비어있는지 확인 - O(1)
    isEmpty() {
        return this.items.length === 0;
    }

    // 스택의 크기 - O(1)
    get size() {
        return this.items.length;
    }

    // 스택 초기화
    clear() {
        this.items = [];
    }

    // 배열로 변환
    toArray() {
        return [...this.items];
    }

    toString() {
        return `Stack([${this.items.join(', ')}])`;
    }
}


// 사용 예제
const stack = new Stack();
stack.push("A").push("B").push("C");

console.log(`스택: ${stack}`);            // Stack([A, B, C])
console.log(`top: ${stack.peek()}`);      // C
console.log(`크기: ${stack.size}`);        // 3

console.log(`pop: ${stack.pop()}`);       // C
console.log(`pop: ${stack.pop()}`);       // B
console.log(`남은 스택: ${stack}`);         // Stack([A])


// ========== 실무 활용 예제 ==========

// 1. 괄호 유효성 검사
function isValidParentheses(s) {
    const stack = [];
    const pairs = { ')': '(', '}': '{', ']': '[' };

    for (const char of s) {
        if ('({['.includes(char)) {
            stack.push(char);
        } else if (')}]'.includes(char)) {
            if (stack.length === 0 || stack[stack.length - 1] !== pairs[char]) {
                return false;
            }
            stack.pop();
        }
    }

    return stack.length === 0;
}

console.log(isValidParentheses("({[]})")); // true
console.log(isValidParentheses("([)]"));   // false


// 2. 브라우저 히스토리 (뒤로가기/앞으로가기)
class BrowserHistory {
    constructor(homepage) {
        this.backStack = [];
        this.forwardStack = [];
        this.current = homepage;
    }

    visit(url) {
        this.backStack.push(this.current);
        this.current = url;
        this.forwardStack = [];  // 새 페이지 방문 시 앞으로 가기 스택 초기화
        console.log(`방문: ${url}`);
    }

    back() {
        if (this.backStack.length === 0) {
            console.log("뒤로 갈 수 없습니다.");
            return this.current;
        }
        this.forwardStack.push(this.current);
        this.current = this.backStack.pop();
        console.log(`뒤로 -> ${this.current}`);
        return this.current;
    }

    forward() {
        if (this.forwardStack.length === 0) {
            console.log("앞으로 갈 수 없습니다.");
            return this.current;
        }
        this.backStack.push(this.current);
        this.current = this.forwardStack.pop();
        console.log(`앞으로 -> ${this.current}`);
        return this.current;
    }
}

const browser = new BrowserHistory("google.com");
browser.visit("youtube.com");
browser.visit("facebook.com");
browser.back();    // youtube.com
browser.back();    // google.com
browser.forward(); // youtube.com


// 3. DFS (깊이 우선 탐색) - 스택 활용
function dfsIterative(graph, start) {
    const visited = new Set();
    const stack = [start];
    const result = [];

    while (stack.length > 0) {
        const node = stack.pop();
        if (!visited.has(node)) {
            visited.add(node);
            result.push(node);
            // 역순으로 추가
            const neighbors = graph[node] || [];
            for (let i = neighbors.length - 1; i >= 0; i--) {
                if (!visited.has(neighbors[i])) {
                    stack.push(neighbors[i]);
                }
            }
        }
    }

    return result;
}

const graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
};
console.log(`DFS 순회: ${dfsIterative(graph, 'A')}`); // A,B,D,E,F,C


// 4. 수식 계산기 (후위 표기법)
function evaluatePostfix(expression) {
    const stack = [];
    const tokens = expression.split(' ');

    for (const token of tokens) {
        if (!isNaN(token)) {
            stack.push(parseFloat(token));
        } else {
            const b = stack.pop();
            const a = stack.pop();
            switch (token) {
                case '+': stack.push(a + b); break;
                case '-': stack.push(a - b); break;
                case '*': stack.push(a * b); break;
                case '/': stack.push(a / b); break;
            }
        }
    }

    return stack.pop();
}

// "3 + 4 * 2" -> 후위: "3 4 2 * +"
console.log(evaluatePostfix("3 4 2 * +"));  // 11
// "( 5 - 3 ) * 4" -> 후위: "5 3 - 4 *"
console.log(evaluatePostfix("5 3 - 4 *"));  // 8


// 5. Min Stack (최솟값 O(1) 조회 스택)
class MinStack {
    constructor() {
        this.stack = [];
        this.minStack = [];  // 각 시점의 최솟값 저장
    }

    push(val) {
        this.stack.push(val);
        const minVal = this.minStack.length === 0
            ? val
            : Math.min(val, this.minStack[this.minStack.length - 1]);
        this.minStack.push(minVal);
    }

    pop() {
        this.stack.pop();
        this.minStack.pop();
    }

    top() {
        return this.stack[this.stack.length - 1];
    }

    getMin() {
        return this.minStack[this.minStack.length - 1];
    }
}

const minStack = new MinStack();
minStack.push(5);
minStack.push(2);
minStack.push(7);
console.log(`최솟값: ${minStack.getMin()}`);  // 2
minStack.pop();
minStack.pop();
console.log(`최솟값: ${minStack.getMin()}`);  // 5