큐

큐는 FIFO(First In First Out) 먼저 들어가 데이터가 먼저 나오는 형식의 자료구조입니다. 순서를 지키기 때문에 주로 버퍼에 사용됩니다. 다들 아시는 내용이니 바로 구현을 해보죠.

배열을 활용한 구현

// 배열을 이용한 큐

class Queue {
  constructor() {
    this.store = [];
  }

  enqueue(data) {
    this.store.push(data);
  }

  dequeue() {
    return this.store.shift();
  }
}

const queue = new Queue();

queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

queue.dequeue();

queue.enqueue(4);
queue.dequeue();

console.log(queue); // [3, 4]

그런데 배열을 활용해 큐를 구현하게 되면 문제점이 있습니다. shift() 메소드는 맨 앞에 인자를 제거할 때 모든 배열 인자의 인덱스를 재조정하기 때문에 시간복잡도를 O(n)만큼 가지게 되죠. 따라서 Linked List로 구현하는 것이 좋습니다. (스택은 상관없습니다. push pop 메소드의 작동방식을 떠올려보세요.)

Linked List를 활용한 Queue

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

class Queue {
  constructor() {
    this.head = null;
  }

  enqueue(data) {
    const node = new Node(data);

    if (!this.head) {
      this.head = node;
    } else {
      let tmp = this.head;

      while (tmp.next) {
        tmp = tmp.next;
      }

      tmp.next = node;
    }
  }

  dequeue() {
    const tmp = this.head;
    this.head = this.head.next;

    return tmp;
  }
}

const queue = new Queue();

queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5);
queue.enqueue(6);
queue.enqueue(7);

queue.dequeue();
queue.dequeue();

console.log(queue.head); // 3 -> 4 -> 5 -> 6 -> 7

스택

스택은 LIFO(Last In First Out)로 마지막에 들어간 데이터가 가장 먼저 나오는 자료 구조입니다. 자바스크립트의 동작 방식에서 빼놓을 수 없는 콜 스택에 스택이 사용되죠.

구현

class Stack {
  constructor() {
    this.store = [];
  }

  push(data) {
    this.store.push(data);
  }

  pop(data) {
    this.store.pop();
  }
}

const stack = new Stack();

stack.push(1);
stack.push(2);
stack.push(3);
stack.pop();
console.log(stack); // [1, 2]