순환 대기열

오늘은 내가 배운 것에 대한 순환 대기열에 대해 이야기할 것입니다.

지난 포스트에서 우리는 에 대해 논의했습니다.

순환 대기열에는 작은 문제가 있습니다.

요소 크기가 5인 큐가 있다고 가정해 보겠습니다. 큐 배열에는 우리가 사용할 5개의 메모리 할당이 있습니다.



이제 난수(34)가 첫 번째 요소로 대기열에 삽입되었다고 가정해 보겠습니다. 이 순간 큐 배열의 앞, 뒤 값은 모두 0입니다. 하나의 메모리 위치가 사용됩니다. 4개 갑니다.



이제 4개의 난수 요소를 삽입하여 전체를 만들어 보겠습니다. 메모리 할당은 다음과 같아야 합니다.



이제 하나의 요소를 삭제해 보겠습니다. 34인 앞 요소가 삭제됩니다. 그리고 앞은 올바른 두 번째 요소로 1 이동하고 이제 앞은 1입니다.



후방의 가치를 보십시오. 후면은 가장 큰 숫자인 4를 사용합니다.

이제 큐에 요소를 하나 더 삽입해야 합니다.
게시물의 삽입 방법을 기억해 봅시다.

후면이 최대 크기인지 먼저 확인합니다. 그렇지 않은 경우 대기열에 삽입할 수 있습니다.

하지만 가득 찬 큐에 요소를 삽입해야 하는 이유는 무엇입니까?
가득 찼습니까? 아니요, 한 요소를 삭제했기 때문이 아닙니까?

예, 하지만 대기열 구현에서는 사용 가능한 일부 여유 슬롯이 있더라도 여유 메모리 할당을 사용할 수 없습니다. 후면이 최대값이 되면 발생합니다.

대기열에 더 많은 요소를 삽입할 수 없지만 삭제할 수는 있습니다.

이것은 대기열 구현의 문제입니다. 해결책은 순환 대기열입니다.

순환 큐는 재사용 가능한 메모리 위치가 있는 특수 큐인 큐입니다. 따라서 사용 가능한 여유 슬롯이 있으면 이를 사용하여 값을 삽입할 수 있습니다.

따라서 이 기능을 지원하려면 대기열의 삽입 및 삭제 메서드를 수정해야 합니다.

삽입 방법

public void insert(int x) {
   if (items == size) {
      System.out.println("Queue already full!");
   }
   else {
      if(rear == size - 1) {
         rear = -1;
      }
      rear++;
      queue[rear] = x;
      items++;
      System.out.println(x + " Inserted to queue");
   }
}

// first checks if queue is full not by checking the 
// the rear's maximum value, but by comparing
// if items count is the size of queue array's length.
// if it is we do not allow insertion, or else
// we checks if rear is in its max and if so
// adjust the rear's value to adopt circular queue behavior
// by pointing it to rear's initial value which is (-1).

삭제 방법

public void delete() {
   if (items == 0) {
      System.out.println(“Queue is Empty!”);
   }
   else {
      int frontItem = queue[front];
      front++;
      if (front == size) {
         front = 0;
      }
      items--;
      System.out.println(frontItem + " Deleted from queue");
   }
}

// first we check whether queue is empty
// if it is we do not allow to delete from the queue
// else we take the first item to a variable called 
// frontItem and then shifts up front by one.
// if front's value is the maximum then assign
// front's value to 0 which is the initial value 
// of front thus adopting circular queue behavior.

위에서 설명한 순환 대기열 코드 샘플은 정수를 요소 유형으로 사용합니다.
소스 코드는 다음 URL에서 사용할 수 있습니다.

https://github.com/lizardkingLK/CircularQueues