티스토리 뷰

 

간단한 구현 : 

javascript로 큐를 간단히 구현하려면 배열, push() 함수 (enqueue), shift() 함수 (dequeue)를 이용하면 된다.

 

그런데 shift() 함수의 시간 복잡도는 O(n)으로 다소 비효율적일 수 있다.

 

온라인 저지 사이트에서 javascript로 문제 풀다가 큐 때문에 시간 초과가 나면 아래처럼 바꿔보자.

 

 

 

효율적인 구현 : 

offset 변수를 추가로 이용해서 배열에서 dequeue 될 요소에 바로 접근한다 O(1)

 

만약 offset이 큐 길이 2배 이상이 되면 앞 부분을 자르고 (이미 dequeue 된 요소들),

offset은 0으로 초기화한다.

 

(내가 구현한 것 아님. 맨 아래 출처 참고 바랍니다.)

function Queue(){

  // initialise the queue and offset
  var queue  = [];
  var offset = 0;

  // Returns the length of the queue.
  this.getLength = function(){
    return (queue.length - offset);
  }

  // Returns true if the queue is empty, and false otherwise.
  this.isEmpty = function(){
    return (queue.length == 0);
  }

  /* Enqueues the specified item. The parameter is:
   *
   * item - the item to enqueue
   */
  this.enqueue = function(item){
    queue.push(item);
  }

  /* Dequeues an item and returns it. If the queue is empty, the value
   * 'undefined' is returned.
   */
  this.dequeue = function(){

    // if the queue is empty, return immediately
    if (queue.length == 0) return undefined;

    // store the item at the front of the queue
    var item = queue[offset];

    // increment the offset and remove the free space if necessary
    if (++ offset * 2 >= queue.length){
      queue  = queue.slice(offset);
      offset = 0;
    }

    // return the dequeued item
    return item;

  }

  /* Returns the item at the front of the queue (without dequeuing it). If the
   * queue is empty then undefined is returned.
   */
  this.peek = function(){
    return (queue.length > 0 ? queue[offset] : undefined);
  }

}

 

 

 

같은 코드 짧은 버전 : 

function Queue(){
  var a=[],b=0;
  this.getLength=function(){return a.length-b};
  this.isEmpty=function(){return 0==a.length};
  this.enqueue=function(b){a.push(b)};
  this.dequeue=function(){if(0!=a.length){
      var c=a[b];
      2*++b>=a.length&&(a=a.slice(b),b=0);
      return c}};
  this.peek=function(){return 0<a.length?a[b]:void 0}
};

 

 

 

출처 : code.iamkate.com/javascript/queues/

'시리즈 > Javascript' 카테고리의 다른 글

정규표현식 예제  (0) 2021.02.20
Map and Set  (0) 2021.02.20
String.prototype.replace() 함수  (0) 2021.01.22
javascript 팁  (0) 2021.01.21
javascript 콘솔 입출력  (0) 2021.01.21
댓글
공지사항
최근에 올라온 글