Javascript Implementation Queue

 

 

사용한 개념

큐를 생각하면 "고속도로에서의 차량 대기열", "애플 스토어 앞에서 제품을 기다리는 사람들의 줄" 이런 개념이 떠오른다. 즉 "선입선출" 먼저 줄을 서면 먼저 집에 갈 수 있다. 이런 개념이다.  이렇게 순서대로 작동하는 것을 큐라고 한다. 

 

멤버 변수

• 데이터를 저장할 Object 타입의 storage
• 큐의 가장 앞을 가리키는 Number 타입의 포인터 front
• 큐의 가장 뒤를 가리키는 Number 타입의 포인터 rear

메서드

• size(): 큐에 추가된 데이터의 크기를 리턴해야 합니다.
• enqueue(): 큐에 데이터를 추가할 수 있어야 합니다.
• dequeue(): 가장 먼저 추가된 데이터를 큐에서 삭제하고 삭제한 데이터를 리턴해야 합니다.
  
  

 

사용 예시

const queue = new Queue();

queue.size(); // 0
for(let i = 1; i < 10; i++) {
  	queue.enqueue(i);
}
queue.dequeue(); // 1
queue.dequeue(); // 2
queue.size(); // 7
queue.enqueue(10);
queue.size(); // 8
queue.dequeue(); // 3
queue.dequeue(); // 4
queue.size(); // 6

 

 

 

풀이코드 설명

class Queue {
  constructor() {
    this.storage = {}; //storage 초기화
    this.front = 0;    //큐의 처음위치
    this.rear = 0;     //큐의 마지막위치
  }

  size() {
    //사이즈는 큐의 마지막위치에서 큐의 첫번째 위치를 뺀 값
    return this.rear - this.front ;
    
  }
	
  // 큐에 데이터를 추가 >> rear에 += 1
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }
	
	// 가장 먼저 추가된 데이터가 가장 먼저 추출되어야 합니다.
    // 선입선출
    
  dequeue() {
    // 빈 큐에 dequeue 연산을 적용해도 에러가 발생하지 않아야 합니다
    // 사이즈가 0 이하면 return 
    if ( this.size() <= 0 ) {
      return;
    }

    //result에 큐의 첫번째위치를 인덱스로 설정
    //front 속성에 +=1
    const result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1;

    return result;
  }
}