[JavaScript] Queue 구현 및 시간 복잡도

✏️ JS에서 Stack. Queue의 시간 복잡도

흔히 알고있는 stack, queue를 JS에서 사용하려고 할 때, 보통 다음과 같이 사용한다.

const stack = [];
stack.push(1);
stack.push(2);
console.log(stack[stack.length - 1]);
stack.pop();

const queue = [];
queue.push(1);
queue.push(2);
console.log(queue[queue.length - 1]);
queue.shift();

Stack의 경우 psuh, pop을 사용하고, Queue의 경우 push, shift을 사용한다.

 

하지만 최근에 알게 된 사실인데, shift 메소드의 경우 최악일때는 O(n)의 복잡도를 가진다.

(push, pop은 O(1)의 시간복잡도를 가진다.)

 

요소가 적은 경우 자바스크립트 엔진이 어느정도 최적화를 해주긴 하지만, 최악의 경우(n)의 복잡도를

가지기 때문에 JS에서 Queue를 사용할려면 직접 구현해서 사용해야한다.

(JS는 Queue 내장함수가 없어서 직접 구현해서 사용해야한다.ㅠㅠ)

개발 멘토님이 만약 N이 1,000 이하라면 shift를 사용해도 무방하다고 하셨다.

 

지금까지 많은 알고리즘을 해결하면서 그냥 간단하게 push, shift를 사용했는데 왜 시간초과가 났는지

이제서야 알 것 같다.

 

JS로 Queue 구현 정리를 잘 해놓은 블로그를 발견해서 가져왔다. Queue를 사용할 경우가 생기면 다음 코드를 이용하면 된다. 해당 알고리즘은 Linked List를 활용하여 Queue를 구현하였다.

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

// 큐 클래스
class Queue {
  constructor() {
    this.head = null; // 제일 앞 노드
    this.rear = null; // 제일 뒤 노드
    this.length = 0; // 노드의 길이
  }

  enqueue(data) {
    // 노드 추가.
    const node = new Node(data); // data를 가진 node를 만들어준다.
    if (!this.head) {
      // 헤드가 없을 경우 head를 해당 노드로
      this.head = node;
    } else {
      this.rear.next = node; // 아닐 경우 마지막의 다음 노드로
    }
    this.rear = node; // 마지막을 해당 노드로 한다.
    this.length++;
  }

  dequeue() {
    // 노드 삭제.
    if (!this.head) {
      // 헤드가 없으면 한 개도 없는 것이므로 false를 반환.
      return false;
    }
    const data = this.head.data; // head를 head의 다음 것으로 바꿔주고 뺀 data를 return
    this.head = this.head.next;
    this.length--;

    return data;
  }
  // head를 반환하는 함수
  front() {
    // head가 있을 경우 head의 data를 반환.
    return this.head && this.head.data;
  }
  //큐의 모든 원소를 반환하는 함수
  getQueue() {
    if (!this.head) return false;
    let node = this.head;
    const array = [];
    while (node) {
      // node가 없을 때까지 array에 추가한 후 반환해준다.
      array.push(node.data);
      node = node.next;
    }
    return array;
  }
}

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
queue.dequeue();
console.log(queue.front());
console.log(queue.dequeue());
console.log(queue.getQueue());

 

 

📃 참고 사이트

Queue 알고리즘

https://velog.io/@ansrjsdn/JS-Queue-%EA%B5%AC%ED%98%84%ED%95%B4%EB%B3%B4%EA%B8%B0

Queue시간복잡도

https://stackoverflow.com/questions/22614237/javascript-runtime-complexity-of-array-functions/22615787