(data-structure) 자료구조 (큐, queue)

큐는 실생활에서 흔히 볼 수 있는 대기열이라고 생각하면 편하다 페스트 푸드점에서 주문을 하려고 해도, 먼저 온 사람 순으로 주문을 하게 된다 .이렇게 뒤에서 들어가고(enqueue) 앞에서 빠지는(dequeue) 구조이다. 자바스크립트의 배열로 따지면 push(enqueue)와 shift(dequeue) 메소드만 있는 것이라 생각하면 편하다.

추가로 제일 앞의 데이터를 알 수 있는 front가 있다.

스택에는 제일 위를 가리키는 Top만 있었다면 큐에는 맨 처음을 가리키는 head와 맨 끝을 가리키는 rear 두개가 있다.

특수한 큐도 있습니다. 순환 큐가 그 중 하나인데, front와 rear가 연결되어 있다. 예를 들면 1, 2, 3의 데이터가 들어가는 큐가 있을 때 원래라면 3에서 끝나지만, 순환 큐는 rear인 3에서 다시 front인 1로 넘어간다.

코딩은 그냥 this.rear.next = this.front를 추가해주면 구현할 수 있다. 순환 큐가 사용되는 이유는 메모리 관리가 쉽기 때문인데 자바스크립트에서는 메모리를 알아서 정리해주기 때문에 그 효용성이 조금 떨어진다.

또 다른 큐로는 우선순위 큐가 있다. enqueue, dequeque는 같지만, 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 = functuon() {
    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

출처

자료구조(큐, queue) 제로초 블로그