Queue in Date structure

Queue

 

일반적으로 커피를 주문하기 위해 줄을 선다.

(FIFO : First in, First out 선입선출, 선착순의 개념) 

양쪽 끝에서만 데이터를 넣거나 뺄 수 있는 선형구조

//제일 먼저 들어온 데이터가 제일 빨리 나가는 방식

 

큐는 선착순으로 줄을 서는 것과 같이 작동한다.

 

Queue 그림예제_출처 : 코드스테이츠

큐가 가지고있는 method

enqueue(element) - 요소를 큐의 젤 마지막에 추가한다.

dequeue() - 큐의 젤 앞의 요소를 제거 후 반환한다.

size() - 큐의 현재 요소 개수를 반환한다.

 

코드로 구현해보기_Array(배열) in Javascript

class Queue{
  constructor() {
    this.storage = []
    this.start = 0; // 배열의 젤 앞의 값
    this.end = 0; // 배열의 젤 뒤의 값
  }
  
  size(){
    return this.end - this.start
  }//현재 큐의 값을 return
  
  enqueue(element){
    this.storage.push(element)
    this.end++//추가될 때, end+
  } //element를 Queue 추가
  
  dequeue(){
    this.end--//제거될 때, end-
    return this.storage.shift()
  }//start의 값을 제거하고 그 요소의 값을 return
} 

<-- 사용해보기 -->

let queue = new Queue;

queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);

queue;
//Queue{storae : Array(4), start : 0, end : 4}
//storage : (4) [1, 2, 3, 4]

queue.dequeue(); // 1
queue.dequeue(); // 2

queue.size() // 2

queue;
//Queue{storae : Array(2), start : 0, end : 2}
//storage : (2) [3, 4]

 

코드로 구현해보기_Object(객체) in Javascript

class Queue{
  constructor() {
    this.storage = {}
    this.start = 0; // 객채의 젤 위의 값
    this.end = 0; // 객체의 젤 밑의 값
  }
  
  size(){
    return this.end - this.start
  }//현재 큐의 값을 return
  
  enqueue(element){
    this.storage[this.end] = element
    this.end++//추가될 때, end+
  } //element를 Queue 추가
  
  dequeue(){
    let result = this.storage[this.start]
    delete this.storage[this.start];
    this.start++ 
    return result;
  }//start의 값을 제거하고 그 요소의 값을 return
   //start의 값을 추가해주는 이유는, 객체이기 때문의 key값이 바뀐다.
} 

//사용법은 동일하나, storage가 객체인 것만 다르다.

 

큐의 시간복잡도

추가하기 : O(1)

삭제하기 : O(1)

가져오기 : O(n)

//start부터 end까지 반복하여 조회하기 때문

 

 

큐를 이용한 예

대부분의 입출력, 메시지, 프린터 대기열, 게임 대기열(롤, 클래시로얄)