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

探索数据结构：特殊的双向队列

news 文章来源：https://blog.csdn.net/Bettysweetyaaa/article/details/137480315 2024/10/26 8:33:22

✨✨ 欢迎大家来到贝蒂大讲堂✨✨

🎈🎈养成好习惯，先赞后看哦~🎈🎈

所属专栏：数据结构与算法
贝蒂的主页：Betty’s blog

1. 双向队列的定义

**双向队列(double‑ended queue)**是一种特殊的队列，它允许在队列的队尾与队头插入与删除元素。根据其定义，我们也可以理解为两个栈在栈底相连。

队尾入队

队首入队

队尾出队

队尾出队

2. 双向队列的分类

双向队列也是线性表的一种，所以也可以分别用链表与数组实现。基于链表实现：为了方便双向队列在尾部的插入与删除操作，所以我们选用双向链表。基于数组实现：与队列实现类似，需要用循环数组(原因参考队列实现)。

3. 双向队列的功能

队列的初始化。
判断队列是否为空。。
返回队头与队尾的元素。
返回队列的大小。
入队与出队。
打印队列的元素。
销毁队列。

4. 双向队列的声明

4.1. 链式队

双向队列与普通队列的声明区别就在于双向队列是基于双向链表的方式实现。

typedef int QDataType;
typedef struct DuListNode
{QDataType data;struct Node* prev;struct Node* next;
}DuListNode;typedef struct Deque
{size_t size;DuListNode* front;DuListNode* rear;
}Deque;

4.2. 循环队

循环队列的实现方式与普通队列差不多。

typedef int QDataType;
#define MAXSIZE 50  //定义元素的最大个数
typedef struct {QDataType *data;int front;  //头指针int rear;   //尾指针
}Deque;

5. 队列的初始化

5.1. 链式队

void DequeInit(Deque* d)//初始化
{assert(d);d->front = NULL;d->rear = NULL;d->size = 0;
}

5.2. 循环队

void DequeInit(Deque* d)//初始化
{d->data = (QDataType*)malloc(sizeof(QDataType )* MAXSIZE);if (d->data == NULL){perror("malloc fail:");return;}d->front = 0;d->rear = 0;
}

5.3. 复杂度分析

时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
空间复杂度：链式队空间是一个固定大小，空间复杂度为O(1)。而需要开辟整个队列的大小，空间复杂度为O(N)。

6. 判断队列是否为空

6.1. 链式队

bool DequeEmpty(Deque* d)//判断是否为空
{assert(d);return (d->front == NULL) && (d->rear == NULL);
}

6.2. 循环队

bool DequeEmpty(Deque* d)//判断是否为空
{assert(d);return d->front == d->rear;
}

6.3. 复杂度分析

时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)。

7. 判断队列是否为满

7.1. 链式队

链式队并不需要判断。

7.2. 循环队

为什么要取模操作，可以参考一下上一篇普通队列的实现，同下。

bool DequeFull(Deque* d)//判断队列是否满
{assert(d);return (d->rear + 1) % MAXSIZE == d->front;
}

8. 返回队头与队尾的元素

8.1. 链式队

QDataType DequeFront(Deque* d)//获取队头元素
{assert(d);assert(!DequeEmpty(d));return d->front->data;
}
QDataType DequeBack(Deque* d)//获取队尾元素
{assert(d);assert(!DequeEmpty(d));return d->rear->data;
}

8.2. 循环队

QDataType DequeFront(Deque* d)//获取队头元素
{assert(d);assert(!DequeEmpty(d));return d->data[d->front];
}
QDataType DequeBack(Deque* d)//获取队尾元素
{assert(d);assert(!DequeEmpty(d));return d->data[(d->rear-1+MAXSIZE)%MAXSIZE];
}

8.3. 复杂度分析

时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)

9. 返回队列的大小

9.1. 链式队

size_t DequeSize(Deque* d)//队列长度
{return d->size;
}

9.2. 循环队

size_t DequeSize(Deque* d)//获取队列长度
{assert(d);return (d->rear - d->front + MAXSIZE) % MAXSIZE;
}

9.3. 复杂度分析

时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)

10. 入队

10.1. 链式队

10.1.1. 队头入队

void DequeFrontPush(Deque* d, QDataType x)//队首入队
{assert(d);DuListNode* newnode = (DuListNode*)malloc(sizeof(DuListNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;if (d->front == NULL){d->front = d->rear = newnode;}else{d->front->prev = newnode;newnode->next = d->front;d->front = newnode;}d->size++;
}

10.1.2. 队尾入队

void DequeRearPush(Deque* d, QDataType x)//队尾入队
{assert(d);DuListNode* newnode = (DuListNode*)malloc(sizeof(DuListNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;if (d->front == NULL){d->front = d->rear = newnode;}else{d->rear->next = newnode;newnode->prev = d->rear;d->rear = newnode;}d->size++;
}

10.2. 循环队

入队需要提前判断队列是否为满。

10.2.1. 队头入队

void DequeFrontPush(Deque* d, QDataType x)//队首入队
{assert(d);if (DequeFull(d)){printf("队列已满\n");return;}d->data[(d->front - 1 + MAXSIZE) % MAXSIZE]=x;d->front = (d->front - 1 + MAXSIZE) % MAXSIZE;
}

10.2.2. 队尾入队

void DequeRearPush(Deque* d, QDataType x)//队尾入队
{assert(d);if (DequeFull(d)){printf("队列已满\n");return;}d->data[d->rear] = x;d->rear = (d->rear + 1) % MAXSIZE;
}

10.3. 复杂度分析

时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)

11. 出队

11.1. 链式队

出队需要提前判断队列是否为空。

11.1.1. 队头出队

void DequeFrontPop(Deque* d)//队首出队
{assert(d);assert(!DequeEmpty(d));//1.只有一个结点if (d->front == d->rear){free(d->front);d->front = d->rear = NULL;}//2.有多个结点else{DuListNode* next = d->front->next;next->prev = NULL;d->front->next = NULL;free(d->front);d->front = next;}d->size--;
}

11.1.2. 队尾出队

void DequeRearPop(Deque* d)//队尾出队
{assert(d);assert(!DequeEmpty(d));//1.只有一个结点if (d->front == d->rear){free(d->front);d->front = d->rear = NULL;}else{DuListNode* prev = d->rear->prev;prev->next = NULL;d->rear->prev = NULL;free(d->rear);d->rear = prev;}d->size--;
}

11.2. 循环队

11.2.1. 队头出队

void DequeFrontPop(Deque* d)//队首出队
{assert(d);assert(!DequeEmpty(d));d->front = (d->front + 1) % MAXSIZE;
}

11.2.2. 队尾出队

void DequeRearPop(Deque* d)//队尾出队
{assert(d);assert(!DequeEmpty(d));d->rear = (d->rear - 1+MAXSIZE) % MAXSIZE;
}

11.3. 复杂度分析

时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)

12. 打印队列元素

12.1. 链式队

void DequePrint(Deque* d)//打印队列元素
{assert(d);DuListNode* cur = d->front;DuListNode* tail = d->rear;printf("队头:");while (cur != tail->next){printf("%d<=>", cur->data);cur = cur->next;}printf("队尾\n");
}

12.2. 循环队

void DequePrint(Deque* d)//打印队列元素
{assert(d);int cur = d->front;printf("队头->");while (cur != d->rear){printf("%d->", d->data[cur]);cur = (cur + 1) % MAXSIZE;}printf("队尾\n");}

12.3. 复杂度分析

时间复杂度：无论是链式队还是循环队列都需要遍历这个队列，所以时间复杂度为O(N)。
空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)

13. 销毁队列

13.1. 链式队

void DequeDestroy(Deque* d)//销毁队列
{assert(d);DuListNode* cur = d->front;while (cur){DuListNode* del = cur;cur = cur->next;free(del);del = NULL;}d->front = d->rear = NULL;
}

13.2. 循环队

void DequeDestroy(Deque* d)//销毁队列
{assert(d);free(d->data);d->data = NULL;d->front = d->rear = 0;
}

13.3. 复杂度分析

时间复杂度：无论是链式队还是循环队列花费时间都是一个常数，所以时间复杂度为O(1)。
空间复杂度：无论是链式队还是循环队列花费空间都是一个固定大小，所以空间复杂度为O(1)

14. 对比与应用

14.1. 对比

双向队列的两种实现方式的效果与普通队列实现差不多，这里就不在一一赘述。

14.2. 应用

双向队列兼备队列与栈的性质，所以可以应用于这两种数据结构的所有应用场景。

此外它应用于撤销的一种情景：通常情况下，撤销是以栈的方式实现，当我们每次更改时就入栈，撤销就出栈。但是我们知道系统给与栈的空间是有限的，我们不可能一直入栈。当入栈超过一个限度时，我们就用过删除栈底的数据，这时栈这个数据结构就无法满足需求。所以这时我们可以使用双向队列来实现。

15. 完整代码

15.1. 链式队

15.1.1. Deque.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
typedef struct DuListNode
{QDataType data;struct Node* prev;struct Node* next;
}DuListNode;typedef struct Deque
{size_t size;DuListNode* front;DuListNode* rear;
}Deque;
void DequeInit(Deque* d);//初始化
bool DequeEmpty(Deque* d);//判断是否为空
QDataType DequeFront(Deque* d);//获取队头元素
QDataType DequeBack(Deque* d);//获取队尾元素
size_t DequeSize(Deque* d);//获取队列长度
void DequeFrontPush(Deque* d, QDataType x);//队首入队
void DequeRearPush(Deque* d, QDataType x);//队尾入队
void DequeFrontPop(Deque* d);//队首出队
void DequeRearPop(Deque* d);//队尾出队
void DequePrint(Deque* d);//打印队列元素
void DequeDestroy(Deque* d);//销毁队列

15.1.2. Deque.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Deque.h"
void DequeInit(Deque* d)//初始化
{assert(d);d->front = NULL;d->rear = NULL;d->size = 0;
}
bool DequeEmpty(Deque* d)//判断是否为空
{assert(d);return (d->front == NULL) && (d->rear == NULL);
}
QDataType DequeFront(Deque* d)//获取队头元素
{assert(d);assert(!DequeEmpty(d));return d->front->data;
}
QDataType DequeBack(Deque* d)//获取队尾元素
{assert(d);assert(!DequeEmpty(d));return d->rear->data;
}
size_t DequeSize(Deque* d)//队列长度
{return d->size;
}
void DequeFrontPush(Deque* d, QDataType x)//队首入队
{assert(d);DuListNode* newnode = (DuListNode*)malloc(sizeof(DuListNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;if (d->front == NULL){d->front = d->rear = newnode;}else{d->front->prev = newnode;newnode->next = d->front;d->front = newnode;}d->size++;
}
void DequeRearPush(Deque* d, QDataType x)//队尾入队
{assert(d);DuListNode* newnode = (DuListNode*)malloc(sizeof(DuListNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;if (d->front == NULL){d->front = d->rear = newnode;}else{d->rear->next = newnode;newnode->prev = d->rear;d->rear = newnode;}d->size++;
}
void DequeFrontPop(Deque* d)//队首出队
{assert(d);assert(!DequeEmpty(d));//1.只有一个结点if (d->front == d->rear){free(d->front);d->front = d->rear = NULL;}//2.有多个结点else{DuListNode* next = d->front->next;next->prev = NULL;d->front->next = NULL;free(d->front);d->front = next;}d->size--;
}
void DequeRearPop(Deque* d)//队尾出队
{assert(d);assert(!DequeEmpty(d));//1.只有一个结点if (d->front == d->rear){free(d->front);d->front = d->rear = NULL;}else{DuListNode* prev = d->rear->prev;prev->next = NULL;d->rear->prev = NULL;free(d->rear);d->rear = prev;}d->size--;
}
void DequePrint(Deque* d)//打印队列元素
{assert(d);DuListNode* cur = d->front;DuListNode* tail = d->rear;printf("队头:");while (cur != tail->next){printf("%d<=>", cur->data);cur = cur->next;}printf("队尾\n");
}
void DequeDestroy(Deque* d)//销毁队列
{assert(d);DuListNode* cur = d->front;while (cur){DuListNode* del = cur;cur = cur->next;free(del);del = NULL;}d->front = d->rear = NULL;
}

15.2. 循环队

15.2.1. Deque.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
#define MAXSIZE 50  //定义元素的最大个数
typedef struct {QDataType *data;int front;  //头指针int rear;   //尾指针
}Deque;void DequeInit(Deque* d);//初始化
bool DequeEmpty(Deque* d);//判断是否为空
bool DequeFull(Deque* d);//判断队列是否满
QDataType DequeFront(Deque* d);//获取队头元素
QDataType DequeBack(Deque* d);//获取队尾元素
size_t DequeSize(Deque* d);//获取队列长度
void DequeFrontPush(Deque* d, QDataType x);//队首入队
void DequeRearPush(Deque* d, QDataType x);//队尾入队
void DequeFrontPop(Deque* d);//队首出队
void DequeRearPop(Deque* d);//队尾出队
void DequePrint(Deque* d);//打印队列元素
void DequeDestroy(Deque* d);//销毁队列

15.2.2. Deque.c

void DequeInit(Deque* d)//初始化
{d->data = (QDataType*)malloc(sizeof(QDataType )* MAXSIZE);if (d->data == NULL){perror("malloc fail:");return;}d->front = 0;d->rear = 0;
}
bool DequeEmpty(Deque* d)//判断是否为空
{assert(d);return d->front == d->rear;
}
bool DequeFull(Deque* d)//判断队列是否满
{assert(d);return (d->rear + 1) % MAXSIZE == d->front;
}
QDataType DequeFront(Deque* d)//获取队头元素
{assert(d);assert(!DequeEmpty(d));return d->data[d->front];
}
QDataType DequeBack(Deque* d)//获取队尾元素
{assert(d);assert(!DequeEmpty(d));return d->data[(d->rear-1+MAXSIZE)%MAXSIZE];
}
size_t DequeSize(Deque* d)//获取队列长度
{assert(d);return (d->rear - d->front + MAXSIZE) % MAXSIZE;
}
void DequeFrontPush(Deque* d, QDataType x)//队首入队
{assert(d);if (DequeFull(d)){printf("队列已满\n");return;}d->data[(d->front - 1 + MAXSIZE) % MAXSIZE]=x;d->front = (d->front - 1 + MAXSIZE) % MAXSIZE;
}
void DequeRearPush(Deque* d, QDataType x)//队尾入队
{assert(d);if (DequeFull(d)){printf("队列已满\n");return;}d->data[d->rear] = x;d->rear = (d->rear + 1) % MAXSIZE;
}
void DequeFrontPop(Deque* d)//队首出队
{assert(d);assert(!DequeEmpty(d));d->front = (d->front + 1) % MAXSIZE;
}
void DequeRearPop(Deque* d)//队尾出队
{assert(d);assert(!DequeEmpty(d));d->rear = (d->rear - 1+MAXSIZE) % MAXSIZE;
}
void DequePrint(Deque* d)//打印队列元素
{assert(d);int cur = d->front;printf("队头->");while (cur != d->rear){printf("%d->", d->data[cur]);cur = (cur + 1) % MAXSIZE;}printf("队尾\n");}
void DequeDestroy(Deque* d)//销毁队列
{assert(d);free(d->data);d->data = NULL;d->front = d->rear = 0;
}

探索数据结构：特殊的双向队列

✨✨ 欢迎大家来到贝蒂大讲堂✨✨ 🎈🎈养成好习惯，先赞后看哦~🎈🎈 所属专栏：数据结构与算法贝蒂的主页：Betty’s blog 1. 双向队列的定义 **双向队列(double‑ended queue)**是一种特殊的队列…...

编程日记 2024/4/8 3:53:01

I2C库函数 1.void I2C_DeInit(I2C_TypeDef* I2Cx);2.void I2C_Init(I2C_TypeDef* I2Cx, I2C_InitTypeDef* I2C_InitStruct);3.void I2C_StructInit(I2C_InitTypeDef* I2C_InitStruct);4.void I2C_Cmd(I2C_TypeDef* I2Cx, FunctionalState NewState);5.void I2C_DMACmd(I2C_Type…...

编程日记 2024/4/8 3:52:00

十八、Rust gRPC 多 proto 演示

十八、Rust gRPC 多 proto 演示网上及各官方资料，基本是一个 proto 文件，而实际项目，大多是有层级结构的多 proto 文件形式，本篇文章基于此诉求，构建一个使用多 proto 文件的 rust grpc 使用示例。关于 grpc 的实现…...

编程日记 2024/4/8 3:49:57

【Linux】Linux64位环境下编译32位报错skipping incompatible的解决办法

本文首发于 ❄️慕雪的寒舍问题如题，当我尝试在wsl2的ubuntu中使用-m32选项编译32位程序的时候，出现了下面的两种报错 ❯ g -m32 test.cpp -o test1 && ./test1 In file included from test.cpp:1: /usr/include/stdio.h:27:10: fatal error…...

编程日记 2024/4/8 3:47:54

vue指令v-model

<!DOCTYPE html> <html lang"en"> <head> <meta charset"UTF-8"> <meta name"viewport" content"widthdevice-width, initial-scale1.0"> <title>vue指令v-model</title> </head>…...

编程日记 2024/4/8 3:45:51

CentOS安装MySQL数据库

一、更新yum源 #下载对应repo文件 wget -O CentOS-Base.repo http://mirrors.aliyun.com/repo/Centos-8.repo #清除缓存 yum clean all #生成新缓存 yum makecache #更新 yum update -y 二、安装MySQL #获取源 wget http://repo.mysql.com/mysql80-community-release-el7-3.…...

编程日记 2024/4/8 3:43:48

从B2B转向B2B2C模式：工业品牌史丹利百得的转型历程

图片来源：Twitter 在当今数据驱动的营销环境中，企业努力更好了解客户，并在整个客户旅程中提供个性化体验。史丹利百得（Stanley Black & Decker）是一家领先的工具和工业设备供应商，近年来开始重大转型。…...

编程日记 2024/4/8 3:42:47

Redis群集模式和rsync远程同步

一、Redis群集模式 1.1 概念 1.2 作用 1.2.1 Redis集群的数据分片 1.2.2 Redis集群的主从复制模型 1.3 搭建Redis 群集模式 1.3.1 开启群集功能 1.3.2 启动redis节点 1.3.3 启动集群 1.3.4 测试群集二、rsync远程同步 2.1 概念 2.2 同步方式 2.3 备份的方式 2.4…...

编程日记 2024/4/8 3:41:46

JAVA—抽象—定义抽象类Converter及其子类WeightConverter

同样，我们由这道题引出抽象类，抽象方法这个概念。按下面要求定义类Converter及其子类WeightConverter 定义抽象类：Converter： 定义一个抽象类Converter，表示换算器，其定义的如下： 一个私有…...

编程日记 2024/4/8 3:40:45

面对复杂多变的网络攻击，企业应如何守护网络安全

企业上云，即越来越多的企业把业务和数据，迁移到云端。随着云计算、大数据、物联网、人工智能等技术的发展，用户、应用程序和数据无处不在，企业之间的业务边界逐渐被打破，网络攻击愈演愈烈，手段更为多。当前…...

编程日记 2024/4/8 3:39:43

计算机网络练习-计算机网络概述与性能指标

计算机网络概述 ----------------------------------------------------------------------------------------------------------------------------- 1. 计算机网络最据本的功能的是( )。 1,差错控制 Ⅱ.路由选择 Ⅲ,分布式处理 IV.传输控制 …...

编程日记 2024/4/8 3:38:42

vite vue3 ts import.meta在vscode中报错

问题描述：开发使用的框架为vitevue3ts，在开发过程中莫名其妙报仅当“--module”选项为“es2020”、“esnext”或“系统”时才允许使用“import.meta”元属性问题解决： 通过更改tsconfig.json的module为esnext，es2022等&#xff0…...

编程日记 2024/4/8 3:37:41

Java synchronized（详细）

synchronized 一，介绍在Java中，synchronized关键字用于解决多线程并发访问共享资源时可能出现的线程安全问题。当多个线程同时访问共享资源时，如果没有合适的同步机制，可能会导致以下问题： 竞态条件&#xff08…...

编程日记 2024/4/8 3:34:37

算法设计与分析实验报告python实现(排序算法、三壶谜题、交替放置的碟子、带锁的门)

一、实验目的 1．加深学生对算法设计方法的基本思想、基本步骤、基本方法的理解与掌握； 2．提高学生利用课堂所学知识解决实际问题的能力； 3．提高学生综合应用所学知识解决实际问题的能力。二、实验任务 1、排序算法…...

编程日记 2024/4/8 3:33:35

实训问题总结——ajax用get可以成功调用controller方法，用POST就出404错误

因为传输密码时必须用POST。还有用GET传输参数，说有非法字符，想试试POST是否可以解决。 404错误的三个大致原因，1：找不到对的请求路径，2：请求方式错误，3、请求参数错误。后来可以调用了。但…...

编程日记 2024/4/8 3:32:34

1、认识MySQL存储引擎吗？

目录 1、MySQL存储引擎有哪些？ 2、默认的存储引擎是哪个？ 3、InnoDB和MyISAM有什么区别吗？ 3.1、关于事务 3.2、关于行级锁 3.3、关于外键支持 3.4、关于是否支持MVCC 3.5、关于数据安全恢复 3.6、关于索引 3.7、关于性能 4、如何…...

编程日记 2024/4/8 3:26:28

微信小程序媒体查询

在微信小程序中，media媒体查询不支持screen关键字，因为小程序页面是再webview中渲染的，而不是在浏览器中渲染的。在设置样式时，可以使用 wxss 文件中的 media 规则来根据屏幕宽度或高度设置不同的样式。 device-width:设备屏幕…...

编程日记 2024/4/8 3:24:26

前端（动态雪景背景+动态蝴蝶）

1.CSS样式 <style>html, body, a, div, span, table, tr, td, strong, ul, ol, li, h1, h2, h3, p, input {font-weight: inherit;font-size: inherit;list-style: none;border-spacing: 0;border: 0;border-collapse: collapse;text-decoration: none;padding: 0;margi…...

编程日记 2024/4/8 3:22:24