큐

큐의 개념

큐는 '줄을 서다'라는 뜻을 가지고 있습니다. 먼저 들어간 데이터가 먼저 나오는 자료구조입니다.

큐의 특성을 활용하는 분야

먼저들어온 것을 먼저 처리하는 큐의 동작 방식은 프로그래밍 언어에서 많이 활용되고 있습니다. 대표적으로 여러 이벤트가 발생했을 때 발생한 순서대로 처리할 때 큐가 활용됩니다.

작업 대기열: 네트워크 통신을 할 때 다수의 클라이언트에서 요청이 올 경우 순서대로 작업을 처리합니다.
이벤트 처리: 키보드 입력이나 마우스 움직임등 사용자의 이벤트를 처리할 때 큐를 활용할 수 있습니다.

큐의 ADT

구분	정의	설명
연산	boolean isFull()	큐 들어있는 데이터의 갯수가 최대인지 확인합니다.
연산	boolean isEmpty()	큐에 들어있는 데이터가 하나도 없는지 확인합니다.
연산	void push(item: ItemType)	큐에 마지막에 데이터를 추가합니다.
연산	ItemType pop()	큐에 처음에 있는 데이터를 제거하고 해당 데이터를 반환합니다.
상태	int front	큐에서 가장 처음에 삭제할 위치를 기록합니다.
상태	int rear	큐의 가장 최근에 추가한 데이터의 위치를 기록합니다.
상태	ItemType[] data[maxSize]	큐의 데이터를 관리하는 배열입니다. 최대 maxSize 개의 데이터를 관리합니다.

기존의 스택과 비교하였을 때 달라진 점은 top이 front와 rear로 바뀐 것입니다. 왜냐하면 큐는 앞에서 데이터를 제거하고 뒤에서 추가하므로 위치를 기억할 변수가 필요하기 때문입니다.

만약 아무런 데이터를 넣지 않은 상태라면 front와 rear는 둘 다 -1입니다.

큐의 세부 동작에 대해 알아보기

배열을 이용하여 큐의 생김새를 구현해봅니다.

큐에 값을 추가한다면 어떻게 추가되는지 알아보겠습니다.
push(newItem){ if(this.isFull()){ this.rear++; this.value.push(newItem); } else { console.log('큐가 가득 찼습니다'); } }
1. 큐에 값이 넣을 수 있는 상황인지 isFull() 메소드를 사용하여 확인합니다.
2. 큐의 값이 가득 차있는 상황이 아니라면 값을 추가합니다.
3. 또한 길이가 늘었기 때문에 최근에 추가된 아이템의 위치인 0을 반환합니다.
큐에 값을 제거하면 어떻게 되는지 알아보겠습니다.
isEmpty(){ return this.front === this.rear; } pop(){ if(this.isEmpty()){ return this.items[this.front++]; } else { console.log('큐가 비어져 있습니다'); } }
1. 큐에 값이 있는지 front와 rear의 값이 같은지 확인합니다. (최근 추가된 값과 삭제된 값의 번호가 같다면 해당 큐는 비어져 있는 것)
2. 큐의 값이 있다면 front의 값을 1 추가하고 shift를 이용하여 맨 앞의 값을 제거해줍니다.
3. 제거된 아이템을 반환합니다.

큐의 생김새를 본다면 다음과 같이 구현을 할 수 있습니다.

//       index 0  1  2  3  4
const queue = [1, 2, 3, 4, 5];
// front: -1
// rear: 4

queue.push(newItem);
// queue: [1, 2, 3, 4, 5, newItem]
// front: -1
// rear: 5

queue.pop();
//   index 0  1  2  3  4
// queue: [1, 2, 3, 4, 5, newItem]
// front: 0
// rear: 5

top과 같거나 작다면 해당 값은 없는 값으로 취급하기 때문에 위에 최종 값은 [2, 3, 4, 5, newItem]으로 나타납니다.

연결 리스트를 이용하여 구현하기

연결리스트로 구현을 할 수 있지만 연결 리스트는 JavaScript에서 기본적으로 제공되지 않는 자료구조입니다. 따라서 직접 구현할 필요가 있습니다.

class Node {
   constuctor(data) {
      this.data = data; // 요소의 값
      this.next = null; // 다음 참조 주소
   }
}

class Queue {
   constructor(){
      this.head = null;
      this.tail = null;
      this.size = 0;
   }
   
   push(newItem){
      const newNode = new Node(newItem);
   
      if (!this.head) {
         this.head = newNode;
         this.tail = newNode;
      } else {
         this.tail.next = newNode;
         // 이전 마지막 값에 다음 주소로 새로운 노드를 연결합니다.
         this.tail = newNode;
         // 새로운 노드를 마지막으로 대입합니다.
      }
      this.size++;
   }
   
   pop(){
      if(!this.head){
         return null;
      }
      
      const removeNode = this.head;
      // 삭제할 노드의 다음 주소를 새로운 헤드 값으로 대입합니다.
      this.head = this.head.next;
      
      if(!this.head){
        this.tail = null;
      }
      
      this.size--; // 큐 길이를 감소시킵니다.
      
      // 삭제된 요소의 값을 반환합니다.
      return removeNode.data;
   }
   
   isEmpty() {
      return this.size === 0;
   }
}

Last modified: 07 August 2024