DB1-循环链式队列（只设置队尾指针）
代码实现
| C |
|---|
| #include <stdio.h>
#include <stdlib.h>
/**
* 循环单链表结点定义
*/
typedef struct LNode {
int data; // 数据域
struct LNode* next; // 指针域
} LNode, *LinkList;
/**
* 初始化循环队列（只设置队尾指针）
* @param tail 指向队尾指针的指针
* @return 初始化成功返回true，失败返回false
*/
bool init_queue(LinkList* tail) {
// 创建头结点
LinkList head = (LinkList)malloc(sizeof(LNode));
if (head == NULL) {
printf("内存分配失败\n");
return false;
}
// 头结点数据域可设为默认值
head->data = 0;
// 头结点指向自己，形成空循环队列
head->next = head;
// 队尾指针指向头结点
*tail = head;
return true;
}
|
| C |
|---|
| /**
* 入队操作（在队尾插入元素）
* @param tail 指向队尾指针的指针
* @param x 要入队的元素
* @return 入队成功返回true，失败返回false
*/
bool enqueue(LinkList* tail, int x) {
// 参数检查
if (tail == NULL || *tail == NULL) {
printf("队列指针为空\n");
return false;
}
// 创建新结点
LinkList p = (LinkList)malloc(sizeof(LNode));
if (p == NULL) {
printf("内存分配失败\n");
return false;
}
// 设置新结点数据
p->data = x;
// 在队尾插入新结点（循环链表的特点）
p->next = (*tail)->next; // 新结点指向头结点
(*tail)->next = p; // 原队尾结点指向新结点
(*tail) = p; // 更新队尾指针指向新结点
return true;
}
/**
* 出队操作（从队头删除元素）
* @param tail 指向队尾指针的指针
* @param x 指向存储出队元素的指针
* @return 出队成功返回true，队空返回false
*/
bool dequeue(LinkList* tail, int* x) {
// 参数检查
if (tail == NULL || *tail == NULL || x == NULL) {
printf("参数错误\n");
return false;
}
// 检查队列是否为空
if ((*tail)->next == *tail) {
printf("队列为空，无法出队\n");
return false; // 队空
}
// 获取队头结点（头结点的下一个结点）
LinkList head = (*tail)->next; // 头结点
LinkList first = head->next; // 队头元素结点
// 获取队头元素
*x = first->data;
// 删除队头结点
if (first == *tail) {
// 如果队列中只有一个数据结点
head->next = head; // 头结点指向自己
*tail = head; // 队尾指针重新指向头结点
} else {
// 队列中有多个数据结点
head->next = first->next; // 头结点指向第二个结点
}
// 释放被删除结点的内存
free(first);
return true;
}
/**
* 判断队列是否为空
* @param tail 队尾指针
* @return 空队列返回true，非空返回false
*/
bool isEmpty(LinkList tail) {
// 空队列：队尾指针指向头结点，且头结点指向自己
return (tail != NULL && tail->next == tail);
}
/**
* 获取队头元素（不删除）
* @param tail 队尾指针
* @param x 指向存储队头元素的指针
* @return 获取成功返回true，队空返回false
*/
bool getFront(LinkList tail, int* x) {
// 参数检查
if (tail == NULL || x == NULL) {
return false;
}
// 检查队列是否为空
if (tail->next == tail) {
return false; // 队空
}
// 获取队头元素（头结点的下一个结点）
*x = tail->next->next->data;
return true;
}
/**
* 销毁队列，释放所有内存
* @param tail 指向队尾指针的指针
*/
void destroy_queue(LinkList* tail) {
if (tail == NULL || *tail == NULL) {
return;
}
LinkList head = (*tail)->next; // 头结点
LinkList current = head->next; // 第一个数据结点
// 释放所有数据结点
while (current != head) {
LinkList temp = current;
current = current->next;
free(temp);
}
// 释放头结点
free(head);
// 置空队尾指针
*tail = NULL;
}
|
循环链表队列结构图解
队列结构特点：
| Text Only |
|---|
| 循环链表队列结构：
队尾指针tail指向最后一个数据结点
头结点不存储数据，用于标识队列边界
空队列：
tail → [头] → [头] → ...
↑____________│
非空队列：
tail → [头] → [1] → [2] → [3] → [头] → ...
↑___________________________│
|
入队操作过程：
| Text Only |
|---|
| 初始状态：tail → [头] → [1] → [2] → [头] → ...
↑ ↑
head tail
入队元素3：
步骤1：创建新结点[3]
步骤2：[3]->next = head
步骤3：tail->next = [3]
步骤4：tail = [3]
结果：tail → [头] → [1] → [2] → [3] → [头] → ...
↑ ↑
head new tail
|
出队操作过程：
| Text Only |
|---|
| 队列：tail → [头] → [1] → [2] → [3] → [头] → ...
↑____↑ ↑
head front tail
出队元素1：
步骤1：获取front结点[1]的数据
步骤2：head->next = [2]（跳过[1]）
步骤3：释放[1]的内存
结果：tail → [头] → [2] → [3] → [头] → ...
↑____↑ ↑
head new front tail
|
算法执行流程图解
入队操作详细步骤：
| Text Only |
|---|
| 入队前：
tail → [H] → [A] → [B] → [H] → ...
↑ ↑
head current tail
入队元素C：
1. 创建结点[C]
[C] → ?
2. C->next = head
[C] → [H] → [A] → [B] → [H] → ...
↑
tail
3. tail->next = C
[H] → [A] → [B] → [C] → [H] → ...
↑ ↑
head tail->next
4. tail = C
tail → [H] → [A] → [B] → [C] → [H] → ...
↑ ↑
head new tail
|
出队操作详细步骤：
| Text Only |
|---|
| 出队前：
tail → [H] → [A] → [B] → [C] → [H] → ...
↑____↑ ↑
head front tail
出队元素A：
1. 获取front结点[A]的数据
2. head->next = B（删除A）
tail → [H] → [B] → [C] → [H] → ...
↑____↑ ↑
head new front tail
3. free(A)
|
复杂度分析
时间复杂度：O(1)
- 入队操作：直接在队尾插入，O(1)
- 出队操作：通过头结点直接访问队头，O(1)
- 判空操作：简单指针比较，O(1)
- 总体时间复杂度：O(1)
空间复杂度：O(1)
- 入队操作：只创建一个新结点，O(1)
- 出队操作：只释放一个结点，O(1)
- 辅助空间：只使用常数个指针变量
- 总体空间复杂度：O(1)
算法优化版本
| C |
|---|
| /**
* 优化版本：添加计数器
*/
typedef struct {
LinkList tail; // 队尾指针
int count; // 队列元素个数
} OptimizedQueue;
bool enqueue_optimized(OptimizedQueue* q, int x) {
if (q == NULL) return false;
LinkList p = (LinkList)malloc(sizeof(LNode));
if (p == NULL) return false;
p->data = x;
p->next = q->tail->next;
q->tail->next = p;
q->tail = p;
q->count++;
return true;
}
bool dequeue_optimized(OptimizedQueue* q, int* x) {
if (q == NULL || x == NULL || q->count == 0) {
return false;
}
LinkList head = q->tail->next;
LinkList first = head->next;
*x = first->data;
if (first == q->tail) {
head->next = head;
q->tail = head;
} else {
head->next = first->next;
}
free(first);
q->count--;
return true;
}
int getSize(OptimizedQueue q) {
return q.count;
}
|
与其他队列实现的对比
| 实现方式 |
时间复杂度 |
空间复杂度 |
特点 |
| 顺序队列 |
O(1) |
O(n) |
简单但可能假溢出 |
| 循环队列 |
O(1) |
O(n) |
高效但需预分配空间 |
| 链队列(双指针) |
O(1) |
O(1) |
动态分配但需维护两个指针 |
| 链队列(单尾指针) |
O(1) |
O(1) |
最优：单指针维护，动态分配 |
测试用例
| C |
|---|
| /**
* 测试函数
*/
void test_circular_queue() {
LinkList tail;
// 初始化队列
if (!init_queue(&tail)) {
printf("初始化失败\n");
return;
}
printf("队列初始化完成\n");
printf("队列是否为空：%s\n", isEmpty(tail) ? "是" : "否");
// 测试入队
for (int i = 1; i <= 5; i++) {
if (enqueue(&tail, i)) {
printf("入队：%d\n", i);
} else {
printf("入队失败：%d\n", i);
}
}
// 测试获取队头元素
int front;
if (getFront(tail, &front)) {
printf("队头元素：%d\n", front);
}
// 测试出队
int x;
while (dequeue(&tail, &x)) {
printf("出队：%d\n", x);
}
printf("队列是否为空：%s\n", isEmpty(tail) ? "是" : "否");
// 销毁队列
destroy_queue(&tail);
}
|
算法特点
核心思想：
利用循环单链表的特性，只维护队尾指针，通过队尾指针可以访问到头结点和队头元素。
关键技术：
1. 循环链表：头结点指向第一个数据结点，队尾指向头结点
2. 单指针维护：只维护队尾指针，通过链表特性访问队头
3. O(1)操作：入队在尾部，出队通过头结点
优势：
- 时间效率：所有操作都是O(1)时间复杂度
- 空间效率：动态分配，不浪费空间
- 实现简洁：只需要维护一个指针
- 无容量限制：不像数组实现有固定大小限制
应用场景：
- 操作系统任务队列
- 网络数据包处理
- 生产者消费者模式
- 广度优先搜索
- 缓冲区管理
这种只使用队尾指针的循环链表队列实现是队列数据结构的最优实现之一，在实际应用中具有很高的实用价值。