큐(Queue)

큐(Queue)

- FIFO(First In First Out) 으로 데이터를 저장하는 구조입니다.

- 먼저 들어온 데이터가 먼저 나갑니다.

- 주요 동작 : enqueue, dequeue, peekFront

- enqueue(데이터) : 큐에 데이터 추가

- dequeue( ) : 큐의 가장 앞에 있는 데이터 제거 후 반환

- peekFront : 큐의 가장 앞에 있는 데이터 반환

JavaScript 로 Queue 구현(feat.Linked List)

dequeue 메서드 구현 시 array 가 제공하는 shift() 메서드를 사용하면 간단하게 구현 가능하겠지만, shift() 메서드는 시간 복잡도가 O(n) 이므로 Queue 구현에 적합하지 않습니다.

시간 복잡도를 O(1)으로 하기 위해 연결 리스트(Linked List) 를 통해 구현해 보았습니다.

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

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
  }
  
  isEmpty() {
    return this.front == null && this.rear == null;
  }
  
  enqueue(data) {
    const newNode = new Node(data);
    if (this.isEmpty()) this.front = newNode;
    else this.rear.next = newNode;
    
    this.rear = newNode;
  }
  
  dequeue() {
    if (this.isEmpty()) return;
    this.front = this.front.next;
    if (!this.front) this.rear == null;
  }
  
  peekFront() {
    if (this.isEmpty()) return null;
    return this.front.data;
  }
}

큐의 시간 복잡도

삽입 : 큐에 들어가 있는 값들이 무수히 많아도 데이터 삽입은 한 번 일어나기 때문에 시간 복잡도는 O(1) 이 됩니다.

삭제 : FIFO 에 따라 삭제 시 첫 번째 데이터(front)가 삭제되므로 큐의 크기에 상관없이 시간 복잡도는 O(1) 이 됩니다.

접근 : 큐의 특성상 한쪽 끝(rear)으로만 자료를 넣고 뺄 때는 첫 번째 데이터(front)가 빠지게 되는 자료구조이므로 데이터 접근 또한 첫 번째 데이터(front)를 통해서만 접근이 가능합니다. 따라서 n번 째 접근은 첫 번째 데이터(front) 부터 순회하기 때문에 O(n)의 시간 복잡도를 가집니다.

탐색 : 데이터를 찾을 때 만약 큐의 첫 번째 데이터(front)를 찾는다면 시간 복잡도는 O(1) 입니다. 하지만 가장 뒤에 있는 데이터(rear)를 찾는다면 데이터의 개수만큼 작업이 발생되므로 O(n)의 시간 복잡도를 가집니다.

시간 복잡도	삽입	삭제	접근	n번째 접근	탐색
큐	O(1)	O(1)	O(1)	O(n)	O(n)

큐의 사용 사례

- 자바스크립트 엔진에서 비동기 함수 실행 시 콜백들이 대기열로 들어오는 Task queue 가 대표적입니다.

- 순서대로 처리해야 하는 작업을 임시로 저장해두는 버퍼(buffer) 로서 많이 사용됩니다.

- 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용됩니다.