循环队列图解与可视化

循环队列(Circular Queue)

介绍

循环队列是队列的一种变体，采用环形结构设计，解决了普通队列在数组实现中的"假溢出"问题。在普通队列中，随着元素的入队和出队，队头指针不断后移，会导致队列前部空间无法重复利用。而循环队列通过将队列的头尾相连，形成一个环形结构，可以重复利用这些空间。

循环队列一般用数组实现，通过两个指针（队头和队尾）和一些简单的计算来模拟循环结构。

核心特性

环形结构：当到达数组末尾时，下一个位置回到数组开头

空间重用：出队后的空间可以在后续入队操作中重复使用

高效的内存利用：避免了普通队列实现中的"假溢出"问题

固定大小：初始化时指定容量，一般不支持动态扩容

双指针管理：用front和rear指针跟踪队列状态

基本操作

1. 入队(enqueue)

时间复杂度：O(1)

描述：将元素添加到队列尾部，并更新尾指针

2. 出队(dequeue)

时间复杂度：O(1)

描述：移除并返回队列头部元素，并更新头指针

3. 查看队头(peek/front)

时间复杂度：O(1)

描述：查看队头元素但不移除

4. 判断队列是否为空(isEmpty)

时间复杂度：O(1)

描述：检查队列中是否有元素

5. 判断队列是否已满(isFull)

时间复杂度：O(1)

描述：检查队列是否已达到最大容量

基础实现

代码实现

Java

▼Java复制代码public class CircularQueue {

private Object[] array;

private int front; // 队头指针

private int rear; // 队尾指针

private int capacity;

private int size; // 当前元素数量

public CircularQueue(int capacity) {

this.capacity = capacity;

this.array = new Object[capacity];

this.front = 0;

this.rear = 0;

this.size = 0;

}

// 入队

public boolean enqueue(T item) {

if (isFull()) {

return false; // 队列已满

}

array[rear] = item;

rear = (rear + 1) % capacity; // 循环更新尾指针

size++;

return true;

}

// 出队

@SuppressWarnings("unchecked")

public T dequeue() {

if (isEmpty()) {

return null; // 队列为空

}

T item = (T) array[front];

array[front] = null; // 避免内存泄漏

front = (front + 1) % capacity; // 循环更新头指针

size--;

return item;

}

// 查看队头元素

@SuppressWarnings("unchecked")

public T peek() {

if (isEmpty()) {

return null;

}

return (T) array[front];

}

// 判断队列是否为空

public boolean isEmpty() {

return size == 0;

}

// 判断队列是否已满

public boolean isFull() {

return size == capacity;

}

// 获取队列当前大小

public int size() {

return size;

}

public static void main(String[] args) {

CircularQueue queue = new CircularQueue<>(5);

// 入队操作

queue.enqueue(10);

queue.enqueue(20);

queue.enqueue(30);

queue.enqueue(40);

System.out.println("队列大小: " + queue.size()); // 输出: 4

System.out.println("队头元素: " + queue.peek()); // 输出: 10

// 出队操作

System.out.println("出队元素: " + queue.dequeue()); // 输出: 10

System.out.println("出队元素: " + queue.dequeue()); // 输出: 20

// 继续入队，演示循环利用空间

queue.enqueue(50);

queue.enqueue(60);

System.out.println("队列是否已满: " + queue.isFull()); // 输出: true

System.out.println("队列大小: " + queue.size()); // 输出: 4

}

}

JavaScript 实现

▼Javascript复制代码class CircularQueue {

constructor(capacity) {

this.capacity = capacity;

this.queue = new Array(capacity);

this.front = 0;

this.rear = 0;

this.size = 0;

}

// 入队

enqueue(item) {

if (this.isFull()) {

return false; // 队列已满

}

this.queue[this.rear] = item;

this.rear = (this.rear + 1) % this.capacity;

this.size++;

return true;

}

// 出队

dequeue() {

if (this.isEmpty()) {

return null; // 队列为空

}

const item = this.queue[this.front];

this.queue[this.front] = undefined; // 避免内存泄漏

this.front = (this.front + 1) % this.capacity;

this.size--;

return item;

}

// 查看队头元素

peek() {

if (this.isEmpty()) {

return null;

}

return this.queue[this.front];

}

// 判断队列是否为空

isEmpty() {

return this.size === 0;

}

// 判断队列是否已满

isFull() {

return this.size === this.capacity;

}

// 获取队列当前大小

getSize() {

return this.size;

}

}

// 使用示例

const queue = new CircularQueue(5);

// 入队操作

queue.enqueue(10);

queue.enqueue(20);

queue.enqueue(30);

queue.enqueue(40);

console.log("队列大小:", queue.getSize()); // 输出: 4

console.log("队头元素:", queue.peek()); // 输出: 10

// 出队操作

console.log("出队元素:", queue.dequeue()); // 输出: 10

console.log("出队元素:", queue.dequeue()); // 输出: 20

// 继续入队，演示循环利用空间

queue.enqueue(50);

queue.enqueue(60);

console.log("队列是否已满:", queue.isFull()); // 输出: true

console.log("队列大小:", queue.getSize()); // 输出: 4

Python 实现

▼Python复制代码class CircularQueue:

def __init__(self, capacity):

self.capacity = capacity

self.queue = [None] * capacity

self.front = 0

self.rear = 0

self.size = 0

# 入队

def enqueue(self, item):

if self.is_full():

return False # 队列已满

self.queue[self.rear] = item

self.rear = (self.rear + 1) % self.capacity

self.size += 1

return True

# 出队

def dequeue(self):

if self.is_empty():

return None # 队列为空

item = self.queue[self.front]

self.queue[self.front] = None

self.front = (self.front + 1) % self.capacity

self.size -= 1

return item

# 查看队头元素

def peek(self):

if self.is_empty():

return None

return self.queue[self.front]

# 判断队列是否为空

def is_empty(self):

return self.size == 0

# 判断队列是否已满

def is_full(self):

return self.size == self.capacity

# 获取队列当前大小

def get_size(self):

return self.size

# 使用示例

if __name__ == "__main__":

queue = CircularQueue(5)

# 入队操作

queue.enqueue(10)

queue.enqueue(20)

queue.enqueue(30)

queue.enqueue(40)

print("队列大小:", queue.get_size()) # 输出: 4

print("队头元素:", queue.peek()) # 输出: 10

# 出队操作

print("出队元素:", queue.dequeue()) # 输出: 10

print("出队元素:", queue.dequeue()) # 输出: 20

# 继续入队，演示循环利用空间

queue.enqueue(50)

queue.enqueue(60)

print("队列是否已满:", queue.is_full()) # 输出: True

print("队列大小:", queue.get_size()) # 输出: 4

C 实现

▼C复制代码#include

#include

#include

typedef struct {

int* array;

int front;

int rear;

int capacity;

int size;

} CircularQueue;

// 初始化循环队列

CircularQueue* createCircularQueue(int capacity) {

CircularQueue* queue = (CircularQueue*)malloc(sizeof(CircularQueue));

queue->array = (int*)malloc(sizeof(int) * capacity);

queue->front = 0;

queue->rear = 0;

queue->capacity = capacity;

queue->size = 0;

return queue;

}

// 判断队列是否为空

bool isEmpty(CircularQueue* queue) {

return queue->size == 0;

}

// 判断队列是否已满

bool isFull(CircularQueue* queue) {

return queue->size == queue->capacity;

}

// 入队

bool enqueue(CircularQueue* queue, int item) {

if (isFull(queue)) {

return false;

}

queue->array[queue->rear] = item;

queue->rear = (queue->rear + 1) % queue->capacity;

queue->size++;

return true;

}

// 出队

bool dequeue(CircularQueue* queue, int* result) {

if (isEmpty(queue)) {

return false;

}

*result = queue->array[queue->front];

queue->front = (queue->front + 1) % queue->capacity;

queue->size--;

return true;

}

// 查看队头元素

bool peek(CircularQueue* queue, int* result) {

if (isEmpty(queue)) {

return false;

}

*result = queue->array[queue->front];

return true;

}

// 获取队列大小

int size(CircularQueue* queue) {

return queue->size;

}

// 释放队列内存

void destroyCircularQueue(CircularQueue* queue) {

free(queue->array);

free(queue);

}

int main() {

CircularQueue* queue = createCircularQueue(5);

// 入队操作

enqueue(queue, 10);

enqueue(queue, 20);

enqueue(queue, 30);

enqueue(queue, 40);

printf("队列大小: %d

", size(queue)); // 输出: 4

int frontValue;

peek(queue, &frontValue);

printf("队头元素: %d

", frontValue); // 输出: 10

// 出队操作

int dequeuedItem;

dequeue(queue, &dequeuedItem);

printf("出队元素: %d

", dequeuedItem); // 输出: 10

dequeue(queue, &dequeuedItem);

printf("出队元素: %d

", dequeuedItem); // 输出: 20

// 继续入队，演示循环利用空间

enqueue(queue, 50);

enqueue(queue, 60);

printf("队列是否已满: %s

", isFull(queue) ? "是" : "否"); // 输出: 是

printf("队列大小: %d

", size(queue)); // 输出: 4

destroyCircularQueue(queue);

return 0;

}

Go 实现

▼Go复制代码package main

import (

"fmt"

)

// CircularQueue 循环队列结构

type CircularQueue struct {

items []interface{}

front int

rear int

size int

capacity int

}

// NewCircularQueue 创建新的循环队列

func NewCircularQueue(capacity int) *CircularQueue {

return &CircularQueue{

items: make([]interface{}, capacity),

front: 0,

rear: 0,

size: 0,

capacity: capacity,

}

}

// Enqueue 入队

func (q *CircularQueue) Enqueue(item interface{}) bool {

if q.IsFull() {

return false

}

q.items[q.rear] = item

q.rear = (q.rear + 1) % q.capacity

q.size++

return true

}

// Dequeue 出队

func (q *CircularQueue) Dequeue() (interface{}, bool) {

if q.IsEmpty() {

return nil, false

}

item := q.items[q.front]

q.items[q.front] = nil // 避免内存泄漏

q.front = (q.front + 1) % q.capacity

q.size--

return item, true

}

// Peek 查看队头元素

func (q *CircularQueue) Peek() (interface{}, bool) {

if q.IsEmpty() {

return nil, false

}

return q.items[q.front], true

}

// IsEmpty 判断队列是否为空

func (q *CircularQueue) IsEmpty() bool {

return q.size == 0

}

// IsFull 判断队列是否已满

func (q *CircularQueue) IsFull() bool {

return q.size == q.capacity

}

// Size 获取队列当前大小

func (q *CircularQueue) Size() int {

return q.size

}

func main() {

queue := NewCircularQueue(5)

// 入队操作

queue.Enqueue(10)

queue.Enqueue(20)

queue.Enqueue(30)

queue.Enqueue(40)

fmt.Println("队列大小:", queue.Size()) // 输出: 4

frontValue, _ := queue.Peek()

fmt.Println("队头元素:", frontValue) // 输出: 10

// 出队操作

item1, _ := queue.Dequeue()

fmt.Println("出队元素:", item1) // 输出: 10

item2, _ := queue.Dequeue()

fmt.Println("出队元素:", item2) // 输出: 20

// 继续入队，演示循环利用空间

queue.Enqueue(50)

queue.Enqueue(60)

fmt.Println("队列是否已满:", queue.IsFull()) // 输出: true

fmt.Println("队列大小:", queue.Size()) // 输出: 4

}

C++ 实现

▼C++复制代码#include

#include

#include

template

class CircularQueue {

private:

std::vector items;

int front;

int rear;

int size;

int capacity;

public:

CircularQueue(int capacity) : front(0), rear(0), size(0), capacity(capacity) {

items.resize(capacity);

}

// 入队

bool enqueue(T item) {

if (isFull()) {

return false;

}

items[rear] = item;

rear = (rear + 1) % capacity;

size++;

return true;

}

// 出队

T dequeue() {

if (isEmpty()) {

throw std::runtime_error("队列为空");

}

T item = items[front];

front = (front + 1) % capacity;

size--;

return item;

}

// 查看队头元素

T peek() {

if (isEmpty()) {

throw std::runtime_error("队列为空");

}

return items[front];

}

// 判断队列是否为空

bool isEmpty() {

return size == 0;

}

// 判断队列是否已满

bool isFull() {

return size == capacity;

}

// 获取队列当前大小

int getSize() {

return size;

}

};

int main() {

CircularQueue queue(5);

// 入队操作

queue.enqueue(10);

queue.enqueue(20);

queue.enqueue(30);

queue.enqueue(40);

std::cout << "队列大小: " << queue.getSize() << std::endl; // 输出: 4

std::cout << "队头元素: " << queue.peek() << std::endl; // 输出: 10

// 出队操作

std::cout << "出队元素: " << queue.dequeue() << std::endl; // 输出: 10

std::cout << "出队元素: " << queue.dequeue() << std::endl; // 输出: 20

// 继续入队，演示循环利用空间

queue.enqueue(50);

queue.enqueue(60);

std::cout << "队列是否已满: " << (queue.isFull() ? "是" : "否") << std::endl; // 输出: 是

std::cout << "队列大小: " << queue.getSize() << std::endl; // 输出: 4

return 0;

}

优缺点

优点

高效空间利用：可以重用已出队的空间，避免"假溢出"问题

固定内存开销：内存使用量可预测，适合内存受限环境

操作高效：所有基本操作都是O(1)时间复杂度

实现简单：比链表实现的队列更简单，内存布局更紧凑

缺点

固定大小：初始化后容量固定，不易动态调整

空间判断复杂：需要额外的计数或标记来区分队列满和空的状态

不支持随机访问：只能访问队头和队尾元素

内存分配低效：若设置过大可能造成内存浪费，过小则频繁溢出

应用场景

缓冲区实现：键盘缓冲、打印机队列等I/O操作

内存管理：操作系统中的内存页面置换算法

任务调度：嵌入式系统中的任务调度器

数据流处理：有界的生产者消费者模式

CPU调度：操作系统中的进程调度

测验

循环队列与普通队列的主要区别是什么？

在循环队列中，怎么判断队列是空还是满？

当循环队列的rear指针到达数组末尾时，下一个元素应该被放在哪里？

循环队列解决了什么问题？

在实现循环队列时，如何计算下一个位置的索引？

测验答案

循环队列采用环形结构设计，可以重复利用出队后的空间，解决了普通队列在数组实现中的"假溢出"问题。

有多种方法：(1)使用一个额外的计数变量size来记录元素数量；(2)保持一个空位，当(rear+1)%capacity==front时队列满；(3)使用一个标志变量来区分。

应该被放在数组的开头(索引0)，这就是循环队列的环形特性。

循环队列解决了普通数组实现队列时的"假溢出"问题，即队列前部有空间但无法使用的情况。

使用取模运算：(current_index + 1) % capacity。这样当索引到达数组末尾时，会自动回到开头。

相关的LeetCode热门题目

622. 设计循环队列 - 直接实现一个循环队列。

641. 设计循环双端队列 - 实现一个支持在两端插入和删除的循环队列。

859. 亲密字符串 - 可以使用循环队列来处理字符的循环比较。

933. 最近的请求次数 - 使用循环队列来保持最近的请求记录。

1670. 设计前中后队列 - 扩展循环队列的思想，设计更复杂的队列结构。