算法描述
双向队列（Double-Ended Queue，简称Deque）是一种允许在队列的前端（front）和后端（rear） 进行插入和删除操作的线性数据结构。它结合了栈和队列的特性，提供了更灵活的数据操作方式。
核心操作：
pushFront(value)- 在队头插入元素pushRear(value)- 在队尾插入元素popFront()- 删除并返回队头元素popRear()- 删除并返回队尾元素getFront()- 获取队头元素（不删除）getRear()- 获取队尾元素（不删除）
实现特点：
- 循环数组：使用取模运算实现空间的循环利用
- size计数器：通过size变量判断空/满状态，不浪费空间
- 边界处理：正确处理空队列和满队列的特殊情况
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_SIZE 10 // 队列最大容量
typedef struct {
int data[MAX_SIZE];
int front;
int rear;
int size; // 当前元素数量
} Deque;
// 初始化队列
void initDeque(Deque *dq) {
dq->front = -1;
dq->rear = 0;
dq->size = 0;
}
// 检查队列是否为空
bool isEmpty(Deque *dq) {
return dq->size == 0;
}
// 检查队列是否已满
bool isFull(Deque *dq) {
return dq->size == MAX_SIZE;
}
// 从队头入队
bool pushFront(Deque *dq, int value) {
if (isFull(dq)) {
printf("队列已满，无法从队头插入\n");
return false;
}
if (isEmpty(dq)) {
dq->front = 0;
dq->rear = 0;
} else {
dq->front = (dq->front - 1 + MAX_SIZE) % MAX_SIZE;
}
dq->data[dq->front] = value;
dq->size++;
return true;
}
// 从队尾入队
bool pushRear(Deque *dq, int value) {
if (isFull(dq)) {
printf("队列已满，无法从队尾插入\n");
return false;
}
if (isEmpty(dq)) {
dq->front = 0;
dq->rear = 0;
} else {
dq->rear = (dq->rear + 1) % MAX_SIZE;
}
dq->data[dq->rear] = value;
dq->size++;
return true;
}
// 从队头出队
bool popFront(Deque *dq, int *value) {
if (isEmpty(dq)) {
printf("队列为空，无法从队头删除\n");
return false;
}
*value = dq->data[dq->front];
dq->front = (dq->front + 1) % MAX_SIZE;
dq->size--;
if (isEmpty(dq)) {
dq->front = -1;
dq->rear = -1;
}
return true;
}
// 从队尾出队
bool popRear(Deque *dq, int *value) {
if (isEmpty(dq)) {
printf("队列为空，无法从队尾删除\n");
return false;
}
*value = dq->data[dq->rear];
dq->rear = (dq->rear - 1 + MAX_SIZE) % MAX_SIZE;
dq->size--;
if (isEmpty(dq)) {
dq->front = -1;
dq->rear = -1;
}
return true;
}
// 获取队头元素
bool getFront(Deque *dq, int *value) {
if (isEmpty(dq)) {
printf("队列为空\n");
return false;
}
*value = dq->data[dq->front];
return true;
}
// 获取队尾元素
bool getRear(Deque *dq, int *value) {
if (isEmpty(dq)) {
printf("队列为空\n");
return false;
}
*value = dq->data[dq->rear];
return true;
}
// 打印队列中的所有元素
void printDeque(Deque *dq) {
if (isEmpty(dq)) {
printf("队列为空\n");
return;
}
printf("队列元素(从前到后): ");
int i = dq->front;
int count = 0;
while (count < dq->size) {
printf("%d ", dq->data[i]);
i = (i + 1) % MAX_SIZE;
count++;
}
printf("\n");
}
int main() {
Deque dq;
initDeque(&dq);
int value;
printf("=== 双向队列测试 ===\n");
// 测试从队尾入队
pushRear(&dq, 10);
pushRear(&dq, 20);
pushRear(&dq, 30);
printf("从队尾插入10,20,30后: ");
printDeque(&dq);
// 测试从队头入队
pushFront(&dq, 5);
pushFront(&dq, 2);
printf("从队头插入5,2后: ");
printDeque(&dq);
// 测试获取元素
getFront(&dq, &value);
printf("队头元素: %d\n", value);
getRear(&dq, &value);
printf("队尾元素: %d\n", value);
// 测试从队头出队
popFront(&dq, &value);
printf("从队头删除: %d\n", value);
printf("删除后: ");
printDeque(&dq);
// 测试从队尾出队
popRear(&dq, &value);
printf("从队尾删除: %d\n", value);
printf("删除后: ");
printDeque(&dq);
// 测试继续插入
pushFront(&dq, 1);
pushRear(&dq, 40);
printf("继续插入1(头),40(尾)后: ");
printDeque(&dq);
return 0;
}
双向队列的特点：
核心操作：
pushFront()- 从队头插入元素pushRear()- 从队尾插入元素popFront()- 从队头删除元素popRear()- 从队尾删除元素getFront()- 获取队头元素getRear()- 获取队尾元素
与普通队列的区别：
- 双向操作：可以从两端进行插入和删除
- 更灵活：支持更多操作场景
- 实现稍复杂：需要处理两个方向的指针移动
复杂度分析：
- 所有操作的时间复杂度都是 O(1)
- 空间复杂度为 O(MAX_SIZE)
应用场景：
- 需要频繁在两端操作数据的场景
- 滑动窗口问题
- 回文检查
- 某些算法实现（如BFS的变种）
这个实现保持了代码的简洁性，同时提供了双向队列的所有基本功能。
初始状态
Deque dq;
initDeque(&dq); // front = -1, rear = 0, size = 0
队列状态: [空]
front = -1, rear = 0, size = 0
第一步：从队尾插入 10
pushRear(&dq, 10);
代码执行：
if (isEmpty(dq)) { // true
dq->front = 0; // front = 0
dq->rear = 0; // rear = 0
}
dq->data[dq->rear] = value; // data[0] = 10
dq->size++; // size = 1
队列状态: [10]
索引: 0 1 2 3 4 5 6 7 8 9
数据: 10 ? ? ? ? ? ? ? ? ?
↑
front=0, rear=0, size=1
第二步：从队尾插入 20
pushRear(&dq, 20);
代码执行：
if (isEmpty(dq)) { // false
dq->rear = (dq->rear + 1) % MAX_SIZE; // rear = (0+1)%10=1
}
dq->data[dq->rear] = value; // data[1] = 20
dq->size++; // size = 2
队列状态: [10, 20]
索引: 0 1 2 3 4 5 6 7 8 9
数据: 10 20 ? ? ? ? ? ? ? ?
↑ ↑
front=0 rear=1, size=2
第三步：从队尾插入 30
pushRear(&dq, 30);
dq->rear = (1 + 1) % 10 = 2
data[2] = 30
size = 3
队列状态: [10, 20, 30]
索引: 0 1 2 3 4 5 6 7 8 9
数据: 10 20 30 ? ? ? ? ? ? ?
↑ ↑
front=0 rear=2, size=3
第四步：从队头插入 5
pushFront(&dq, 5);
代码执行：
if (isEmpty(dq)) { // false
dq->front = (dq->front - 1 + MAX_SIZE) % MAX_SIZE;
// front = (0 - 1 + 10) % 10 = 9
}
dq->data[dq->front] = value; // data[9] = 5
dq->size++; // size = 4
队列状态: [5, 10, 20, 30]
索引: 0 1 2 3 4 5 6 7 8 9
数据: 10 20 30 ? ? ? ? ? ? 5
↑ ↑
rear=2 front=9, size=4
第五步：从队头插入 2
pushFront(&dq, 2);
front = (9 - 1 + 10) % 10 = 8
data[8] = 2
size = 5
队列状态: [2, 5, 10, 20, 30]
索引: 0 1 2 3 4 5 6 7 8 9
数据: 10 20 30 ? ? ? ? ? 2 5
↑ ↑
rear=2 front=8, size=5
第六步：从队头删除
popFront(&dq, &value); // value = 2
代码执行：
*value = dq->data[dq->front]; // value = data[8] = 2
dq->front = (dq->front + 1) % MAX_SIZE; // front = (8+1)%10=9
dq->size--; // size = 4
队列状态: [5, 10, 20, 30] (删除了2)
索引: 0 1 2 3 4 5 6 7 8 9
数据: 10 20 30 ? ? ? ? ? ? 5
↑ ↑
rear=2 front=9, size=4
第七步：从队尾删除
popRear(&dq, &value); // value = 30
代码执行：
*value = dq->data[dq->rear]; // value = data[2] = 30
dq->rear = (dq->rear - 1 + MAX_SIZE) % MAX_SIZE; // rear = (2-1+10)%10=1
dq->size--; // size = 3
队列状态: [5, 10, 20] (删除了30)
索引: 0 1 2 3 4 5 6 7 8 9
数据: 10 20 ? ? ? ? ? ? ? 5
↑ ↑ ↑
rear=1 front=9, size=3
关键特点：
- 循环特性：
front和rear指针会循环移动 - size计数器：通过
size来判断空/满，不需要浪费空间 - 双向操作：可以从两端插入和删除
- 初始值：
front = -1表示队列为空
这样的设计避免了普通循环队列需要浪费一个位置的问题，通过 size 计数器来准确判断队列状态。
时间复杂度分析
所有操作的时间复杂度：O(1)
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
pushFront() |
O(1) | 常数时间操作，只需计算索引和赋值 |
pushRear() |
O(1) | 常数时间操作，只需计算索引和赋值 |
popFront() |
O(1) | 常数时间操作，只需计算索引 |
popRear() |
O(1) | 常数时间操作，只需计算索引 |
getFront() |
O(1) | 直接访问数组元素 |
getRear() |
O(1) | 直接访问数组元素 |
isEmpty() |
O(1) | 简单比较操作 |
isFull() |
O(1) | 简单比较操作 |
原因分析：
- 数组随机访问：所有操作都基于数组索引的直接访问
- 数学运算简单：索引计算使用取模运算，是常数时间操作
- 无循环操作：所有方法中都没有循环结构
空间复杂度分析
空间复杂度：O(MAX_SIZE)
| 空间使用 | 复杂度 | 说明 |
|---|---|---|
| 数据数组 | O(MAX_SIZE) | 固定大小的数组，主要空间开销 |
| 结构体变量 | O(1) | front, rear, size三个整型变量 |
| 临时变量 | O(1) | 方法中的局部变量 |
| 总计 | O(MAX_SIZE) | 由固定大小的数组决定 |
评论区