큐(Queue)란?

가게 앞에서 기다리는 손님들이 먼저온 사람부터 선착순으로 들어가는 것처럼,
데이터를 넣은 순서대로 꺼내는 자료구조이다.

먼저 입력한 데이터가 먼저 출력되는 FIFO(First In, First Out) 또는 LILO(Last In, Last Out) 방식으로 관리된다.

인터페이스

items - 데이터 목록
enqueue(data) - 큐의 마지막에 데이터를 추가한다.
dequeue() - 큐의 첫번째 데이터를 반환하고, 해당 데이터는 큐에서 삭제한다.
front() - 큐의 첫번째 데이터를 반환하되 큐는 변경하지 않는다.
isEmpty() - 큐가 비었는지 확인한다.
size() - 큐에 있는 데이터의 갯수를 반환한다.

구현 - JavaScript에서의 큐

큐는 데이터의 삽입/삭제 작업이 많으므로 일반적인 언어라면 삽입/삭제가 효율적인 리스트로 구현하는게 좋지만,
JavaScript의 배열은 연관배열로 구현되어있으므로 배열로 구현해도 괜찮다.

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

  get items() {
    return this._items;
  }

  enqueue(item) {
    this._items.push(item);
  }

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

  front() {
    return this._items[0];
  }

  isEmpty() {
    return this._items.length <= 0;
  }

  size() {
    return this._items.length;
  }
}

// Test
it("Queue 클래스는 잘 동작한다.", () => {
  const queue = new Queue();

  queue.enqueue("Qus");
  queue.enqueue("Tom");
  queue.enqueue("Jackson");

  expect(queue.items).toEqual(["Qus", "Tom", "Jackson"]);
  expect(queue.size()).toEqual(3);

  const result1 = queue.dequeue();
  expect(result1).toEqual("Qus");
  expect(queue.items).toEqual(["Tom", "Jackson"]);

  const result2 = queue.front();
  expect(result2).toEqual("Tom");

  expect(queue.isEmpty()).toEqual(false);

  const result3 = queue.dequeue();
  expect(result3).toEqual("Tom");
  expect(queue.items).toEqual(["Jackson"]);

  expect(queue.size()).toEqual(1);

  queue.dequeue();
  expect(queue.isEmpty()).toEqual(true);
});

활용 사례

인쇄 대기열, 그래프의 너비우선탐색(BFS)의 탐색대기목록 등

확장 - 우선순위 큐 Priority Queue

우선순위가 높은 데이터부터 추가/삭제 되는 HIFO(Highest In, First Out)구조의 큐이다.
Queue에서 데이터를 추가(enqueue)할때 우선순위를 고려하여 넣든가, 데이터를 추출(dequeue)할때 우선순위를 고려해서 빼든가 둘 중하나를 수정해서 구현하면 된다.

class PriorityQueueItem {
  constructor(element, priority) {
    this._element = element;
    this._priority = priority;
  }

  get element() {
    return this._element;
  }

  get priority() {
    return this._priority;
  }
}

/**
 * 데이터를 추가(enqueue)할때 우선순위를 고려하도록 구현.
 * 위에서 만든 Queue 클래스를 상속하여 수정이 필요한 메서드만 override.
 */
class PriorityQueue extends Queue {
  enqueue(element, priority) {
    // 숫자가 작을 수록 높은 우선순위
    const item = new PriorityQueueItem(element, priority);

    if (this._items.length <= 0) {
      this._items.push(item);
    } else {
      const itemToBeat = this._items.find((val, index) => {
        return val.priority > item.priority;
      });

      if (itemToBeat) {
        const index = this._items.indexOf(itemToBeat);
        const head = index === 0 ? [] : this._items.slice(0, index - 1);
        const tail = this._items.slice(index);
        this._items = [...head, item, ...tail];
      } else {
        this._items.push(item);
      }
    }
  }

  front() {
    return this._items[0] ? this._items[0].element : null;
  }

  dequeue() {
    const result = this._items.shift();

    return result ? result.element : null;
  }
}

// Test
it("PriorityQueue 클래스는 잘 동작한다.", () => {
  const queue = new PriorityQueue();

  queue.enqueue("Qus", 4);
  queue.enqueue("Tom", 3);
  queue.enqueue("Jackson", 2);

  expect(queue.front()).toEqual("Jackson");
  expect(queue.dequeue()).toEqual("Jackson");

  queue.enqueue("Paul", 5);
  queue.enqueue("Penny", 1);

  const expected = [
    { _element: "Penny", _priority: 1 },
    { _element: "Tom", _priority: 3 },
    { _element: "Qus", _priority: 4 },
    { _element: "Paul", _priority: 5 },
  ];
  expect(queue.items).toEqual(expected);
});

아디트야 바르가바, 『Hello Coding 그림으로 개념을 이해하는 알고리즘』, 김도형, 한빛미디어(2017)
스기우라 켄, 『그림으로 배우는 알고리즘』, 서재원, 영진(2016)
이소 히로시, 『모던 자바스크립트 입문』, 서재원, 길벗(2018)
Martin Erwig, 『그들은 알고리즘을 알았을까?』, 송원형, 영진(2017)
Loiane Groner, 『자바스크립트 자료 구조와 알고리즘』, 이일웅, PACKT-에이콘(2015)

큐(Queue)란 무엇인가

큐(Queue)란?

인터페이스

구현 - JavaScript에서의 큐

활용 사례

확장 - 우선순위 큐 Priority Queue

스택(Stack)이란 무엇인가

연결리스트(Linked List)란 무엇인가