Stack with JS

• 단일 연결 리스트 
• 이중 연결 리스트
• 스택 & 큐 (배열로 하는 방법은 숙지했음! linked list로 구현해 보기)
• 이진 검색 트리
• 트리 순회
• 이진 힙
• 해시 테이블 (사용해 봤지만 복습)
• 그래프, 그래프 순회
• 다익스트라 알고리즘
• 동적 프로그래밍

스택은 후입선출 원칙에 따라 데이터를 추가하고 제거하는 데이터 구조이다.

배열을 사용할 때 js 내에 stack.pop(), stack.push(value) ,stack.unshift(value) 등이 있지만 이것을 기계적으로 사용하다보면 문제를 바라볼 때 이해가 안될때가 많다.

그렇기 때문에 linked list를 통해 원리를 이해하는 것이 중요하다.

Stack class setting

Node 클래스는 연결리스트이기 때문에 똑같다.

stack은 연결리스트에서 했던 것처럼 head, tail, length 대신에 first ,last ,size가 있다. (사실 변수명은 자유)

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

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

push 

링크드리스트와 비슷했지만 아래에서 위로 차는 느낌이라 (왼쪽에서 오른쪽) 뭔가 어색했다. 

    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

pop은 간단하게 first의 위치만 first의 next의 값에 first를 위치하면 된다.

    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;
    }

first 와 last가 같을 때와 기본적인 Pop

 

 

stack에 대한 기본적인 코드 구조

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;
    }
}

 

시간 복잡도 

Big O of Stacks

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

 

자료 : https://www.udemy.com/course/best-javascript-data-structures/