스택(Stacks) & 큐(Queues)

📌 Stack

후입선출(LIFO)에 따라 데이터를 추가하고 삭제하는 자료구조.
가장 마지막으로 추가된 요소가 가장 먼저 제거된다.

예시:

• 함수 호출을 다루는 상황(호출 스택)
• undo/redo(포토샵에서 실행 취소, 재실행)
• 인터넷 브라우저에 있는 방문 기록

추가 : push, 삭제: pop 이라고 부른다.

구현

스택은 추상적인 개념이기 때문에 한 가지 방식으로만 만들 수 있는게 아니고, 여러 방식으로 만들 수 있다.
몇몇 프로그래밍 언어에는 스택이 내장되어 있다.
JS에는 내장되어 있지 않기 때문에 직접 구현해야 하지만 구현하기 쉬운 편이다.

1. JS에 내장되어 있는 배열로 구현

배열의 push&pop 메소드 혹은 unshift&shift 메소드 사용
(방향은 상관없고 후입선출 규칙만 지키면 됨.)

빅오표기법에 따르면 배열에서 맨 앞에 요소를 추가하고 제거하는건 시간복잡도가 좋지 않기 때문에 unshift&shift 보다는 push&pop을 쓰는게 좋다.

인덱스를 기반으로 접근할 일이 없으므로 스택을 배열로 구현하는건 효율성 측면에서 그다지 좋지 않다. 리스트를 이용해 구현하는게 더 낫다.

var stack = [];
stack.push("first");
stack.push("second");
stack.pop(); // second
stack.pop(); // first

stack.unshift("first");
stack.unshift("second");
stack.shift(); // second
stack.shift(); // first

2. 단일 연결 리스트로 구현

단일 연결 리스트로 스택을 구현할 수 있다.

⭐️ 한 가지 유의할 점은 단일 연결 리스트의 특성상 pop의 시간 복잡도가 O(1)이 아닌 O(n)이기 때문에, push&pop을 쓰는 것보다 unshift&shift를 사용하는 것이 더 효율적이라는 것이다.

(코드에서 push&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;
    }
}

⭐️ 스택의 Big O

삽입&제거 : O(1)

탐색&접근 : O(n)

탐색과 접근은 실제로 사용하지 않기 때문에 중요한건 삽입&제거가 얼마나 빠른가이다.

📌 Queue

선입선출(FIFO)에 따라 데이터를 추가하고 삭제하는 자료구조.
가장 먼저 추가된 요소가 가장 먼저 제거된다.
(선입선출 규칙 외에는 스택과 비슷하다.)

예시: 줄서기, 프린트

추가 : enqueue, 삭제: dequeue 이라고 부른다.

구현

1. 배열로 구현

배열의 push&shift 혹은 unshift&pop 메소드를 사용한다.
마찬가지로 효율성이 떨어지는 편이다.

var q = [];
q.push("first");
q.push("second");
q.shift(); // first
q.shift(); // second

q.unshift("first");
q.unshift("second");
q.pop(); // first
q.pop(); // second

2. 단일 연결 리스트로 구현

단일 연결 리스트의 특성상 뒤에서 제거하는 것이 효율성이 좋지 않기 때문에 앞에서 제거해주는 방식을 사용한다.
enqueue : 뒤에서 추가 (push)
dequeue : 앞에서 제거 (shift)

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

class Queue {
    constructor(){
        this.first = null;
        this.last = null;
        this.size = 0;
    }
    enqueue(val){
        var newNode = new Node(val);
        if(!this.first){
            this.first = newNode;
            this.last = newNode;
        } else {
            this.last.next = newNode;
            this.last = newNode;
        }
        return ++this.size;
    }

    dequeue(){
        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

삽입&제거 : O(1)

탐색&접근 : O(n)