上查看所有课程
循环队列是普通队列的扩展版本，其中最后一个元素连接到第一个元素。从而形成一个类似圆的结构。
循环队列解决了普通队列的主要限制。在普通队列中，经过一些插入和删除后，会留下无法使用的空空间。
在这里，索引0和1只有在重置队列（删除所有元素）后才能使用。这会减小队列的实际大小。
循环队列如何工作
循环队列通过循环递增过程工作，即当我们尝试递增指针并到达队列末尾时，我们从队列的开头开始。
在这里，循环递增是通过对队列大小进行模运算来实现的。即，
if REAR + 1 == 5 (overflow!), REAR = (REAR + 1)%5 = 0 (start of queue)循环队列操作
循环队列的工作原理如下
- 两个指针 FRONT 和 REAR
- FRONT 指示队列的第一个元素
- REAR 指示队列的最后一个元素
- 最初，将 FRONT 和 REAR 的值设置为 -1
1. 入队操作
- 检查队列是否已满
- 对于第一个元素，将 FRONT 的值设置为 0
- 循环递增 REAR 索引 1（即如果尾部到达末尾，下一个将在队列的开头）
- 将新元素添加到 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++ 中的循环队列实现
最常见的队列实现是使用数组，但也可以使用列表实现。
# Circular Queue implementation in Python
class MyCircularQueue():
def __init__(self, k):
self.k = k
self.queue = [None] * k
self.head = self.tail = -1
# Insert an element into the circular queue
def enqueue(self, data):
if ((self.tail + 1) % self.k == self.head):
print("The circular queue is full\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
# Delete an element from the circular queue
def dequeue(self):
if (self.head == -1):
print("The circular queue is empty\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("No element in the circular queue")
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()
# Your MyCircularQueue object will be instantiated and called as such:
obj = MyCircularQueue(5)
obj.enqueue(1)
obj.enqueue(2)
obj.enqueue(3)
obj.enqueue(4)
obj.enqueue(5)
print("Initial queue")
obj.printCQueue()
obj.dequeue()
print("After removing an element from the queue")
obj.printCQueue()// Circular Queue implementation in Java
public class CQueue {
int SIZE = 5; // Size of Circular Queue
int front, rear;
int items[] = new int[SIZE];
CQueue() {
front = -1;
rear = -1;
}
// Check if the queue is full
boolean isFull() {
if (front == 0 && rear == SIZE - 1) {
return true;
}
if (front == rear + 1) {
return true;
}
return false;
}
// Check if the queue is empty
boolean isEmpty() {
if (front == -1)
return true;
else
return false;
}
// Adding an element
void enQueue(int element) {
if (isFull()) {
System.out.println("Queue is full");
} else {
if (front == -1)
front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
System.out.println("Inserted " + element);
}
}
// Removing an element
int deQueue() {
int element;
if (isEmpty()) {
System.out.println("Queue is empty");
return (-1);
} else {
element = items[front];
if (front == rear) {
front = -1;
rear = -1;
} /* Q has only one element, so we reset the queue after deleting it. */
else {
front = (front + 1) % SIZE;
}
return (element);
}
}
void display() {
/* Function to display status of Circular Queue */
int i;
if (isEmpty()) {
System.out.println("Empty Queue");
} else {
System.out.println("Front -> " + front);
System.out.println("Items -> ");
for (i = front; i != rear; i = (i + 1) % SIZE)
System.out.print(items[i] + " ");
System.out.println(items[i]);
System.out.println("Rear -> " + rear);
}
}
public static void main(String[] args) {
CQueue q = new CQueue();
// Fails because front = -1
q.deQueue();
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
q.enQueue(4);
q.enQueue(5);
// Fails to enqueue because front == 0 && rear == SIZE - 1
q.enQueue(6);
q.display();
int elem = q.deQueue();
if (elem != -1) {
System.out.println("Deleted Element is " + elem);
}
q.display();
q.enQueue(7);
q.display();
// Fails to enqueue because front == rear + 1
q.enQueue(8);
}
}// Circular Queue implementation in C
#include <stdio.h>
#define SIZE 5
int items[SIZE];
int front = -1, rear = -1;
// check if the queue is full
int isFull() {
if ((front == (rear + 1) % SIZE) || (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;
}// Circular Queue implementation in C++
#include <iostream>
#define SIZE 5 /* Size of Circular Queue */
using namespace std;
class Queue {
private:
int items[SIZE], front, rear;
public:
Queue() {
front = -1;
rear = -1;
}
// Check if the queue is full
bool isFull() {
if (front == 0 && rear == SIZE - 1) {
return true;
}
if (front == (rear + 1) % SIZE) {
return true;
}
return false;
}
// Check if the queue is empty
bool isEmpty() {
if (front == -1)
return true;
else
return false;
}
// Adding an element
void enQueue(int element) {
if (isFull()) {
cout << "Queue is full" << endl;
} else {
if (front == -1) front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
cout << endl
<< "Inserted " << element << endl;
}
}
// Removing an element
int deQueue() {
int element;
if (isEmpty()) {
cout << "Queue is empty" << endl;
return (-1);
} else {
element = items[front];
if (front == rear) {
front = -1;
rear = -1;
}
// Q has only one element,
// so we reset the queue after deleting it.
else {
front = (front + 1) % SIZE;
}
return (element);
}
}
void display() {
// Function to display status of Circular Queue
int i;
if (isEmpty()) {
cout << endl
<< "Empty Queue" << endl;
} else {
cout << "Front -> " << front;
cout << endl
<< "Items -> ";
for (i = front; i != rear; i = (i + 1) % SIZE)
cout << items[i] << "\t";
cout << items[i];
cout << endl
<< "Rear -> " << rear << endl;
}
}
};
int main() {
Queue q;
// Fails because front = -1
q.deQueue();
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
q.enQueue(4);
q.enQueue(5);
// Fails to enqueue because front == 0 && rear == SIZE - 1
q.enQueue(6);
q.display();
int elem = q.deQueue();
if (elem != -1)
cout << endl
<< "Deleted Element is " << elem << endl;
q.display();
q.enQueue(7);
q.display();
// Fails to enqueue because front == rear + 1
q.enQueue(8);
return 0;
}循环队列复杂度分析
循环队列的入队和出队操作的复杂度对于（数组实现）为 O(1)。
循环队列的应用
- CPU 调度
- 内存管理
- 交通管理