Published on

[자료구조] javascript 큐 (Queue)

Authors
  • avatar
    Name
    piano cat
    Twitter

javascript 에서 큐 자료구조 생성, 추가, 삭제 할때 소요되는 시간을 빅오 표기법으로 확인해보자

queue

큐는 선입선출(FIFO, First In First Out)의 구조이다.

javascript 에서 큐의 구현은 클래스로 배열과 연결리스트를 이용하여 구현할 수 있다.

하지만 배열로 구성할경우 인덱스가 계속 늘어나기때문에 연결리스트로 구현을 하는게 좋아 보입니다.

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

class Queue {
  constructor(){
    this.head = null;
    this.tail = null;
    this.size = 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;
  }
}

큐은 추가, 삭제가 일어날때 O(1)의 시간복잡도가 소요된다.

활용 예시

자원의 공유, 프린터 출력, 작업 예약 등의 알고리즘, BFS(Breadth-First Search) 등

  • 자원의 공유: 여러 프로세스가 자원을 공유할 때 사용됨
  • 작업 예약: 작업 예약을 할 때 사용됨
  • 프린터 출력 : 가장 먼저 대기열에 오른 프린트가 먼저 출력됨
  • BFS(Breadth-First Search): 너비 우선 탐색 알고리즘에서 사용됨
Discuss on Twitter • View on GitHub