스택(Stack)

---

스택(Stack)

스택은 후입선출(Last In First Out) 개념을 가진 선형 자료구조로, 맨 마지막에 저장된 데이터가 맨 처음으로 꺼내진다.

push : 스택 맨위에 데이터를 삽입
pop : 스택 맨위에 데이터를 사겢
top : 스택 맨위의 노드를 가르킴
peek : 스택 맨위의 데이터를 삭제하지 않고 가져옴

스택의 특징

• push(), pop(), isEmpty(), peek() 모두 O(1) 시간이 걸린다.
• 배열을 사용하여 구현할 수도 있다.
• 연결 리스트를 사용하여 구현할 수 있다.

구현

연결 리스트로 구현한 스택

class Node {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class Stack {
    constructor() {
        this.top = null;
        this.size = 0;
    }

    push(value) {
        const node = new Node(value);

        node.next = this.top;
        this.top = node;
        this.size += 1;
    }

    pop() {
        const value = this.top.value;

        this.top = this.top.next;
        this.size -=1;

        return value;
    }

    size() {
        return this.size;
    }
}

const stack = new Stack();

stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.pop()); // 3
stack.push(4);
console.log(stack.pop()) // 4
console.log(stack.pop()); // 2