[Data Structure] 선형 - Queue(큐)

Queue (큐)

• 스택과 반대로 먼저 저장된 것이 제일 먼저 나온다. 가장 나중에 저장된 것이 꺼내어 쓸 때는 가장 나중에 나온다.
• 가장 먼저 입력된 요소를 처리하는 FIFO (First In First Out) 또는 LILO(Last-In, Last-Out) 방식.

 

Ex) 큐 구현

class Queue {
  constructor() {
    this.storage = {}; // 여기에 담는다.
    this.front = 0;
    this.rear = 0;
  }

  size() {
    return Object.keys(this.storage).length;
  }
	
  // 큐에 데이터를 추가 할 수 있어야 한다.
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }
	
  // 가장 먼저 추가된 데이터가 가장 먼저 추출되어야 한다.
  dequeue() {
    // 빈 큐에 dequeue 연산을 적용해도 에러가 발생하지 않아야 한다.
    if (Object.keys(this.storage).length === 0) {
      return;
    }

    const result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1;

    return result;
  }
}

적용

const queueData = new Queue;
queueData.enqueue('a'); //'a'를 넣는다
queueData.enqueue('b'); //'b'를 넣는다
queueData.enqueue('c'); //'c'를 넣는다
console.log(queueData); // {storage: {…}, front: 0, rear: 3}
// storage: {0: "a", 1: "b", 2: "c"}
console.log(queueData.size()); // 큐의 길이는 3
queueData.dequeue(); // 콘솔에는 'a'가 찍힌다
console.log(queueData); // {storage: {…}, front: 1, rear: 3}
// storage: {1: "b", 2: "c"}
// 즉 먼저 삽입된 'a'가 빠진 것을 알 수 있다.