자바스크립트로 큐(Queue) 구현하기

2021년 06월 29일

자바스크립트로 큐 구현하기

배열로 큐 구현하기

class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }
  enqueue(value) {
    this.queue[this.rear++] = value;
  }

  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front += 1;
    return value;
  }

  peek() {
    return this.queue[this.front];
  }

  size() {
    return this.rear - this.front;
  }
}

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(3);
queue.enqueue(5);
queue.dequeue();
console.log(queue);

최근에 큐를 다시 공부하다가 알게 된 사실이 있다.

배열로 구현한 큐에서 dequeue 연산을 할 때, shift()로 구현하는 것은 자바스크립트 배열에서 shift()가 O(n)의 시간 복잡도를 가진다. 그래서 본래 큐에서 기대하는 로직이 수행되지 않기 때문에 잘못된 것이다.

위의 코드처럼 로직을 짜는 것이 맞다.

연결 리스트로 큐 구현하기

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

class Queue {
    constructor(){
        this.head = null;
        this.tail = null;
        this.siz = 0;
    }
    
    enqueue(newValue){
        const newNode = new Node(newValue);
        if(this.head === null) {
            this.head = this.tail = newNode;
        } else {
            this.tail.next = newNode;
            this.tail = newNode;
        }
        this.size += 1;
    }
    
    dequeue(){
        const value = this.head.value;
        this.head = this.head.next;
        this.size -= 1;
        return value;
    }
    
    peek(){
        return this.head.value;
    }
}