대기열

큐는 후면(테일이라고도 함)이라고 하는 한쪽 끝에서 요소를 삽입하고 전면(헤드라고도 함)이라고 하는 다른 쪽 끝에서 요소를 삭제할 수 있는 간단한 데이터 구조입니다.



대기열은 선입선출 원칙을 따르는 항목 모음입니다. 첫 번째 요소를 먼저 처리하고 최신 요소를 마지막으로 처리하는 데이터 구조를 처리하는 방법입니다.

대기열을 구현하는 방법?

대기열을 구현하면 크기 가져오기, 새 요소 추가, 요소 삭제 또는 단순히 비어 있는지 확인하는 것과 같은 몇 가지 메서드가 연결될 수 있습니다. 위에서 언급한 이러한 유형의 데이터 구조(FIFO)가 기반으로 하는 구현 순서를 항상 존중합니다.

코드를 작성해 봅시다

먼저 대기열을 생성하는 함수가 필요합니다. 맞습니까? 이제 JS의 기본 메서드를 사용하여 새 함수를 만들어 보겠습니다(개념을 이해하기 위해 간단한 작업을 수행하고 있습니다).

function createQueue() {
  const queue = [];
  return queue;
}

지금까지 빈 배열을 반환하는 함수가 있습니다. 그러나 구현에 몇 가지 기능을 추가하려고 합니다. 예를 들어 새 대기열에 항목을 대기열에 넣겠습니다.

function enqueue() {
  queue.unshift(item);
}

무슨 일이야? enqueue 메서드인 unshift 메서드를 호출할 때 큐의 시작 부분에 우리가 지정한 요소를 추가합니다.

Reference to Unshift Method

이제 메서드를 대기열에 추가할 수 있지만 더 나아가 대기열을 해제하는 메서드를 추가해 보겠습니다.

function dequeue() {
  return queue.pop();
}

이전에 말했듯이 이러한 유형의 구조는 일반적으로 FIFO라고 부르므로 입력한 마지막 항목을 제거해야 합니다. 이것이 JS 배열의 기본 팝 기능이 처리하는 것입니다.

Reference to Pop Method

구조가 거의 준비되었습니다. 이제 대기열의 현재 크기를 계산하고 비어 있는지 확인하는 두 가지 방법을 추가하겠습니다.

function length() {
  return queue.length
}
function isEmpty() {
  return queue.length == 0
}```



We will use the native method length, to calculate the dimension of our queue. And we will do a simple mathematical check equaling 0 to know if our queue is empty or not.

Now, let's put it all together.



```javascript
function createQueue() {
  const queue = [];
  return { 
    enqueue(item) {
      queue.unshift(item);
    },
    dequeue() {
      return queue.pop();
    },
    get length() {
      return queue.length;
    },
    get values() {
      return queue;
    },
    isEmpty() {
      return queue.length == 0;
    } 
  };
}

const myQueue = createQueue(); console.log("Is Empty ?", myQueue.isEmpty()); // true
myQueue.enqueue("Adding my first element"); myQueue.enqueue("Learning how a queue works");

console.log("My Queue Elements", myQueue.values); // ["Learning how a queue works", "Adding my first element"]
console.log("Is Empty ?", myQueue.isEmpty()); // false console.log("Size of Queue", myQueue.length); // 2 

myQueue.dequeue();
console.log("Size of Queue", myQueue.length); // 1

Play Code Here

실제 사용

Queue는 BFS(Breadth First Search) 알고리즘에서 사용됩니다. 트리나 그래프를 순회하는 데 도움이 됩니다.

대기열은 작업 예약을 위해 운영 체제에서도 사용됩니다.

대기열은 혼잡을 처리하기 위해 네트워킹에서 사용됩니다.

대기열의 정말 재미있는 예

나만의 Snake "Nokia"게임을 만들려면 무엇이 필요합니까?

Okay, so initially my snake will be of some X pixels length. Every time it consumes food, its length increments by 1. I’ll also have to keep track of the snake’s head, or the start. And the end. And also any turning points on the body. And every time the user turns the snake in a valid direction, I’ll have to add a new turning point at that position. And then the tail — the end of the snake has to follow the same turns the head made initially. So let me rephrase that. The head first turns. Eventually the rest of the body turns. The head turns again, the body turns again. If head turns East then North then West, the body turns East then North then West. I’ll need a queue.

보너스

우선순위 대기열

우선 순위 큐는 다음 속성을 가진 큐의 확장입니다.

모든 항목에는 관련된 우선 순위가 있습니다.

우선순위가 높은 요소는 우선순위가 낮은 요소보다 먼저 대기열에서 제외됩니다.

두 요소의 우선 순위가 같으면 대기열의 순서에 따라 처리됩니다.

아래 우선 순위 큐에서 최대 ASCII 값을 가진 요소가 가장 높은 우선 순위를 갖습니다.

대기열에 넣기

항목을 대기열에 추가하는 방법은 이제 항목의 우선 순위가 높은지 여부를 알려주는 두 번째 인수를 받습니다. 기본적으로 이 값은 false입니다. 우선 순위가 높은지 표시하지 않으려면 값을 생략할 수 있기 때문입니다. 이런 식으로 우리가 적용한 조건부 논리에 따라 항목이 낮은 우선 순위 대기열에 추가됩니다.

function enqueue(item, isHighPriority = false) {
  isHighPriority
    ? highPriorityQueue.enqueue(item)
    : lowPriorityQueue.enqueue(item);
}```



*Dequeue*

Our method for dequeue will be set first in the high priority list, in case it is not empty, dequeue the first item in the high priority list. Otherwise go to the low priority list to remove an item.



```javascript
function dequeue() {
  if (!highPriorityQueue.isEmpty()) { 
    return highPriorityQueue.dequeue();\
  } 

  return lowPriorityQueue.dequeue(); }

몰래 엿보다

우리의 peek 방법은 비슷한 변화를 가져옵니다. 우선순위가 높은 대기열에서 먼저 대기열을 빼는 것처럼 우선순위가 높은 대기열에서도 먼저 엿볼 것입니다. 실제로 이 코드를 복사하여 붙여넣고 호출되는 메서드를 변경할 수 있습니다.

function peek() {
  if (!highPriorityQueue.isEmpty()) {
    return highPriorityQueue.peek();
  }

  return lowPriorityQueue.peek(); }

길이

우리의 길이 방법은 함께 추가된 두 대기열의 크기만 반환합니다.

function length() {
  return highPriorityQueue.length + lowPriorityQueue.length;
}```



*Is Empty*

Lastly, our isEmpty method is the conjunction of the two queues' isEmpty methods.



```javascript
function isEmpty() {
  return highPriorityQueue.isEmpty()
    && lowPriorityQueue.isEmpty();
}```



Let's put all together



```javascript
import { createQueue } from "./queue";

function createPriorityQueue() {
  const lowPriorityQueue = createQueue();
  const highPriorityQueue = createQueue();

  return {
    enqueue(item, isHighPriority = false) {
     isHighPriority
       ? highPriorityQueue.enqueue(item)
       : lowPriorityQueue.enqueue(item);
    },
    dequeue() {
      if (!highPriorityQueue.isEmpty()) {
        return highPriorityQueue.dequeue();
      }

      return lowPriorityQueue.dequeue();
    },
    peek() {
      if (!highPriorityQueue.isEmpty()) {
        return highPriorityQueue.peek();
      }

      return lowPriorityQueue.peek();
    },
    length() {
      return highPriorityQueue.length + lowPriorityQueue.length;\
    },
    isEmpty() {
      return highPriorityQueue.isEmpty()
        && lowPriorityQueue.isEmpty();
    }
  };
}

const myQueue = createPriorityQueue();

myQueue.enqueue("A fix here");
myQueue.enqueue("A bug there");
myQueue.enqueue("A new feature");

console.log(myQueue.peek()); // A fix here

myQueue.dequeue();

console.log(myQueue.peek()); // A bug there 

myQueue.enqueue("Emergency task!", true); 

console.log(myQueue.peek()); // Emergency task! myQueue.dequeue(); console.log(myQueue.peek()); // A bug there

Play Code

실제 사용

Dijkstra의 최단 경로 알고리즘 - Prim의 알고리즘 - 데이터 압축을 위한 Huffman 코드.

힙 정렬

서버에서 로드 밸런싱.

여기까지 왔다면 이제 큐를 직접 구현하는 방법과 장점이 무엇인지 확실하게 알게 되었습니다. 다음 게시물에서는 스택 데이터 구조가 어떻게 작동하는지 살펴보겠습니다.