개념정리 - Queue 구조

Queue

1. Queue 구조란?

Queue 구조는 저번에 정리했던 Stack 구조와 조금 다르다.
Stack이 선입후출 (FILO) 였다면, Queue는 (FIFO) 구조로 이루어져있다.

말그대로 선입선출의 구조라는것인데, 예를 들어 설명해보자면

콘서트장의 대기줄이 생긴다고 봤을때, 가장 먼저 와서 줄을서고 있던 사람이
가장 먼저 콘서트장에 들어갈 수 있는것 같은 개념인것이다.

스택에 처음 들어온 데이터가 가장 먼저 나올 수 있는 구조라고 생각하면 되겠다.

& 웹에서 Queue 구조가 사용되는 예

컴퓨터와 연결된 프린터에서 여러 문서를 순서대로 인쇄하려면 어떻게 해야 할까.

1. 문서를 작성하고 출력 버튼을 누르면 해당 문서는 인쇄 작업 (임시 기억 장치의) Queue에 들어간다.

2. 프린터는 인쇄 작업 Queue에 들어온 문서를 순서대로 인쇄한다.

3. 컴퓨터(출력 버튼) - (임시 기억 장치의) Queue에 하나씩 들어옴 - Queue에 들어온 문서를 순서대로 인쇄

만약 Queue에 들어온 순서대로 출력하지 않는다면, 인쇄 결과물이 뒤죽박죽일것이다.

2. Queue 구조 구현

Queue 구조를 구현하기 위한 코드를 작성해보자.

1) Queue 클래스 및 빈 스택 생성

빈 Queue 스택을 만든다, 그리고 스택은 두가지의 인스턴스를 생성해야 한다.

class Queue {           // Queue 라는 class를 생성한다.
  constructor() {
    this.storage = {};  // 빈 스택을 생성하고,
    this.front = 0;     // 스택의 앞
    this.rear = 0;      // 스택의 뒤쪽을 분리해서 생성해놓는다.
  }

2) Queue 의 size 파악하기

Queue 의 사이즈를 파악할 수 있는 메서드를 작성한다.

size() {
    return (this.rear) - (this.front)  // stack과는 다르게 끝에서 처음을 빼면 크기가 나온다.
  }

3) Queue 에 데이터 추가하기 (enqueue)

Queue 에 데이터를 추가하는 코드를 구현한다. enqueue 라고 한다.

 enqueue(element) {
    this.storage[this.rear] = element; // 스택의 맨 끝에 인자를 추가한다.
    this.rear += 1;                    // 끝자리에 카운트를 준다.
  }

4) Queue 안의 데이터를 추출하기 (dequeue)

Queue 안에 있는 데이터를 꺼내온다, 맨 앞쪽의 데이터를 추출해야 한다. dequeue 라고 한다.

 dequeue() {
    if (this.size() === 0) {  // 스택의 사이즈가 없어도
      return;                 // 스택을 그대로 리턴한다. 오류가 나면 안된다.
    }

    const result = this.storage[this.front];  // 스택의 맨 앞 인덱스를 변수에 할당하고
    delete this.storage[this.front];          // 실질적으로 스택에서 제거한다.
    this.front += 1;                          // front에 1을 더해서 맨 앞이 한칸 밀리게 한다.

    return result;            // 변수를 최종 리턴한다.
  }