(JS 자료구조)스택(Stack)과 큐(Queue)

스택(Stack)

• 스택은 LIFO(Last In Fisrt Out, 후입선출) 자료구조이다. 스택에서는 마지막으로 추가된 요소가 제일 먼저 제거된다.
• 배열에서 push 메서드와 pop 메서드를 사용하여 스택 자료구조를 만들 수 있다. 또는 별도의 클래스로 자신만의 스택 자료구조를 만들 수도 있다.

기본 구조

• 기본 구조는 연결리스트에서 했던 것처럼 Node 클래스를 활용하고, Stack 클래스의 constructor에는 first, last, size 프로퍼티를 둔다. 연결 리스트의 일종이라고 볼 수 있다.
• push와 pop 메서드를 만들 때, 연결 리스트에서 만들었던 메서드를 활용하면 되는데, 그 중 O(1) 시간복잡도를 가지는 shift와 unshift 메서드를 활용한다. 리스트의 제일 앞에 추가하고 제일 앞의 것을 제거하는 형태이지만, 결과적으로 스택 자료구조이다.

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

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

Stack class 작성

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

    push(val){
        let newNode = new Node(val);
        if(!this.first){
            this.first = newNode;
            this.last = newNode;
        }else{
            let temp = this.first;
            this.first = newNode;
            this.first.next = temp;
        }
        return ++this.size;
    }

    pop(){
        if(!this.first) return undefined;

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

Stack의 성능

시간 복잡도

• 삽입 : O(1)
• 제거 : O(1)
• 탐색 : O(N)
• 접근 : O(N)

결론

• 스택은 후입선출의 특성을 갖는 자료구조다.
• 함수 호출의 Call Stack이나 실행취소(Ctrl+Z)나 재귀의 작동방식 등이 스택이다.
• 스택은 자바스크립트에 내장된 자료구조가 아니지만 간단한 스택을 코딩하기에 어렵지는 않다.
• 스택을 이용하여 탐색, 접근하는 것이 중요하다면 배열이나 다른 자료구조를 활용하는 것이 낫다. 다만, 아주 많은 데이터에 대하여 삽입과 제거를 위주로 작업한다면, 스택 자료구조가 적합할 수 있다.

큐(Queue)

• 큐는 FIFO(First In First Out, 선입선출) 구조다. 놀이공원 줄 서기를 생각하면 된다.
• 배열을 활용한다면, unshift와 pop 메서드나 push와 shift 메서드 조합을 사용하는 것이 큐의 작동방식과 같다. 하지만 unshift 메서드를 써서 데이터를 추가할 때마다 전체 배열에 인덱스를 다시 부여해야 하므로 성능이 좋지 않다. 그래서 성능을 신경써야 하는 경우라면, 직접 큐 클래스를 만드는 것이 낫다.

기본 구조

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

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

Queue class 작성

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

    enqueue(val){ //push(val) 처럼 맨 뒤에 노드 추가
        let qNode = new Node(val);
        if(!this.first){
            this.first = qNode;
            this.last = qNode;
        }else{
            this.last.next = qNode;
            this.last = qNode;
        }
        return ++this.size;
    }

    dequeue(){ //shift()처럼 맨 앞에서 노드 제거 후 반환
        if(!this.first) return null;

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

Queue 성능

시간복잡도

• 삽입 : O(1)
• 제거 : O(1)
• 탐색 : O(N)
• 접근 : O(N)

결론

• 큐는 FIFO(선입선출) 자료구조다.
• 큐에서는 삽입과 제거가 중요하며, O(1)을 가진다.