[자료구조] 큐 (Queue) - 정의, 특징, 그리고 자바스크립트로 구현하기

Queue의 정의

• 줄을 서서 기다리다, 대기 행렬
• 데이터(data)를 입력된 순서대로 처리할 때 주로 사용하는 자료구조

Queue의 특징

• FIFO (First In First Out) = LILO (Last In Last Out)
• 먼저 들어간 데이터가 먼저 나오는 자료구조

일상생활의 예시

명절에는 고향으로 가기 위해 많은 자동차들이 고속도로를 지납니다. 고속도로에는 톨게이트가 있고, 자동차는 톨게이트에 진입한 순서대로 통행료를 내고 톨게이트를 통과합니다.

• 톨게이트: Queue 자료구조
• 자동차: 데이터(data)

 

 

Queue의 실사용 예제

컴퓨터와 연결된 프린터에서 여러 문서를 순서대로 인쇄

순서

1. 문서를 작성하고 출력 버튼을 누르면 해당 문서는 인쇄 작업 (임시 기억 장치의) Queue에 들어갑니다.
2. 프린터는 인쇄 작업 Queue에 들어온 문서를 순서대로 인쇄합니다.

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

 

 위 예시처럼 컴퓨터 장치들 사이에서 데이터(data)를 주고 받을 때, 각 장치 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용합니다. 이것을 통틀어 버퍼(buffer)라고 합니다.

 아래 이미지는 버퍼링(buffering)의 개념을 보여주고 있습니다.

 

 

대부분의 컴퓨터 장치에서 발생하는 이벤트는 파동 그래프와 같이 불규칙적으로 발생합니다.
이에 비해 CPU와 같이 발생한 이벤트를 처리하는 장치는 일정한 처리 속도를 갖습니다.
불규칙적으로 발생한 이벤트를 규칙적으로 처리하기 위해 버퍼(buffer)를 사용합니다.

(왼쪽) CPU에서는 이벤트를 규칙적으로 처리합니다. (오른쪽) 대부분의 컴퓨터 장치에서는 이벤트가 불규칙하게 발생합니다.

컴퓨터와 프린터 사이의 데이터(data) 통신을 정리하면 다음과 같습니다.

• 일반적으로 프린터는 속도가 느립니다.
• CPU는 프린터와 비교하여, 데이터를 처리하는 속도가 빠릅니다.
• 따라서, CPU는 빠른 속도로 인쇄에 필요한 데이터(data)를 만든 다음, 인쇄 작업 Queue에 저장하고 다른 작업을 수행합니다.
• 프린터는 인쇄 작업 Queue에서 데이터(data)를 받아 일정한 속도로 인쇄합니다.

 유튜브와 같은 동영상 스트리밍 앱을 통해 동영상을 시청할 때, 다운로드 된 데이터(data)가 영상을 재생하기에 충분하지 않은 경우가 있습니다. 이때 동영상을 정상적으로 재생하기 위해 Queue에 모아 두었다가 동영상을 재생하기에 충분한 양의 데이터가 모였을 때 동영상을 재생합니다.

 

 

 

---

1.class 로 사용자 정의 데이터 타입을 만들어 Stack 구현하기

JavaScript로 사용자 정의 데이터 타입을 만들어 내는 여러 방법 중에서, ES6 문법 중 하나인 class 키워드로 사용자 정의 데이터 타입을 만들고, Stack과 Queue의 데이터 타입을 정의합니다. 이렇게 생성한 사용자 정의 데이터 타입은 Stack과 Queue를 Array와 object처럼 사용할 수 있습니다.

사용자 정의 데이터 타입으로 Stack과 Queue를 정의하면, new 키워드를 통해 새로운 객체(인스턴스)를 만들 수 있습니다. 그리고 생성한 인스턴스를 통해 다양한 메서드를 사용할 수 있습니다.

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;  // 큐의 가장 앞을 가리키는 Number 포인터
    this.rear = 0;   // 큐의 가장 뒤 가리키는 Number 포인터
  }

  size() {
    return this.rear - this.front;
  }
	
  // 큐에 데이터를 추가
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }
	
  // 가장 먼저 추가된 데이터가 가장 먼저 추출
  dequeue() {
    // 빈 큐에 dequeue 연산을 적용해도 에러가 발생하지 않도록
    if (this.size() <= 0) {
      return;
    }

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

    return result;
  }
}

 

2. Javascript의 Array를 활용하여 Stack 사용하기

JavaScript에는 Array라는 훌륭한 자료형이 이미 있습니다. Array를 사용하면 사용자 정의 데이터 타입을 구현하는 시간을 절약할 수 있고, 몇 가지의 메서드로 Stack과 Queue처럼 동작하도록 사용할 수 있습니다.

자료구조로써 Stack과 Queue의 특성만 이해한다면, Array를 활용하여 Stack과 Queue로 사용할 수 있습니다.
다시 말해 자료구조는 자료(데이터)를 다루는 구조 그 자체를 뜻하며, 구현하는 방식에는 제약이 없습니다.

// const array = new Array() 미리 정의된 Array 객체를 사용합니다.
const queue = [];

queue.push(1); // [1]
queue.push(2); // [1, 2]
queue.push(3); // [1, 2, 3]
queue.push(4); // [1, 2, 3, 4]
queue.push(5); // [1, 2, 3, 4, 5]

console.log(queue); // [1, 2, 3, 4, 5]

queue.shift(); // [2, 3, 4, 5]
queue.shift(); // [3, 4, 5]

console.log(queue); // [3, 4, 5]

 

질문

• Array.prototype에는 Stack, Queue 사용을 위해 어떤 메서드가 존재하나요?
  • Stack: push, pop
  • Queue: push, shift
• 배열로 Stack, Queue를 사용할 때 주의해야 할 사항은 어떤것들이 있나요?
  • Stack: push, pop, empty, size 메소드를 만든다
    • emty() : 저장소가 비어있는지 확인하는 메소드
    • size() : 현재 저장소에 저장되어있는 데이터의 수를 반환하는 메소드
  • Queue: push, shift, empty, size 메소드를 만든다
• 배열로 Stack을 사용할 때 push, pop 이외에 필요한 메서드를 어떻게 구현할 수 있나요?
  • Stack의 size() : Array.length
  • Stack의 empty() : Array.length === 0
• 배열로 Queue를 사용할 때 push, shift 이외에 필요한 메서드를 어떻게 구현할 수 있나요?
• JavaScript의 배열과 Stack, Queue는 어떤 차이가 있나요?
  • javascript의 배열: 배열의 요소를 순서에 상관없이 메소드(push, pop, shift, unshift)를 사용해서 넣었다가 뺐다 할 수 있음
  • Stack, Queue: 요소를 다룰 때 정해진 순서를 지켜야 함