在使用本博客提供的学习笔记及相关内容时，请注意以下免责声明：
信息准确性：本博客的内容是基于作者的个人理解和经验，尽力确保信息的准确性和时效性，但不保证所有信息都完全正确或最新。
非专业建议：博客中的内容仅供参考，不能替代专业人士的意见和建议。在做出任何重要决定之前，请咨询相关领域的专业人士。
个人责任：使用本博客内容的风险由用户自行承担。作者不对因使用本博客内容而导致的任何直接或间接损失承担责任。
版权声明：本博客中的所有内容均为作者原创，如需转载，请注明出处。同时，若有引用他人作品，也将尽力标明出处，如有侵权请及时联系作者。
链接免责：博客中可能包含外部链接，作者对这些链接所指向的内容不负责任，访问此类链接需谨慎。
感谢您的理解与支持！希望本博客能够为您的学习提供帮助。
双端队列（Deque）是一种允许在两端进行插入和删除操作的数据结构。它结合了队列和栈的特性，能够在队头和队尾进行操作。
### 双端队列的基本操作
1. **插入操作**：
- 在队头插入（push_front）
- 在队尾插入（push_back）
2. **删除操作**：
- 从队头删除（pop_front）
- 从队尾删除（pop_back）
3. **查看操作**：
- 查看队头元素（front）
- 查看队尾元素（back）
### 双端队列的实现
下面是双端队列的简单实现，使用链表和数组两种方式。
#### 1. 使用链表实现双端队列
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *prev;
struct Node *next;
} Node;
typedef struct {
Node *front;
Node *rear;
} Deque;
// 初始化双端队列
void initDeque(Deque *deque) {
deque->front = NULL;
deque->rear = NULL;
}
// 在队头插入
void push_front(Deque *deque, int value) {
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = value;
newNode->prev = NULL;
newNode->next = deque->front;
if (deque->front != NULL) {
deque->front->prev = newNode;
}
deque->front = newNode;
if (deque->rear == NULL) {
deque->rear = newNode; // 如果队列为空，rear也指向新节点
}
}
// 在队尾插入
void push_back(Deque *deque, int value) {
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
newNode->prev = deque->rear;
if (deque->rear != NULL) {
deque->rear->next = newNode;
}
deque->rear = newNode;
if (deque->front == NULL) {
deque->front = newNode; // 如果队列为空，front也指向新节点
}
}
// 从队头删除
int pop_front(Deque *deque) {
if (deque->front == NULL) {
printf("队列为空\n");
return -1;
}
Node *temp = deque->front;
int value = temp->data;
deque->front = temp->next;
if (deque->front != NULL) {
deque->front->prev = NULL;
} else {
deque->rear = NULL; // 如果队列为空，rear也设置为NULL
}
free(temp);
return value;
}
// 从队尾删除
int pop_back(Deque *deque) {
if (deque->rear == NULL) {
printf("队列为空\n");
return -1;
}
Node *temp = deque->rear;
int value = temp->data;
deque->rear = temp->prev;
if (deque->rear != NULL) {
deque->rear->next = NULL;
} else {
deque->front = NULL; // 如果队列为空，front也设置为NULL
}
free(temp);
return value;
}
// 打印双端队列
void printDeque(Deque *deque) {
Node *current = deque->front;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
// 释放双端队列
void freeDeque(Deque *deque) {
Node *current = deque->front;
while (current != NULL) {
Node *temp = current;
current = current->next;
free(temp);
}
}
int main() {
Deque deque;
initDeque(&deque);
push_back(&deque, 10);
push_back(&deque, 20);
push_front(&deque, 5);
printDeque(&deque);
printf("从队头删除: %d\n", pop_front(&deque));
printf("从队尾删除: %d\n", pop_back(&deque));
printDeque(&deque);
freeDeque(&deque);
return 0;
}
#### 2. 使用数组实现双端队列
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int front;
int rear;
} Deque;
// 初始化双端队列
void initDeque(Deque *deque) {
deque->front = -1;
deque->rear = -1;
}
// 判断队列是否为空
int isEmpty(Deque *deque) {
return deque->front == -1;
}
// 判断队列是否满
int isFull(Deque *deque) {
return (deque->rear + 1) % MAX_SIZE == deque->front;
}
// 在队头插入
void push_front(Deque *deque, int value) {
if (isFull(deque)) {
printf("队列已满\n");
return;
}
if (isEmpty(deque)) {
deque->front = 0;
deque->rear = 0;
} else {
deque->front = (deque->front - 1 + MAX_SIZE) % MAX_SIZE;
}
deque->data[deque->front] = value;
}
// 在队尾插入
void push_back(Deque *deque, int value) {
if (isFull(deque)) {
printf("队列已满\n");
return;
}
if (isEmpty(deque)) {
deque->front = 0;
deque->rear = 0;
} else {
deque->rear = (deque->rear + 1) % MAX_SIZE;
}
deque->data[deque->rear] = value;
}
// 从队头删除
int pop_front(Deque *deque) {
if (isEmpty(deque)) {
printf("队列为空\n");
return -1;
}
int value = deque->data[deque->front];
if (deque->front == deque->rear) {
deque->front = -1; // 队列变空
deque->rear = -1;
} else {
deque->front = (deque->front + 1) % MAX_SIZE;
}
return value;
}
// 从队尾删除
int pop_back(Deque *deque) {
if (isEmpty(deque)) {
printf("队列为空\n");
return -1;
}
int value = deque->data[deque->rear];
if (deque->front == deque->rear) {
deque->front = -1; // 队列变空
deque->rear = -1;
} else {
deque->rear = (deque->rear - 1 + MAX_SIZE) % MAX_SIZE;
}
return value;
}
// 打印双端队列
void printDeque(Deque *deque) {
if (isEmpty(deque)) {
printf("队列为空\n");
return;
}
int i = deque->front;
while (1) {
printf("%d ", deque->data[i]);
if (i == deque->rear) break;
i = (i + 1) % MAX_SIZE;
}
printf("\n");
}
int main() {
Deque deque;
initDeque(&deque);
push_back(&deque, 10);
push_back(&deque, 20);
push_front(&deque, 5);
printDeque(&deque);
printf("从队头删除: %d\n", pop_front(&deque));
printf("从队尾删除: %d\n", pop_back(&deque));
printDeque(&deque);
return 0;
}
### 总结
- **双端队列**：支持在两端进行插入和删除操作，适合需要灵活访问的场景。
- **实现方式**：可以使用链表或数组实现，选择时应考虑内存管理和操作效率。