Circular queue là gì?

Hàng đợi tròn (circular queue) là phiên bản mở rộng của hàng đợi (queue) thông thường trong đó phần tử cuối cùng (element) được kết nối với phần tử đầu tiên. Do đó tạo thành một cấu trúc giống như vòng tròn.

Hàng đợi tròn (circular queue) giải quyết được hạn chế chính của hàng đợi bình thường. Trong một hàng đợi bình thường, sau khi chèn và xóa một chút, sẽ có không gian (space) trống không thể sử dụng được.

Hàng đợi tròn (circular queue) hoạt động theo quy trình tăng vòng tròn (circular increment), tức là khi chúng ta cố gắng tăng con trỏ (pointer) và chúng ta đến cuối hàng đợi, chúng ta bắt đầu từ đầu hàng đợi. Ở đây, quy trình tăng vòng tròn được thực hiện bằng phép chia modulo với kích thước hàng đợi. Đó là:

if REAR + 1 == 5 (overflow!), REAR = (REAR + 1)%5 = 0 (start of queue)

Hàng đợi tròn (circular queue) hoạt động như sau:

• Hai con trỏ FRONT và REAR
• FRONT theo dõi phần tử đầu tiên của hàng đợi
• REAR theo dõi các phần tử cuối cùng của hàng đợi
• Ban đầu, đặt giá trị của FRONT và REAR thành -1

Cách triển khai (implementation) hàng đợi phổ biến nhất là sử dụng mảng (array), nhưng nó cũng có thể được triển khai bằng cách sử dụng danh sách (list).

// Circular Queue implementation in C

#include 

#define SIZE 5

int items[SIZE];
int front = -1, rear = -1;

// Check if the queue is full
int isFull() {
  if ((front == rear + 1) || (front == 0 && rear == SIZE - 1)) return 1;
  return 0;
}

// Check if the queue is empty
int isEmpty() {
  if (front == -1) return 1;
  return 0;
}

// Adding an element
void enQueue(int element) {
  if (isFull())
    printf("\n Queue is full!! \n");
  else {
    if (front == -1) front = 0;
    rear = (rear + 1) % SIZE;
    items[rear] = element;
    printf("\n Inserted -> %d", element);
  }
}

// Removing an element
int deQueue() {
  int element;
  if (isEmpty()) {
    printf("\n Queue is empty !! \n");
    return (-1);
  } else {
    element = items[front];
    if (front == rear) {
      front = -1;
      rear = -1;
    } 
    // Q has only one element, so we reset the 
    // queue after dequeing it. ?
    else {
      front = (front + 1) % SIZE;
    }
    printf("\n Deleted element -> %d \n", element);
    return (element);
  }
}

// Display the queue
void display() {
  int i;
  if (isEmpty())
    printf(" \n Empty Queue\n");
  else {
    printf("\n Front -> %d ", front);
    printf("\n Items -> ");
    for (i = front; i != rear; i = (i + 1) % SIZE) {
      printf("%d ", items[i]);
    }
    printf("%d ", items[i]);
    printf("\n Rear -> %d \n", rear);
  }
}

int main() {
  // Fails because front = -1
  deQueue();

  enQueue(1);
  enQueue(2);
  enQueue(3);
  enQueue(4);
  enQueue(5);

  // Fails to enqueue because front == 0 && rear == SIZE - 1
  enQueue(6);

  display();
  deQueue();

  display();

  enQueue(7);
  display();

  // Fails to enqueue because front == rear + 1
  enQueue(8);

  return 0;
}