큐

큐

---

끝부분으로 데이터가 삽입, 앞부분으로는 데이터가 삭제되는 자료구조.
선입선출(FIFO)

 

용도

---

운영체제의 프로세스 처리순서, 프린트 목록, 대기줄 선착순

 

 

추상적인 데이터형

---

enqueue : 큐의 끝부분에 요소를 추가하는 함수

dequeue : 큐의 앞부분에서 요소를 삭제하는 함수

clear : 큐에서 모든 요소를 삭제하는 함수

front : 큐의 앞부분에 저장된 요소를 반환 (내용만 확인)

back : 큐의 끝부분에 저장된 요소를 반환 (내용만 확인)

empty : 큐의 요소가 있는지 여부를 반환하는 함수

toString : 큐의 모든 요소를 문자열로 변환해 반환하는 함수

 

* JS 배열에서 사용할 수 있는 함수

push() : 배열의 끝부분에 데이터를 추가하는 함수

shift() : 배열의 앞부분에 데이터를 삭제하는 함수

 

 

JS 큐 구현

---

1

//큐 생성자 함수
function Queue() {
    this.dataStore = []; 
    this.enqueue = enqueue;
    this.dequeue = dequeue;
    this.front = front;
    this.back = back;
    this.toString = toString;
    this.empty = empty;
}

//enqueue
//큐의 끝부분에 요소를 추가
function enqueue(element) {
    this.dataStore.push(element);
}

//dequeue
//큐의 앞부분에서 요소를 삭제
function dequeue() {
    return this.dataStore.shift();
}

//front
//큐의 앞부분에 저장된 요소 확인
function front() {
    return this.dataStore[0];
}

//back
//큐의 끝부분에 저장된 요소 확인
function back() {
    return this.dataStore[this.dataStore.length-1];
}

//toString
//큐의 모든 요소를 출력
function toString() {
    var retStr = "";
    for (var i = 0;i < this.dataStore.length; ++i )    {
        retStr += this.dataStore[i] + "\n";
    }
    return retStr;
}

//empty
//큐가 비어있는지 여부 확인
function empty() {
    if (this.dataStore.length == 0) {
        return true;
    } else {
        return false;
    }
}


//테스트
var q = new Queue();
q.enqueue("첫번째");
q.enqueue("두번째");
q.enqueue("셋번째");
print(q.toString());
q.dequeue();
print(q.toString());
print("Front of queue: " + q.front());
print("Back of queue: " + q.back());


function print(v) {
    document.write(v+"<br/>");
    //console.log(v);
} 

seagull-dev.tistory.com/14

 

2

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

// 출처 - 제로초
// https://www.zerocho.com/category/Algorithm/post/580b9b94108f510015524097

 

예제는 일반적인 큐지만, 특수한 형태의 큐 두가지가 있다.

 

1. 순환 큐 

front와 rear이 연결되어 있다. 아래를 추가해주면 된다. 메모리 관리가 쉬워서 사용하나 JS는 메모리 관리가 자동이라 효용성이 떨어진다.

this.rear.next = this.front

 

 

2. 우선순위 큐

enqueue 시 제일 뒤가 아니라 우선순위를 따져서 데이터를 넣는다. 단점은 데이터 삽입이 어렵다는 것인데 단점은 힙이라는 자료구조를 사용해서 보완한다. 힙을 이해하려면 자료구조 트리와 함께 공부하면 좋다. 

 

트리 :  나무의 뿌리같이 생긴 자료구조. 제일 첫번째 노드는 root이며, 제일 마지막 노드는 leaf라고 부른다. 그 둘을 제외한 노드들은 내부 노드라고 퉁쳐 부른다. 실생활에서 대진표 등에 사용된다.

힙 :  트리의 일종. 최대힙은 완전 트리이면서 Root가 모든 자식들보다 커야하며, 최소힙은 Root가 자식보다 작은 것. 

완전 트리 : 노드가 순서대로 들어있는 트리

 

 

소스 출처

www.zerocho.com/category/Algorithm/post/580b9b94108f510015524097