数据结构–双端队列
双端队列(Double-ended Queue,简称Deque)是一种具有队列和栈特性的数据结构,可以在队列的两端进行插入和删除操作。双端队列允许从前端和后端同时进行插入和删除操作,因此可以称为“两端都可以进出的队列”。
双端队列的特点包括:
- 可以在队列的头部和尾部进行插入和删除操作。
- 元素的插入和删除操作可以分别称为入队和出队操作。
- 可以实现先进先出(FIFO)和后进先出(LIFO)两种操作方式。
- 可以用于实现栈、队列以及其他需要在两端进行插入和删除操作的场景。
双端队列的常见操作包括:文章来源:https://www.toymoban.com/news/detail-721776.html
- 在队列头部插入元素(头部入队):将元素插入到队列头部。
- 在队列尾部插入元素(尾部入队):将元素插入到队列尾部。
- 从队列头部删除元素(头部出队):删除队列头部的元素并返回。
- 从队列尾部删除元素(尾部出队):删除队列尾部的元素并返回。
- 获取队列头部的元素:返回队列头部的元素,但不删除。
- 获取队列尾部的元素:返回队列尾部的元素,但不删除。
- 判断队列是否为空:判断队列中是否有元素。
- 获取队列中的元素个数:返回队列中元素的个数。
双端队列的实现方式有多种,包括使用数组、链表等数据结构。具体的实现方式可以根据不同的需求和场景选择合适的方式。文章来源地址https://www.toymoban.com/news/detail-721776.html
常用操作代码实现
#include <stdio.h>
#include <stdlib.h>
// 定义双端队列节点结构体
typedef struct Node {
int data; // 数据域
struct Node* next; // 指针域,指向下一个节点
} Node;
// 定义双端队列结构体
typedef struct Deque {
Node* front; // 队头指针
Node* rear; // 队尾指针
} Deque;
// 初始化双端队列
Deque* initializeDeque() {
Deque* deque = (Deque*)malloc(sizeof(Deque));
deque->front = NULL;
deque->rear = NULL;
return deque;
}
// 判断双端队列是否为空
int isEmpty(Deque* deque) {
return (deque->front == NULL);
}
// 在队头插入元素
void insertFront(Deque* deque, int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
if (isEmpty(deque)) {
deque->front = newNode;
deque->rear = newNode;
} else {
newNode->next = deque->front;
deque->front = newNode;
}
}
// 在队尾插入元素
void insertRear(Deque* deque, int value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = value;
newNode->next = NULL;
if (isEmpty(deque)) {
deque->front = newNode;
deque->rear = newNode;
} else {
deque->rear->next = newNode;
deque->rear = newNode;
}
}
// 从队头删除元素
int deleteFront(Deque* deque) {
if (isEmpty(deque)) {
printf("Deque is empty.\n");
return -1;
}
int value = deque->front->data;
Node* temp = deque->front;
deque->front = deque->front->next;
if (deque->front == NULL) {
deque->rear = NULL;
}
free(temp);
return value;
}
// 从队尾删除元素
int deleteRear(Deque* deque) {
if (isEmpty(deque)) {
printf("Deque is empty.\n");
return -1;
}
int value = deque->rear->data;
Node* temp = deque->rear;
Node* current = deque->front;
while (current->next != deque->rear) {
current = current->next;
}
deque->rear = current;
deque->rear->next = NULL;
free(temp);
return value;
}
// 获取队头元素
int getFront(Deque* deque) {
if (isEmpty(deque)) {
printf("Deque is empty.\n");
return -1;
}
return deque->front->data;
}
// 获取队尾元素
int getRear(Deque* deque) {
if (isEmpty(deque)) {
printf("Deque is empty.\n");
return -1;
}
return deque->rear->data;
}
// 打印双端队列元素
void printDeque(Deque* deque) {
Node* current = deque->front;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
int main() {
Deque* deque = initializeDeque();
insertFront(deque, 1); // 队头插入元素1
insertFront(deque, 2); // 队头插入元素2
insertRear(deque, 3); // 队尾插入元素3
printDeque(deque); // 输出:2 1 3
deleteFront(deque); // 从队头删除元素
printDeque(deque); // 输出:1 3
deleteRear(deque); // 从队尾删除元素
printDeque(deque); // 输出:1
printf("Front element: %d\n", getFront(deque)); // 输出队头元素:1
printf("Rear element: %d\n", getRear(deque)); // 输出队尾元素:1
return 0;
}
知识点回顾与重要考点
到了这里,关于数据结构--双端队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!