[JavaScript] 자료구조 (2): 큐(Queue)

1. What is 큐?

큐를 설명하라고 했더니 이번에는 줄이 빽빽하게 있는 모습이 보인다? 저 위의 사진은 서울역이다. 명절 대비해서 기차표를 예매하는 모습이다. 기차표를 예매할 때 줄을 서는데, 선착순이다. 먼저 온 사람이 먼저 예매를 하는 형식이다.

위는 큐를 영한사전에서 찾아본 결과이다. 한마디로 말해서 큐는 줄이다. 그리고 선착순이 원칙이다. 즉, 선입선출(FIFO(First In First Out)) 혹은 후입후출(LILO(Last In Last Out))이 특징이다. 큐도 스택과 마찬가지로 추상적 자료구조이기 때문에 선착순의 원칙만 지켜지면 데이터의 형식은 상관이 없다.

2. 큐 구현하기

이번에도 큐를 ES6 문법인 클래스를 이용하여 큐 자료구조를 구현해볼 것이다.
아래는 자바스크립트 코드이다.

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'가 빠진 것을 알 수 있다.

3. 큐의 예시: 프린터

프린터가 인쇄를 하는 방식도 큐의 방식을 따른다. 먼저 요청된 것이 먼저 인쇄가 된다. 하지만 여기서 끝이 아니다. 컴퓨터 사용의 효율성을 위하여 임시로 저장해두는 기억공간인 버퍼의 용량도 고려해야 된다. 그리고 한번에 최대 동시에 저장되는 문서의 양도 고려해야 된다. 이것에 따라서 queuePrinter라는 함수를 작성하고자 하며, 리턴값은 문서가 모두 인쇄되는데 걸리는 최소 시간이다. 인자는 다음과 같다.

• 인자1: bufferSize
  Number 타입의 인쇄 작업 목록 크기
• 인자 2: capacities
  Number 타입의 인쇄 작업 목록에 추가될 수 있는 최대 용량
• 인자 3: documents
  Number 타입을 요소로 갖는 문서 크기가 나열된 배열

우선 documents 배열은 선착순으로 인쇄가 되어야 되므로 큐의 형식이라는 것을 알 수 있다. 그리고 최소 시간이 지나야 되기 때문에 시간을 표기할 변수도 필요할 것이다. 큐에는 형식으로 0을 넣어준다. 현재까지의 코드는 다음과 같다.

function queuePrinter(bufferSize, capacities, documents) {
  let time = 0; // 걸린 시간(초)
  let queue = []; // 문서를 여기에 옮길 것이다.
  let totalBufferVolume = 0; // 문서가 버퍼에 들어갈 때 총 들어간 용량이다. 
  // queue에 bufferSize만큼 0을 삽입 (queue에 들어갈 요소의 고정 갯수를 만들어 주는 과정입니다.)
    for(let i = 0; i < bufferSize; i++){
        queue.push(0);
    }
}

이제 처음 문서가 인쇄될 때(1초)를 고려해야 된다. 현재 문서가 무엇인지를 지정해두고, 동시에 documents의 맨 먼저 들어온 배열을 queue 배열로 옮긴다(복사가 아님). 그리고 문서가 버퍼에 옮겨졌으므로, totalBufferVolume도 바뀐 값에 대하여 수정을 해준다. 그리고 초를 나타내는 time 변수에 1을 더해준다(1초가 지났음). 여기까지의 코드는 다음과 같다.

  let currentDocument = documents.shift();
  queue.unshift(currentDocument);
  queue.pop(); // 이는 queue의 배열의 length를 일정하게 하게 만드는 스킬이다.
  totalBufferVolume += currentDocument;
  time++;

이제 1초가 지난 후에는 작업을 반복시켜주면 된다. 반복 조건은 문서에 버퍼에 들어간 총 용량이 0 이상일 때이다. 인쇄가 다 완료가 되었다면 버퍼에 들어간 총 용량은 Zero가 될 것이기 때문이다. 2초부터는 총 들어간 버퍼의 용량에 대한 수정을 해주어야 된다. 새로운 문서가 들어가기 때문이다. 그리고 새로운 문서가 들어갔는데, 버퍼에 들어갈 수 있는 경우와 용량이 모자르기 때문에 못 들어가는 경우가 있을 수 있다. 각각의 경우에 대하여 코딩을 해주면 된다. 아래는 1초 이후의 상황을 코딩해본 것이다.

while (totalBufferVolume) {
  // totalBufferVolume(총 용량)에 queue의 마지막 배열을 빼준다.
  totalBufferVolume -= queue.pop();
  // document의 맨 앞의 요소를 일단 빼고, 현재 문서로 저장한다.
  currentDocument = documents.shift();
  // 여기서 용량에 따라서 분기점이 생긴다.
  // 만약 여유공간이 있다면
  if (currentDocument + totalBufferVolume <= capacities) {
    // queue에 currentDocument 삽입 후 총 용량에 현재 문서의 용량을 더해준다.
    queue.unshift(currentDocument);
    totalBufferVolume += currentDocument;
  } else { // 용량이 모자른 경우
    // documents에 현재 문서를 맨 앞에 다시 넣어준다.(shift해준것을 다시 복구)
    documents.unshift(currentDocument);
    queue.unshift(0);// 추가된 문서가 없기 때문에 맨 앞의 queue에 0을 추가
  }
  time++; // 1초의 경우처럼 마지막에 시간을 1초 추가해준다.
}

그 후에 count를 리턴해준다. 총 코드는 다음과 같다.

function queuePrinter(bufferSize, capacities, documents) {
  let time = 0; // 걸린 시간(초)
  let queue = []; // 문서를 여기에 옮길 것이다.
  let totalBufferVolume = 0; // 문서가 버퍼에 들어갈 때 총 들어간 용량이다. 
  // queue에 bufferSize만큼 0을 삽입 (queue에 들어갈 요소의 고정 갯수를 만들어 주는 과정입니다.)
    for(let i = 0; i < bufferSize; i++){
        queue.push(0);
    }
  
  let currentDocument = documents.shift();
  queue.unshift(currentDocument);
  queue.pop(); // 이는 queue의 배열의 length를 일정하게 하게 만드는 스킬이다.
  totalBufferVolume += currentDocument;
  time++;
  
  while (totalBufferVolume) {
  // totalBufferVolume(총 용량)에 queue의 마지막 배열을 빼준다.
    totalBufferVolume -= queue.pop();
  // document의 맨 앞의 요소를 일단 빼고, 현재 문서로 저장한다.
    currentDocument = documents.shift();
  // 여기서 용량에 따라서 분기점이 생긴다.
  // 만약 여유공간이 있다면
    if (currentDocument + totalBufferVolume <= capacities) {
    // queue에 currentDocument 삽입 후 총 용량에 현재 문서의 용량을 더해준다.
      queue.unshift(currentDocument);
      totalBufferVolume += currentDocument;
    } else { // 용량이 모자른 경우
    // documents에 현재 문서를 맨 앞에 다시 넣어준다.(shift해준것을 다시 복구)
      documents.unshift(currentDocument);
      queue.unshift(0);// 추가된 문서가 없기 때문에 맨 앞의 queue에 0을 추가
    }
    time++; // 1초의 경우처럼 마지막에 시간을 1초 추가해준다.
  }
  return time;
}