스택(stack)과 큐(Queue)

1. 스택(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;
    }
}

Push 메서드

• 연결리스트에서 살펴본 unshift 메서드의 로직을 활용한다.
  • 노드를 리스트의 가장 앞에 추가한다.

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

Pop 메서드

• 연결리스트에서 살펴본 shift 메서드의 로직을 활용한다.
  • 리스트의 가장 앞에 있는 노드를 제거한다.

  pop() {
    if (!this.first) return null;
    const temp = this.first;
    if (this.first === this.last) {
      this.last = null;
    }
    this.first = this.first.next;
    this.size--;
    return temp.value;
  }

스택의 성능 - 시간복잡도

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

결론

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

2. 큐(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;
  }
}

enqueue 메서드

• push처럼 노드를 제일 뒤에 추가한다.(시간복잡도 O(1))

  enqueue(val) {
    const 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처럼 제일 앞 노드를 제거하고 반환한다.(시간복잡도 O(1))

  dequeue() {
    if (!this.first) return null;

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

큐 성능 - 시간복잡도

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

결론

• 큐는 FIFO(선입선출) 자료구조다.
• 큐에서는 삽입과 제거가 중요하며, 이들은 O(1)으로서 빠르다. 탐색과 접근은 큐에서 실제로 잘 사용하지 않는 기능이다.