[자료구조] 스택 & 큐

스택 LIFO

• Last In First Out ( 후입선출 )
• 가장 마지막에 있는 요소가 먼저 제거
• 자바스크립트에서 재귀를 다룰 때 콜스택도 마찬가지로 이 스택의 원리이다.
• 다른 언어는 내장된 경우가 있는데, 자바스크립트에서는 내장되어있지 않아서 배열을 사용하던가, 연결리스트 통하여 구현해야한다.

사용되는 예시

• 함수호출을 다루는 콜스택
• 포토샵 실행취소, 다시실행 ( undo / redo)
• 브라우저 방문기록

---

접근 - 배열

• 배열의 끝 지점의 삽입과 삭제를 다루는 push, pop 함수를 이용한다.

• 배열의 첫 지점에서 삽입과 삭제를 다루는 unshift, shift 함수를 이용할 수도 있다.

후입선출의 규칙만 지킨다면 어느방향으로 하던 상관은 없지만
unshift, shift 는 배열에서는 첫번째 인자를 삽입 삭제할 경우 모든 요소들이 다 움직여야하기 때문에 시간복잡도가 O(N)이라 비효율적이다.

push, pop의 경우는 O(1) 상수시간이기 때문에 이것을 사용하는게 더 낫다.

접근 - 연결 리스트 (클래스)

인덱스에 접근하는 것이 아니라 그냥 삽입했을 때 순서에 기반해서 정보를 다루기만 하면 되기 때문에 배열에 사용되는 많은 메소드들이 필요가 없다.

단일 연결리스트에서는 한쪽 방향으로만 연결되는 특성 때문에 맨 마지막에 요소를 삽입하거나 삭제할 때 앞에서부터 검색해야 함으로 push, pop보단 unshift,shift 로 처음요소를 삽입하고 제거하는것이 낫다.

후입선출의 규칙은 동일하다!

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

    push(val){
        //앞에 삽입 
        const addData = new Node(val);
        if(this.size ===0){
            this.first = addData;
            this.last = addData;
        }
        else{
            addData.next = this.first;
            this.first = addData;
        }
        return ++this.size;
        
    }
    pop(){
        //앞을 제거 

        if(this.size ===0 ) return null;

        let deleteData = this.first;
        if(this.first===this.last){
            this.last = null;
        }
        this.first = this.first.next;
        
        this.size--;
        return deleteData;

    }
}

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

---

큐 FIFO

• 먼저들어온 것이 먼저 나간다
• 삽입 enqueue, 삭제 dequeue

예시

• 줄 서는 경우
• 게임에서 접속하려고 대기 > 가장 오래 기다린 사람을 추적하는 큐 데이터 구조
• 컴퓨터 백그라운드
• 프린트

접근 - 배열

• 삽입 push 함수 / 삭제 shift함수
• 삽입 unshift / 삭제 pop 함수 ( 거꾸로 구현 )
• 삽입 O(1), 삭제 O(N)

접근 - 리스트

• 맨 뒤에 추가하고 맨 앞에 삭제
• 맨 앞에 추가하고 맨 뒤에 삭제 ( 거꾸로 )

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

    enqueue(val){
        const newNode = new Node(val);
        if(this.size ===0){
            this.first = newNode;
            this.last = newNode;
        }
        else{
            this.last.next = newNode;
            this.last = newNode;
        }
        return ++this.size;
        
    }
    dequeue(){

        if(this.size ===0 ) return null;

        let deleteData = this.first;
        if(this.first===this.last){
            this.last = null;
        }
        this.first = this.first.next;
        
        this.size--;
        return deleteData;

    }
}

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

---

스택 & 큐 빅오

스택과 큐에서는 탐색, 인덱스 위치를 사용해서 접근하는 것이 필요 없다.
삽입과 제거 후입선출, 선입선출을 잘 지키는 것이 중요하다.

스택

연결리스트 - 삽입 O(1) / 삭제 O(1)
배열 - 삽입 O(1) / 삭제 O(1)
복잡도는 상수시간이지만 스택에서는 삽입 삭제만 필요함으로 배열처럼 많은 메서드가 필요없다.
연결리스트의 경우는 코드를 많이 구현해야하기 때문에, 좋은 방법이지만
빠르게 작성을 해야할 경우 배열을 사용하는 것이 낫다.

큐

연결리스트 - 삽입 O(1) / 삭제 O(1)
배열 - 삽입 O(1) / 삭제 O(N) 혹은 반대