스택이란

stack이 뭔가요

데이터 구조입니다. 후입선출 (LIFO) 원칙을 따르는 데이터들의 모읍이죠
가장 마지막에 추가된 요소는 가장 먼저 제거됩니다.

쌓여있는 책을 생각해봅시다. 그리고 그 책을 정리하려면 어떻게 해야할까요? 맨 위에 있는 책부터 내려놓겠죠?

배열로 스택 만들기

let stack= [];

stack.push("google")
stack.push("instagram")
stack.push("youtube")

stack.pop()

물론 shift, unshift 를 사용할 수도 있지만 비효율적입니다. 하나의 데이터가 바뀔 때마다 인덱싱을 다시해야하기 때문이죠

스크레치로 자신만의 스택 작성하기

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

class Stack {
    constructor(){
        this.first = null;
        this.last = null;
        this.size = 0;
    }
    push(val){
        var newNode = new Node(val);
        if(!this.first){
            this.first = newNode;
            this.last = newNode;
        } else {
            var temp = this.first;
            this.first = newNode;
            this.first.next = temp;
        }
        return ++this.size;
    }
    pop(){
        if(!this.first) return null;
        var temp = this.first;
        if(this.first === this.last){
            this.last = null;
        }
        this.first = this.first.next;
        this.size--;
        return temp.value;
    }
}

스택의 빅오

• Insertion : O(1)
• Removal : O(1)
• Searching : O(N)
• Access : O(N)

스택의 장점은 삽입과 제거의 빅오입니다.