当前位置：首页 > news >正文

《数据结构笔记六》队列 ⭐⭐⭐

news 2025/5/30 18:05:04

一、队列的基本概念与特性

队列（Queue） 是一种 先进先出（FIFO, First In First Out） 的线性数据结构，核心操作包括：

enqueue：元素入队（添加到队尾）
dequeue：元素出队（移除队首元素）
front：查看队首元素（不移除）
isEmpty：判断队列是否为空
isFull：判断队列是否已满（仅限固定容量队列）

二、C语言实现队列（基于循环数组）

1. 队列的结构定义

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>#define MAX_SIZE 5  // 队列的最大容量typedef struct {int front;      // 队首指针（指向第一个元素）int rear;       // 队尾指针（指向最后一个元素的下一个位置）int capacity;   // 队列容量int* array;     // 存储元素的数组
} Queue;

2. 核心操作函数

// 初始化队列
Queue* createQueue(int capacity) {Queue* queue = (Queue*)malloc(sizeof(Queue));queue->capacity = capacity;queue->front = 0;queue->rear = 0;queue->array = (int*)malloc(capacity * sizeof(int));return queue;
}
// 判断队列是否为空
bool isEmpty(Queue* queue) {return queue->front == queue->rear;
}
// 判断队列是否已满
bool isFull(Queue* queue) {return (queue->rear + 1) % queue->capacity == queue->front;
}// 入队操作
void enqueue(Queue* queue, int item) {if (isFull(queue)) {printf("Queue is full! Cannot enqueue %d\n", item);return;}queue->array[queue->rear] = item;queue->rear = (queue->rear + 1) % queue->capacity;  // 循环移动指针
}// 出队操作
int dequeue(Queue* queue) {if (isEmpty(queue)) {printf("Queue is empty!\n");return -1;  // 错误码}int item = queue->array[queue->front];queue->front = (queue->front + 1) % queue->capacity;  // 循环移动指针return item;
}
// 查看队首元素
int front(Queue* queue) {if (isEmpty(queue)) {printf("Queue is empty!\n");return -1;}return queue->array[queue->front];
}
// 释放队列内存
void freeQueue(Queue* queue) {free(queue->array);free(queue);
}

3. 测试用例

int main() {Queue* queue = createQueue(MAX_SIZE);enqueue(queue, 10);enqueue(queue, 20);enqueue(queue, 30);enqueue(queue, 40);  // 队列满（MAX_SIZE=5时实际可用容量为4，因循环队列需浪费一个位置）printf("Front element: %d\n", front(queue));  // 应输出10printf("Dequeued: %d\n", dequeue(queue));     // 10出队printf("Dequeued: %d\n", dequeue(queue));     // 20出队enqueue(queue, 50);  // 入队50enqueue(queue, 60);  // 入队60printf("Queue is full? %s\n", isFull(queue) ? "Yes" : "No");  // 应输出YesfreeQueue(queue);return 0;
}

三、深度分析

1. 循环数组设计的必要性

假溢出问题：
普通数组实现队列时，rear指针到达数组末尾后即使前面有空位也无法继续入队（假溢出）。
循环数组通过取模运算（(rear + 1) % capacity）实现指针循环，复用空闲空间。
队列空/满判断：
- 空队列：front == rear
- 满队列：(rear + 1) % capacity == front
- 牺牲一个存储单元：为了区分空和满状态，实际可用容量为 capacity - 1。

2. 核心操作的时间复杂度

操作	时间复杂度	说明
`enqueue`	O(1)	直接操作队尾指针
`dequeue`	O(1)	直接操作队首指针
`front`	O(1)	直接访问队首元素
`isEmpty`	O(1)	检查 `front == rear`

3. 数组实现 vs 链表实现

特性	数组实现	链表实现
内存占用	固定容量，可能浪费空间	动态分配，无容量限制
扩容成本	需重新分配内存并复制数据（O(n)）	动态添加节点（O(1)）
访问速度	缓存友好，连续内存访问	指针跳转，缓存不友好
实现复杂度	需处理循环指针逻辑	需维护头尾节点指针

4. 应用场景

任务调度：操作系统中的进程就绪队列。
数据缓冲：网络数据包的接收缓冲区。
广度优先搜索（BFS）：按层级遍历树或图。
打印机任务队列：按顺序处理打印请求。

四、链表实现队列

typedef struct Node {int data;struct Node* next;
} Node;typedef struct {Node* front;  // 队首指针Node* rear;   // 队尾指针
} LinkedQueue;// 初始化链表队列
LinkedQueue* createLinkedQueue() {LinkedQueue* queue = (LinkedQueue*)malloc(sizeof(LinkedQueue));queue->front = queue->rear = NULL;return queue;
}// 入队（链表尾插法）
void linkedEnqueue(LinkedQueue* queue, int data) {Node* newNode = (Node*)malloc(sizeof(Node));newNode->data = data;newNode->next = NULL;if (queue->rear == NULL) {  // 空队列queue->front = queue->rear = newNode;} else {queue->rear->next = newNode;queue->rear = newNode;}
}// 出队
int linkedDequeue(LinkedQueue* queue) {if (queue->front == NULL) return -1;Node* temp = queue->front;int data = temp->data;queue->front = queue->front->next;if (queue->front == NULL) {  // 队列空后重置rearqueue->rear = NULL;}free(temp);return data;
}

五、关键设计细节

循环指针的数学运算：
- 入队时更新 rear：rear = (rear + 1) % capacity
- 出队时更新 front：front = (front + 1) % capacity
动态扩容策略（可选）：
- 当队列满时，可分配更大的数组并迁移数据（例如容量翻倍）。
错误处理：
- 入队时检测队列满，出队时检测队列空。
内存管理：
- 链表实现需逐个释放节点内存。