15 스택 & 큐

15.1 스택(Stack)

  스택이란 후입선출 원칙을 따르는 데이터 구조를 일컫는 말이다. 즉, 나중에 들어온 데이터가 먼저 제거되는 방식의 자료 구조를 스택이라고 말한다. 설거지를 하기 위해 싱크대에 쌓인 그릇 중 가장위에 있는 그릇을 하나씩 설거지해 나간다고 생각하면 쉽다. 스택을 코딩하는 방법은 여러가지가 있고 연결 리스트를 사용해서 구현할 수도 있다. 즉, 스택이라는 개념은 후입선출 원칙을 지키는 자료 구조들을 말하는 추상적인 개념이다. 

 

15.2 배열로 스택 구현하기

  배열을 만들고 해당 배열에 데이터를 추가할 때 push() 메서드를 활용하고, 제거할 때 pop() 메서드만을 사용하거나 shift(), unshift() 메서드만을 사용한다면 배열을 스택으로 사용하는 방법이 된다. 후입선출 원칙을 지키고 있기 때문이다. 다만 배열을 스택으로 활용하는 경우에는 push(),pop() 메서드를 활용하는것이 더 좋다.(인덱스 때문에)

var stack = [];
stack.push('a');
stack.push('b');
stack.push('c');
console.log(stack.pop()); // c
console.log(stack.pop()); // b
console.log(stack.pop()); // a

15.3 단일 연결 리스트로 스택 구현하기

  스택은 후입선출 구조 원칙을 지키면 되기 때문에 단일 연결 리스트로도 스택을 구현할 수 있다. 다만, 단일 연결 리스트를 스택으로 구현하기 위해서는 배열과 다르게 shift(), unshift()로 구현하는것이 좋다. 단일 연결 리스트는 인덱스가 없기 때문에 마지막에 노드를 제거하기 위해서는 테일 노드의 직전 노드를 찾기위해 헤드 노드부터 시작해서 찾아가야 하므로 O(N) 시간 복잡도를 갖게 되므로 연결 리스트의 맨 앞에 노드를 추가하고 제거하는 방식으로 스택을 구현하는 것이 더 효율적이다.

class Stack {
    constructor(){
        this.first = null;
        this.last = null;
        this.size = 0;
    }
    unshift(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;
    }
    shift(){ // 맨 앞에 노드 추가
        if(!this.first) return null; //노드가 없는지 확인
        var temp = this.first;
        if(this.first === this.last){ //노드가 하나인지 확인
            this.last = null;
        }
        this.first = this.first.next; //값이 하나라면 애초에 next는 null이므로
        // 위에서는 노드가 하나인지 확인하는 과정에서는 last만 바꿔주면 됨
        this.size--;
        return temp.value;
    }
}

15.4 큐(Queue)

  큐도 스택과 마찬가지로 데이터 구조로서 데이터를 추가하고 제거한다. 그렇지만 스택과는 다르게 선입선출 방식이다. 즉, 먼저 들어간 것이 먼저 나게 된다. 에버랜드 입장을 위해 줄 서 있는것을 생각하면 이해하기 쉽다. 스택과 마찬가지로 배열을 이용해서 큐를 구현할 수 있고 또는 자체적으로 큐를 구현할 수도 있다. 큐에서는 보통 데이터를 추가하기 위해 사용되는 키워드를 enqueue, 데이터를 제거하기 위해 사용하는 키워드를 dequeue라고 한다. 

 

※배열의 메서드를 이용하여 스택&큐 구현 정리

스택(후입선출)	큐(선입선출)
push() & pop()	push() & shift()
shift() & unshift()	unshift() & pop()

15.5 단일 연결 리스트로 큐 작성하기

  단일 연결 리스트로 큐를 구현하려면 배열의 push() & shift() 메서드처럼 기능을 구현하는것이 좋다. 왜냐하면 단일 연결 리스트의 경우 뒤에서 제거를 하려면 헤드 노드부터 타고 들어가야 하므로 시간이 오래 걸리기 때문이다. 큐는 엄청 큰 데이터를 가지더라도 상관없다. 인덱스가 없으므로 모든 명령이 상수값을 가지게 되므로 전혀 문제가 없다. 가장 뒤에 넣고, 가장 앞에서 제거하므로 배열이 길어져도 항상 O(1) 시간 복잡도를 갖는다. 스택과의 차이는 후입선출이냐 선입선출이냐의 차이이고 코드 구현 방식은 거의 동일하다. 

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

class Queue {
    constructor(){
        this.first = null;
        this.last = null;
        this.size = 0;
    }
    enqueue(val){ //push 역할을 함
        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(){ //shift 역할을 함
        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;
    }
}