[JS] 자료구조 큐(Queue) 구현의 필요성

 

1. 스택 (Stack)

스택(Stack)은 FILO(first in, last out) 알고리즘으로 JS에서 제공되는 push(), pop() 메서드를 사용합니다.

배열의 탐색이 필요 없기 때문에 시간 복잡도 O(1) 이므로 별도 알고리즘을 구현할 필요가 없습니다.

const stack = [];

stack.push("dog");
stack.push("cat");
stack.push("bear");
document.write("storage : " + stack, '<br/>'); 
//storage ["dog", "cat", "bear"]

stack.pop(); //"bear"
document.write("storage : " + stack, '<br/>'); 
//storage ["dog", "cat"]

---

2. 큐( Queue)

하지만 큐는 상황이 다릅니다.

FIFO(first In, first Out) 알고리즘으로 JS에서 제공되는 push(), shift() 메서드를 사용 가능합니다.

shift() 메서드의 경우 배열의 탐색이 필요하므로 최대 시간 복잡도 O(N)입니다.

(자바스크립트 배열은 해시 테이블로 구현된 객체이기 때문임)

따라서 데이터량이 많아질수록 런타임(Runtime)에 영향이 있을 수 있습니다.

const queue = [];

//enqueue
queue.push("seahorse");
queue.push("dolphin");
queue.push("whale shark");
document.write("storage : " + queue, '<br/>'); 
//storage ["seahorse", "dolphin", "whale shark"]

//dequeue
queue.shift();
document.write("storage : " + queue, '<br/>'); 
//storage ["dolphin", "whale shark"]

일반적으로 데이터 1,000 건 이하는 shift() 메서드를 사용해도 무방합니다.

1,000건이 초과되는 경우 아래의 예제와 같이 Queue 알고리즘을 구현하여 사용하는 것이 좋습니다.

class Queue {
  constructor() {
    this.storage = {}
    this.head= 0
    this.tail = 0
  }
  enqueue(element) {
    this.storage[this.tail] = element
    this.tail++
  }

  dequeue() {
    let removed = this.storage[this.head]
    delete this.storage[this.head]
    this.head++
    return removed
  }

  print() {
    var data = ""
    var n = this.head

    while(this.tail > n){
      data = data + this.storage[n] + ", "
      n++
    }    
    return data
  }
}

const queue = new Queue();

//enqueue
queue.enqueue('seahorse');
queue.enqueue('dolphin');
queue.enqueue('whale shark');
document.write("queue : " + queue.print(), '<br/>'); 
// Queue { storage: { '0' : 'seahorse' , '1' : 'dolphin', '2' : 'whale shark' }, head: 0, tail: 3 }

//dequeue
queue.dequeue(); //'seahorse'
document.write("queue : " + queue.print(), '<br/>');
// Queue { storage: { '1' : 'dolphin', '2' : 'whale shark' }, head: 1, tail: 3 }

 

레퍼런스 

유튜브 : beiatrix

https://stackoverflow.com/questions/22614237/javascript-runtime-complexity-of-array-functions/22615787
 

 

읽어주셔서 감사합니다.