큐(QUEUE)

큐도 스택과 마찬가지로 임시 데이터를 처리하기 위해 디자인된 데이터 구조다.
데이터를 처리하는 순서만 제외하면 많은 면에서 스택과 비슷하다.
스택처럼 큐도 추상 데이터 타입이다.

선착순을 QUEUE라고 볼 수 있다.(실제 대기열을 Queue라고 한다)

먼저 도착한 사람이, 먼저 행동하게 된다
이는 FirstInFirstOut FIFO로 표현한다.

스택이 세로로 된 배열로 묘사된다면 스택은 주로 가로로 묘사된다.
또한 흔히 큐의 앞을 front 큐의 끝을 back이라 부른다.

스택과 마찬가지로 큐도 세 가지 제약을 갖지만 제약 사항이 조금 다르다.

• 데이터는 큐의 끝에만 삽입할 수 있다.
• 데이터는 큐의 앞에서만 삭제할 수 있다.
• 큐의 앞에 있는 원소만 읽을 수 있다.

큐에 값을 삽입할 때에는 enqueue, 값을 제거할때에는 dequeue라 부른다.

---

큐 다뤄보기

출력부터 웹 어플리케이션의 백그라운드 워커에 이르기까지 많은 앱에서 흔하게 큐를 사용한다.

프린터가 네트워크상에 있는 여러 컴퓨터로부터 출력 잡을 받아, 요청받은 순서대로 각 문서를 출력하는 기능을 구현해보자

class PrintQueue {
  constructor() {
    this.queue = [];
  }

  enqueue(item) {
    this.queue.push(item);
  }

  dequeue() {
    return this.queue.shift();
  }

  isEmpty() {
    return this.queue.length === 0;
  }

  size() {
    return this.queue.length;
  }
}

모던 자바스크립트에서의 배열은 해시에 가깝기 때문에 배열을 사용하여 큐를 구현하였다.

---

스택과 큐를 언제 사용할까?

다음은 실 생활에서 스택과 큐 자료구조를 언제 사용할지 선택에 도움을 줄 수 있는 예시다.

1. 전화를 건 사람을 잠시 대기시킨 후 다음 연결 가능한 통화원에게 연결해 주는 콜센터 소프트웨어 작성중이라면 스택을 쓰겠는가 큐를 쓰겠는가?

큐를 사용한다. 전화를 건 사람이 복수일 수 있으므로 전화를 건 사람을 큐에 저장시키고 FIFO를 적용하여 한명씩 상담원에게 연결한다.

2. 1,2,3,4,5,6의 순서대로 스택에 푸시한 후 두 항목을 팝하면 스택,큐에서 어떤 수를 읽는가?

스택은4 큐는3을 읽는다. 큐는 Front의 값만, 스택의 Top의 값만 읽을 수 있다.

3. 스택을 사용해 문자열을 거꾸로 만드는 함수를 작성하라

function reverseWord(word){
  const stack = [];
  let newString = '';
  for(let i = 0; i < word.length ; i++) {
      stack.push(word[i]);
  }
  for(let i = 0; i < word.length; i++){
  	newString += stack.pop();
  }
return newString;
}

reverseWord('안녕하세요?') // ?요세하녕안