循环队列数据结构

提示

1. 循环队列概念：循环队列是普通队列的扩展，其中最后一个元素连接到第一个元素，形成圆形结构，解决了普通队列中的空间浪费问题。
2. 工作原理：循环队列通过循环增量过程工作，当指针增加到队列末尾时会从队列开始处重新开始，使用模除运算来实现。
3. 基本操作：循环队列支持入队和出队操作，其中入队在队尾添加元素，出队从队首移除元素。队列空或满的判断依赖于头尾指针的相对位置。

循环队列是 普通队列 的扩展版本，其中最后一个元素连接到第一个元素，从而形成类似圆形的结构。

循环队列解决了普通队列的主要限制。在普通队列中，经过一些插入和删除操作后，会有无法使用的空间。

此处，索引 0 和 1 只有在重置队列（删除所有元素）后才能使用。这减少了队列的实际大小。

循环队列的工作原理

循环队列通过循环增量的过程来工作，即当我们尝试增加指针并到达队列末尾时，我们从队列的开始处重新开始。

这里，循环增量是通过队列大小进行模除来实现的。即，

if REAR + 1 == 5（溢出！），REAR = (REAR + 1)%5 = 0（队列开始处）

循环队列操作

循环队列的工作方式如下：

• 两个指针 FRONT 和 REAR
• FRONT 跟踪队列的第一个元素
• REAR 跟踪队列的最后一个元素
• 最初，将 FRONT 和 REAR 的值设置为 -1

1. 入队操作

• 检查队列是否已满
• 对于第一个元素，将 FRONT 的值设置为 0
• 循环地将 REAR 索引增加 1（即如果 REAR 达到末尾，下一个将位于队列的开始处）
• 在 REAR 指向的位置添加新元素

2. 出队操作

• 检查队列是否为空
• 返回 FRONT 指向的值
• 循环地将 FRONT 索引增加 1
• 对于最后一个元素，将 FRONT 和 REAR 的值重置为 -1

然而，检查队列是否已满的条件有一个新的附加情况：

• 情况 1：FRONT = 0 && REAR == SIZE - 1
• 情况 2：FRONT = REAR + 1

第二种情况发生在 REAR 由于循环增量从 0 开始，并且其值比 FRONT 小 1 时，队列就满了。

Python、Java、C 和 C++ 中的循环队列实现

最常见的队列实现是使用数组，但也可以使用列表实现。

Python Java C C+

# Python 中的循环队列实现

class MyCircularQueue():

    def __init__(self, k):
        self.k = k
        self.queue = [None] * k
        self.head = self.tail = -1

    # 向循环队列中插入一个元素
    def enqueue(self, data):

        if ((self.tail + 1) % self.k == self.head):
            print("循环队列已满\n")

        elif (self.head == -1):
            self.head = 0
            self.tail = 0
            self.queue[self.tail] = data
        else:
            self.tail = (self.tail + 1) % self.k
            self.queue[self.tail] = data

    # 从循环队列中删除一个元素
    def dequeue(self):
        if (self.head == -1):
            print("循环队列为空\n")

        elif (self.head == self.tail):
            temp = self.queue[self.head]
            self.head = -1
            self.tail = -1
            return temp
        else:
            temp = self.queue[self.head]
            self.head = (self.head + 1) % self.k
            return temp

    def printCQueue(self):
        if(self.head == -1):
            print("循环队列中没有元素")

        elif (self.tail >= self.head):
            for i in range(self.head, self.tail + 1):
                print(self.queue[i], end=" ")
            print()
        else:
            for i in range(self.head, self.k):
                print(self.queue[i], end=" ")
            for i in range(0, self.tail + 1):
                print(self.queue[i], end=" ")
            print()


# 实例化 MyCircularQueue 对象并调用
obj = MyCircularQueue(5)
obj.enqueue(1)
obj.enqueue(2)
obj.enqueue(3)
obj.enqueue(4)
obj.enqueue(5)
print("初始队列")
obj.printCQueue()

obj.dequeue()
print("从队列中移除一个元素后")
obj.printCQueue()

// Java 中的循环队列实现

public class CQueue {
  int SIZE = 5; // 循环队列的大小
  int front, rear;
  int items[] = new int[SIZE];

  CQueue() {
    front = -1;
    rear = -1;
  }

  // 检查队列是否已满
  boolean isFull() {
    if (front == 0 && rear == SIZE - 1) {
      return true;
    }
    if (front == rear + 1) {
      return true;
    }
    return false;
  }

  // 检查队列是否为空
  boolean isEmpty() {
    if (front == -1)
      return true;
    else
      return false;
  }

  // 添加元素
  void enQueue(int element) {
    if (isFull()) {
      System.out.println("队列已满");
    } else {
      if (front == -1)
        front = 0;
      rear = (rear + 1) % SIZE;
      items[rear] = element;
      System.out.println("插入了 " + element);
    }
  }

  // 移除元素
  int deQueue() {
    int element;
    if (isEmpty()) {
      System.out.println("队列为空");
      return (-1);
    } else {
      element = items[front];
      if (front == rear) {
        front = -1;
        rear = -1;
      } /* 队列中只有一个元素，删除后重置队列。 */
      else {
        front = (front + 1) % SIZE;
      }
      return (element);
    }
  }

  void display() {
    /* 显示循环队列的状态 */
    int i;
    if (isEmpty()) {
      System.out.println("队列为空");
    } else {
      System.out.println("前端 -> " + front);
      System.out.println("元素 -> ");
      for (i = front; i != rear; i = (i + 1) % SIZE)
        System.out.print(items[i] + " ");
      System.out.println(items[i]);
      System.out.println("后端 -> " + rear);
    }
  }

  public static void main(String[] args) {

    CQueue q = new CQueue();

    // 失败，因为 front = -1
    q.deQueue();

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

    // 因 front == 0 && rear == SIZE - 1 而无法入队
    q.enQueue(6);

    q.display();

    int elem = q.deQueue();

    if (elem != -1) {
      System.out.println("删除的元素是 " + elem);
    }
    q.display();

    q.enQueue(7);

    q.display();

    // 因 front == rear + 1 而无法入队
    q.enQueue(8);
  }

}

// C 中的循环队列实现

#include <stdio.h>

#define SIZE 5

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

// 检查队列是否已满
int isFull() {
  if ((front == rear + 1) || (front == 0 && rear == SIZE - 1)) return 1;
  return 0;
}

// 检查队列是否为空
int isEmpty() {
  if (front == -1) return 1;
  return 0;
}

// 添加元素
void enQueue(int element) {
  if (isFull())
    printf("\n 队列已满！！ \n");
  else {
    if (front == -1) front = 0;
    rear = (rear + 1) % SIZE;
    items[rear] = element;
    printf("\n 插入 -> %d", element);
  }
}

// 移除元素
int deQueue() {
  int element;
  if (isEmpty()) {
    printf("\n 队列为空！！ \n");
    return (-1);
  } else {
    element = items[front];
    if (front == rear) {
      front = -1;
      rear = -1;
    }
    // 队列中只有一个元素，出队后重置队列。
    else {
      front = (front + 1) % SIZE;
    }
    printf("\n 删除的元素 -> %d \n", element);
    return (element);
  }
}

// 显示

队列
void display() {
  int i;
  if (isEmpty())
    printf(" \n 队列为空\n");
  else {
    printf("\n 前端 -> %d ", front);
    printf("\n 元素 -> ");
    for (i = front; i != rear; i = (i + 1) % SIZE) {
      printf("%d ", items[i]);
    }
    printf("%d ", items[i]);
    printf("\n 后端 -> %d \n", rear);
  }
}

int main() {
  // 失败，因为 front = -1
  deQueue();

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

  // 因 front == 0 && rear == SIZE - 1 而无法入队
  enQueue(6);

  display();
  deQueue();

  display();

  enQueue(7);
  display();

  // 因 front == rear + 1 而无法入队
  enQueue(8);

  return 0;
}

// C++ 中的循环队列实现

#include <iostream>
#define SIZE 5 /* 循环队列的大小 */

using namespace std;

class Queue {
   private:
  int items[SIZE], front, rear;

   public:
  Queue() {
    front = -1;
    rear = -1;
  }
  // 检查队列是否已满
  bool isFull() {
    if (front == 0 && rear == SIZE - 1) {
      return true;
    }
    if (front == rear + 1) {
      return true;
    }
    return false;
  }
  // 检查队列是否为空
  bool isEmpty() {
    if (front == -1)
      return true;
    else
      return false;
  }
  // 添加元素
  void enQueue(int element) {
    if (isFull()) {
      cout << "队列已满";
    } else {
      if (front == -1) front = 0;
      rear = (rear + 1) % SIZE;
      items[rear] = element;
      cout << endl
         << "已插入 " << element << endl;
    }
  }
  // 移除元素
  int deQueue() {
    int element;
    if (isEmpty()) {
      cout << "队列为空" << endl;
      return (-1);
    } else {
      element = items[front];
      if (front == rear) {
        front = -1;
        rear = -1;
      }
      // 如果队列中只有一个元素，
      // 那么我们在删除它后重置队列。
      else {
        front = (front + 1) % SIZE;
      }
      return (element);
    }
  }

  void display() {
    // 显示循环队列的状态
    int i;
    if (isEmpty()) {
      cout << endl
         << "队列为空" << endl;
    } else {
      cout << "前端 -> " << front;
      cout << endl
         << "元素 -> ";
      for (i = front; i != rear; i = (i + 1) % SIZE)
        cout << items[i];
      cout << items[i];
      cout << endl
         << "后端 -> " << rear;
    }
  }
};

int main() {
  Queue q;

  // 因为 front = -1 而失败
  q.deQueue();

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

  // 由于 front == 0 && rear == SIZE - 1 而无法入队
  q.enQueue(6);

  q.display();

  int elem = q.deQueue();

  if (elem != -1)
    cout << endl
       << "已删除的元素为 " << elem;

  q.display();

  q.enQueue(7);

  q.display();

  // 由于 front == rear + 1 而无法入队
  q.enQueue(8);

  return 0;
}

循环队列复杂度分析

循环队列的入队（enQueue）和出队（deQueue）操作的复杂度在数组实现中为 O(1)。

循环队列的应用

• CPU 调度
• 内存管理- 交通管理