循环队列是普通队列的扩展版本,在循环队列中,最后一个元素与第一个元素相连。因此形成了一种类似圆环的结构。
循环队列解决了普通队列的一个主要局限性。在普通队列中,经过一些插入和删除操作后,会出现无法利用的空闲空间。
在这里,只有在重置队列(删除所有元素)之后,索引 0 和 1 才能够被使用。这就减小了队列的实际可用大小。
循环队列是怎么工作的
循环队列是通过循环递增的过程来工作的,也就是说,当我们尝试递增指针,并且指针到达队列末尾时,我们会从队列的开头重新开始。 在这里,循环递增是通过对队列大小进行取模运算来实现的。也就是说,
如果 REAR + 1 == 5 (溢出!), REAR = (REAR + 1)%5 = 0 (队列起点处)
循环队列的操作
循环队列按如下方式工作:
- 两个指针
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++中的实现
最常用数组实现,也有用列表实现的
Python
# 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()
Java
// 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);
}
}
C
// 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;
}
C++
// 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)调度
- 内存管理
- 交通管理