[알고리즘] 큐 - Queue

2. 큐(Queue)

---

참고

스택과 같이 큐는 같은 선형적 구조는 특정한 순서를 따릅니다.
순서는 FIFO(First In First Out) 선입선출입니다.

출처: https://devowen.com/211

스택과 큐의 차이점은 제거에 있습니다.

스택은 가장 최근에 추가된 데이터를 제거하지만, 큐는 가장 처음에 들어왔던 데이터를 삭제한다.

스택은 가장 마지막에 쌓인 데이터를 제거하고 큐는 가장 앞에 추가된 데이터를 삭제한다.

큐의 동작

• Enqueue: 큐에 데이터를 추가한다. 만약 큐가 꽉 찼을 때, Overflow condition이 된다.
• Dequeue: 큐에서 데이터를 제거한다. 데이터는 들어온 순서대로 빠져나온다. 만약 큐가 비어져 있을 경우, Underflow condition이 된다.
• Front: 큐의 앞부분의 데이터를 가진다.
• Rear: 큐의 뒷부분의 데이터를 가진다.

이미지를 함께 보시면, 위에서 이야기한 큐의 4가지 기본 작업에 대해 표현하고 있습니다.

스택에서는 제일 위를 가리키는 top이 있다면,

큐에는 맨 처음을 가리키는 head와 맨 끝을 가리키는 rear, 두 개가 있습니다.

큐의 종류

큐를 구현하기 위해서, 우리는 두 가지 지표를 추적해야 합니다. - front(머리)와 rear(꼬리)

1. 순환 큐

여기에 대한 방법으로는 front와 rear를 circular Queue(순환 큐)(으)로 증가시켜주는 방법이 있습니다.

front와 rear가 연결되어 있는데요, 원래 1, 2, 3의 큐에선 3에서 끝나지만,

순환 큐는 rear인 3에서 다시 front인 1로 넘어갑니다.

this.rear.next = this.front

순환 큐가 사용되는 이유는 메모리 관리 측면인데,

자바스크립트에서는 메모리를 알아서 정리해주기 때문에, 효용성이 조금 떨어진다고 합니다!

2. 우선순위 큐

우선순위 큐는 enqueue와 dequeue는 같지만,

enqueue 할 때, 제일 뒤에 넣는 것이 아닌, 우선순위를 따져 데이터를 넣습니다.

우선순위는 프로그래머가 직접 정해주면 됩니다.

다만, 우선순위 큐의 문제로, 보통 큐와 같이 구현하면 데이터를 삽입하기 힘들다는 단점이 있어,

주로 힙이라는 자료구조를 사용해서 구한다고 합니다.

큐 구현하기

var Queue = (function() {
  function Queue() {
    this.count = 0;
    this.head = null;
    this.rear = null;
  }
  function Node(data) {
    this.data = data;
    this.next = null;
  }
  Queue.prototype.enqueue = function(data) {
    var node = new Node(data);
    if (!this.head) {
      this.head = node;
    } else {
      this.rear.next = node;
    }
    this.rear = node;
    return ++this.count;
  };
  Queue.prototype.dequeue = function() {
    if (!this.head) { // stack underflow 방지
      return false;
    }
    var data = this.head.data;
    this.head = this.head.next;
    // this.head 메모리 클린
    --this.count;
    return data;
  };
  Queue.prototype.front = function() {
    return this.head && this.head.data;
  };
  return Queue;
})();

큐 호출하기

var queue = new Queue();
queue.enqueue(1); // 1
queue.enqueue(3); // 2
queue.enqueue(5); // 3
queue.dequeue(); // 1
queue.front(); // 3

큐의 시간 복잡도

Enqueue (insertion) : O(1)

Dequeue (deletion) : O(1)

Front (Get front) : O(1)

Rear (Get Rear) : O(1)

보조 공간: input size를 고려하여 알고리즘이 문제를 해결하기 위해 임시로 사용하는 공간

: O(N)

배열로 큐를 구현할 때의 장단점

장점: 구현하기 쉽다.

단점: 사이즈가 고정되어 있다 (정적인 데이터 구조)

만약에 enqueue와 dequeue로 큐가 큰 숫자를 가졌다면, 큐가 비어있더라도 큐에 요소를 삽입하지 못할 수 있다. (순환 큐로 대처할 수 있다)

링크드리스트로 큐를 구현하는 게 더 쉽다.