【数据结构】栈和队列（链表模拟队列）

devtools/2024/9/19 18:52:37/ 标签: 数据结构, 链表, 队列, 单链表

 

学习本章节必须具备 单链表的前置知识，

建议提前学习：点击链接学习：单链表各种功能函数 细节 详解

本章节是学习用 单链表模拟队列

1. 单链表实现队列 思路如下

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先 进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一 端称为队头

1.1 使用 数组 还是 链表 模拟 队列 结构？

因为需要 模拟队列 先进先出的 特性：队头 只能出，队尾 只能进

若 使用 数组模拟，每次 pop 队头操作，就需要 全部元素向前面移动，时间复杂度为 O(n)

综上，因为需要 考虑位置变化，选择 链表 实现 队列 较优

1.2. 需要使用 什么类型的 链表模拟队列？

单向

带头 / 不带头 都可以 ：因为哨兵位主要用于 双向链表 找尾 ，为了方便删除，这里差别不大

不循环

我们下面实现的 是 单向不带头不循环链表

实际上，单向或双向，循环或不循环，带头或不带头 完全取决于 你自己要实现一个功能的需求，不是说 一定要固定使用 哪一个套 ，需要灵活选择使用

1.3. 单向链表 实现队列 的链表节点结构体创建：

typedef int QDataType;
typedef struct QueueNode
{QDataType value;            // 节点数据struct QueueNode* next;     // 指向下一个节点
}QNode;
1.4. 考虑效率，创建 头尾指针结构体

因为 队列需要：队头 push，队尾 pop

涉及到对 链表 的 尾部操作必须意识到：需要先进行 找尾操作，时间复杂度为 O(n)

方案：因为涉及头尾频繁操作：可以 直接 同时定义 头指针 phead 和 尾指针 ptail

技巧：同类型的变量可以封装成一个结构体

因为 phead 和 ptail 是可以不断变化的，每个相关函数都需要同时传递 phead 和 ptail 两个变量

则可以将多个同类型的变量 封装成 一个结构体，方便操作

这样，传递变量时 直接传递一个 结构体的指针就行了

typedef struct Queue
{QNode* phead;QNode* ptail;
}Queue;
// 区别：减少了传递变量的数量，利于协助开发
// void QueuePush(QNode* phead, QNode* ptail);
void QueuePush(Queue* pq);
// void QueuePop(QNode* phead, QNode* ptail);
void QueuePop(Queue* pq);

1.5. Push / Pop ：入队 和 出队操作

Push 在队尾入队，Pop 在队头出队

void QueuePop(Queue* pq)
{assert(pq);// pop 的删除操作 需要分类讨论：链表节点个数为 0、为 1、为 两个以上// 为 0 ：直接判空，退出操作：phead == ptail == NULLassert(pq->phead);    // 头节点为空 就一定代表为空了// 为 1：phead == ptail  但是 phead != NULL 的情况：即一定指向一个节点if (pq->phead == pq->ptail && pq->phead != NULL) {free(pq->phead);pq->phead = pq->ptail = NULL;}else // 为 两个以上：先记录第二个节点，free 掉头节点，更新头节点{QNode* tmp = pq->phead->next;free(pq->phead);pq->phead = tmp;}
}

为什么 ” 头节点为空 或 尾节点为空 就一定代表链表为空了 “？

1.6. 观察上面代码：有需要 判断链表节点数量的 需求，为了简化代码与优化过程，可以 直接定义一个 size ，放进结构体中，时刻记录 链表节点数量

// 结构体更改：
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;// 加入 size 后 的 Push 和 Pop 函数
void QueuePop(Queue* pq)
{assert(pq);assert(pq->phead);if (pq->size == 1) {free(pq->phead);pq->phead = pq->ptail = NULL;}else if (pq->size >= 2){QNode* next = pq->phead->next;  // 保留下一个free(pq->phead);pq->phead = next;}pq->size--;    // 注意 pop 代表弹出一个节点，数量 - 1
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);// push 前先创建一个新节点QNode* newNode = (QNode*)malloc(sizeof(QNode));if (newNode == NULL) {perror("malloc fail");return;}newNode->value = x;newNode->next = NULL;if (pq->ptail) // 若 ptail != NULL 说明此时链表不为空{pq->ptail->next = newNode; // 旧的尾节点和一个新的点 进行链接pq->ptail = newNode; // 重新更新尾节点}else  // 若链表为空，则 phead 和 ptail 都要 处理{pq->phead = pq->ptail = newNode;}pq->size++;   // 数量++
}

2. 综上所述，最终代码：

Queue.c

#include"Queue.h"// Push 入队，Pop 出队
void QueuePop(Queue* pq)
{assert(pq);assert(pq->phead);if (pq->size == 1) {free(pq->phead);pq->phead = pq->ptail = NULL;}else if (pq->size >= 2){QNode* next = pq->phead->next;  // 保留下一个free(pq->phead);pq->phead = next;}pq->size--;    // 注意 pop 代表弹出一个节点，数量 - 1
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);// push 前先创建一个新节点QNode* newNode = (QNode*)malloc(sizeof(QNode));if (newNode == NULL) {perror("malloc fail");return;}newNode->value = x;newNode->next = NULL;if (pq->ptail) // 若 ptail != NULL 说明此时链表不为空{pq->ptail->next = newNode; // 旧的尾节点和一个新的点 进行链接pq->ptail = newNode; // 重新更新尾节点}else  // 若链表为空，则 phead 和 ptail 都要 处理{pq->phead = pq->ptail = newNode;}pq->size++;   // 数量++
}// 初始化
void  QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}// 销毁链表：就是 单链表的 销毁操作
void QueueDestory(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur) {QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;  // 最后别忘了头尾指针置为 NULLpq->size = 0;
}// Front 返回队头元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead); // 若链表为空 自然没有头节点;return pq->phead->value;
}// Back 返回队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail); // 若链表为空 自然没有尾节点;return pq->ptail->value;
}// Empty 判断是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}// Size 返回节点数量
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef int QDataType;
typedef struct QueueNode
{QDataType value;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;// 初始化
void  QueueInit(Queue* pq);   // Push 入队，Pop 出队
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);// Front 队头元素，Back 队尾元素
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);// Empty 判断是否为空，Size 返回节点数量
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);// 销毁链表
void QueueDestory(Queue* pq);

Main.c

#include"Queue.h"int main()
{Queue q;   // 创建队列结构体QueueInit(&q); // 初始化：用于初始化链表的头尾节点：phead  /  ptailfor (int i = 1; i <= 5; ++i) {  // 入队列 几个元素： 1 2 3 4 5QueuePush(&q, i); }// 一个个读取队列元素while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}QueueDestory(&q);return 0;
}

3. LeetCode：225.队列实现栈

使用两个队列实现栈

核心思路：

保持一个队列存数据，一个队列为空
push 入数据，入到不为空的队列
pop 出数据，将 非空队列中 前 n-1 个数据 导入 空队列

代码实现

// 以下均是 链式队列的 相关函数，复制粘贴过来罢了
///
typedef int QDataType;
typedef struct QueueNode
{QDataType value;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;void QueuePop(Queue* pq)
{assert(pq);assert(pq->phead);if (pq->size == 1) {free(pq->phead);pq->phead = pq->ptail = NULL;}else if (pq->size >= 2){QNode* next = pq->phead->next;  // 保留下一个free(pq->phead);pq->phead = next;}pq->size--;    // 注意 pop 代表弹出一个节点，数量 - 1
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);// push 前先创建一个新节点QNode* newNode = (QNode*)malloc(sizeof(QNode));if (newNode == NULL) {perror("malloc fail");return;}newNode->value = x;newNode->next = NULL;if (pq->ptail) // 若 ptail != NULL 说明此时链表不为空{pq->ptail->next = newNode; // 旧的尾节点和一个新的点 进行链接pq->ptail = newNode; // 重新更新尾节点}else  // 若链表为空，则 phead 和 ptail 都要 处理{pq->phead = pq->ptail = newNode;}pq->size++;   // 数量++
}// 初始化
void  QueueInit(Queue* pq)
{assert(pq);pq->phead = pq->ptail = NULL;pq->size = 0;
}// 销毁链表：就是 单链表的 销毁操作
void QueueDestory(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur) {QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;  // 最后别忘了头尾指针置为 NULLpq->size = 0;
}// Front 返回队头元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead); // 若链表为空 自然没有头节点;return pq->phead->value;
}// Back 返回队尾元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail); // 若链表为空 自然没有尾节点;return pq->ptail->value;
}// Empty 判断是否为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}// Size 返回节点数量
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
// 以上均是 链式队列的 相关函数，复制粘贴过来罢了
//////
// 下面是题目主体
typedef struct {Queue q1, q2; // 创建两个队列
} MyStack;MyStack* myStackCreate() {MyStack* pst = (MyStack*)malloc(sizeof(MyStack)); // 创建一个栈QueueInit(&(pst->q1));QueueInit(&(pst->q2));return pst;
}void myStackPush(MyStack* obj, int x) {// push 到 不为空的 队列if(QueueEmpty(&(obj->q1))) {QueuePush(&(obj->q2), x);}else {QueuePush(&(obj->q1), x);}
}int myStackPop(MyStack* obj) {// 找到非空的 队列，将 size-1 个元素放进 另一个空队列，同时最后一个元素pop掉// 有两种情况：q1 为空，q2 不为空, q2 为空，q1 不为空// 可以先假设，后调整// 先假设 队列1 为空，队列2 不为空，后面判断后调整Queue* pEmptyQ = &(obj->q1);Queue* pNonEmptyQ = &(obj->q2);if(!QueueEmpty(&(obj->q1))){pEmptyQ = &(obj->q2);pNonEmptyQ = &(obj->q1);}// 将不为空队列 的前 n-1 个元素放进 空队列中while(QueueSize(pNonEmptyQ) > 1) {int x = QueueFront(pNonEmptyQ);QueuePush(pEmptyQ, x);QueuePop(pNonEmptyQ);}int t = QueueFront(pNonEmptyQ);QueuePop(pNonEmptyQ);return t;
}int myStackTop(MyStack* obj) {if(QueueEmpty(&(obj->q1))) {return QueueBack(&(obj->q2));}else {return QueueBack(&(obj->q1));}
}bool myStackEmpty(MyStack* obj) {return QueueEmpty(&(obj->q1)) && QueueEmpty(&(obj->q2)); // 两个都为空才是栈空
}void myStackFree(MyStack* obj) {if(QueueEmpty(&(obj->q1))) {QueueDestory(&(obj->q2));}else if(QueueEmpty(&(obj->q2))) {QueueDestory(&(obj->q1));}
}

4. LeetCode：223.栈实现队列

使用 两个栈 模拟队列

思路

定义一个 pushStack ：专门用来接收 push入队列的 数据
定义一个 popStack ：专门用来 pop 队列数据
当 popStack 为空时，此时需要 pop 操作，则将 pushStack 的数据全部 放进 popStack ，补充数据（注意是全部）；若popStack 不为空，则进行 pop 操作即可
当 需要 push 操作，直接往 pushStack 中放数据即可

演示： push 2 次，pop 1 次，push 3 次， pop 3 次

【若文章有什么错误，欢迎评论区讨论或私信指出】 


http://www.ppmy.cn/devtools/8393.html

相关文章

Spring-boot框架——2.属性自动注入

Spring-boot框架——2.属性自动注入

在spring中注入jdbc配置项是通过PropertySource和Value以及Bean结合jdbc.properties配置文件完成数据库的注入。 1.在springboot中&#xff1a;首先在默认配置文件Application.properties中添加jdbc配置&#xff1a; jdbc.driverClassNamecom.mysql.jsbc.Driver jdbc.url****…
阅读更多...
C语言趣味代码（二）

C语言趣味代码（二）

1.珠玑妙算 1.1 介绍 《珠玑妙算》(Mastermind)是英国Invicta公司于1973年开始销售的一款益智游戏&#xff0c;据说迄今为止已经在全世界销售了5000万套。《珠玑妙算》于1974年获奖后&#xff0c;在1975年传入美国&#xff0c;1976年leslieH.Autl博士甚至还出版了一本名为The…
阅读更多...
从迷宫问题理解dfs

从迷宫问题理解dfs

文章目录 迷宫问题打印路径1思路定义一个结构体要保存所走的路径&#xff0c;就需要使用到栈遍历所有的可能性核心代码 部分函数递归图源代码 迷宫问题返回最短路径这里的思想同上面类似。源代码 迷宫问题打印路径1 定义一个二维数组 N*M &#xff0c;如 5 5 数组下所示&…
阅读更多...
微服务架构与Dubbo

微服务架构与Dubbo

一、微服务架构 微服务架构是一种架构概念&#xff0c;旨在通过将功能分解到各个离散的服务中以实现对解决方案的解耦。 分布式系统式若干独立系统的集合&#xff0c;但是用户使用起来好像是在使用一套系统。 和微服务对应的是单体式开发&#xff0c;即所有的功能打包在一个WAR…
阅读更多...
【离散数学】特殊关系

【离散数学】特殊关系

一、等价关系 等价关系和等价类 等价关系定义&#xff1a;R是非空集合A上的关系&#xff0c;如果R是自反的、对称的、传递的&#xff0c;则R为A上的等价关系 等价类定义&#xff1a;R是非空集合A上的等价关系&#xff0c;对于任意x∈A&#xff0c;称集合[x]R{y|y∈A,<x,y…
阅读更多...
docker网路和主机通讯问题

docker网路和主机通讯问题

#注 1&#xff0c;安装docker和启动容器服务的时候如果防火墙处于开启状态&#xff0c;那么重启docker里面的容器的时候必须开启防火墙&#xff0c;否则会出现iptable错误&#xff1b; 2&#xff0c;linux开启防火墙会导致主机和docker网络之间单向通讯&#xff0c;主机可以访…
阅读更多...
设计模式-构建者模式

设计模式-构建者模式

作者持续关注 WPS二次开发专题系列&#xff0c;持续为大家带来更多有价值的WPS二次开发技术细节&#xff0c;如果能够帮助到您&#xff0c;请帮忙来个一键三连&#xff0c;更多问题请联系我&#xff08;QQ:250325397&#xff09; 目录 定义 特点 使用场景 优缺点 (1) 优点 …
阅读更多...
每天五分钟计算机视觉：基于卷积操作完成滑动窗口的图片分类？

每天五分钟计算机视觉：基于卷积操作完成滑动窗口的图片分类？

本文重点 我们前面学习了使用不同大小的滑动窗口来滑动图片，然后切分成许多小的图片，然后依次应用到我们已经训练好的图像分类模型中，但是这种方式效率太低了，本节课程我们学习一种新的方式，来看一下如何并行识别这些剪切的图片。 原始结构 首先我们先来看一下，如何把…
阅读更多...
Redis系列5：深入分析Cluster 集群模式

Redis系列5：深入分析Cluster 集群模式

1 背景 前面我们学习了Redis高可用的两种架构模式&#xff1a;主从模式、哨兵模式。 解决了我们在Redis实例发生故障时&#xff0c;具备主从自动切换、故障转移的能力&#xff0c;终保证服务的高可用。 但是这些其实远远不够&#xff0c;随着我们业务规模的不断扩展&#xff0…
阅读更多...
Java学习笔记29（泛型）

Java学习笔记29（泛型）

1.泛型 ArrayList<Dog> arrayList new ArrayList<Dog>(); //1.当我们ArrayList<Dog>表示存放到ArrayList集合中的元素是Dog类 //2.如果编译器发现添加的类型&#xff0c;不满足要求&#xff0c;就会报错 //3.在便利的时候&#xff0c;可以直接取出Dog类型而…
阅读更多...
restful请求风格的增删改查-----查询and添加

restful请求风格的增删改查-----查询and添加

一、restful风格的介绍 restful也称之为REST ( Representational State Transfer )&#xff0c;可以将它理解为一种软件架构风格或设计风格&#xff0c;而不是一个标准。简单来说&#xff0c;restful风格就是把请求参数变成请求路径的一种风格。例如&#xff0c;传统的URL请求…
阅读更多...
C语言数据结构之链表

C语言数据结构之链表

目录 前言 \color{maroon}{前言} 前言1.链表的概念及结构2.链表的分类3.无头单向非循环链表的实现4.带头双向循环链表的实现5.顺序表和链表的对比 前言 \color{maroon}{前言} 前言 在上一篇博客中我们提到&#xff0c;线性表包括顺序表和链表&#xff0c;顺序表在上篇博客中已…
阅读更多...
yolov8下实现绿萝识别

yolov8下实现绿萝识别

目录 一：背景 二：过程 一：背景 上一节我们学习了yolov8自带模型的使用，这一节我们讲解下yolov8的数据训练，生成模型来识别绿萝。 二：过程 1：数据准备，我们可以自己收集绿萝的图片，最起码需要准备几百张的图片。我们这里通过网络下载图片保存到一个目录等待处理。 …
阅读更多...
RIP最短路实验（华为）

RIP最短路实验（华为）

思科设备参考&#xff1a;RIP最短路实验&#xff08;思科&#xff09; 一&#xff0c;技术简介 RIP&#xff08;Routing Information Protocol&#xff0c;路由信息协议&#xff09;是一种基于距离矢量的内部网关协议&#xff0c;工作原理是每个路由器周期性地向邻居路由器发…
阅读更多...
Rust---泛型（Generics）

Rust---泛型（Generics）

目录 泛型和多态泛型参数泛型的使用结构体中使用枚举中使用方法中使用函数中使用为特定的类型参数提供特定的方法实现泛型和多态 泛型允许在编写代码时使用抽象类型来代替具体类型，可以在不同的数据类型上工作，同时避免代码重复。通过泛型，我们可以编写一次代码，然后在需要…
阅读更多...
RAID技术

RAID技术

RIAD 什么是RAID 磁盘阵列:利用虚拟化存储技术把多个硬盘组合起来&#xff0c;成为一个或多个硬盘阵列组&#xff0c;目的为提升性能或数据冗余&#xff0c;或是两者同时提升。 简单来说RAID是把多个硬盘组合成为一个逻辑硬盘&#xff0c;因此&#xff0c;操作系统只会把它当作…
阅读更多...
vue循环发起请求，等一个请求结束后，进行下一次请求

vue循环发起请求，等一个请求结束后，进行下一次请求

vue循环发起请求&#xff0c;等一个请求结束后&#xff0c;进行下一次请求 async await new Promise async filesSubmitted(files, fileList) {if (files.length 0) {return this.$message.error("文件列表存在同名文件&#xff0c;请关闭文件列表后再试。");}for (…
阅读更多...
JavaWeb--JS正则表达式

JavaWeb--JS正则表达式

目录 1. 简介 1.1. 语法 1.1.1. 使用RegExp构造函数创建正则表达式 1.1.2. 使用正则表达式字面量语法创建正则表达式 1.1.3. 正则表达式的应用 2. 修饰符 3. 方括号 4. 元字符 5. 量词 6. RegExp对象方法 7. 支持正则的String的方法 8. 正则表达式体验 8.1. 验证 …
阅读更多...
python开发应该具备哪些能力

python开发应该具备哪些能力

Python开发能力涵盖了多个方面&#xff0c;这些能力不仅涉及Python语言本身&#xff0c;还包括与Python开发相关的技术栈、工具和方法论。以下是一些关键的Python开发能力&#xff1a; Python语言基础&#xff1a; 熟练掌握Python的语法和核心特性&#xff0c;如变量、数据类型…
阅读更多...
arm64-v8a、armeabi-v7a、x86、x86_64

arm64-v8a、armeabi-v7a、x86、x86_64

当我们去GitHub下载应用的时候是不是经常很懵逼&#xff0c;就像下图一样&#xff0c;粗看一下如此多安装包到底要选择下载哪个且每种安装包到底有哪差别&#xff1f;毕竟因为自己一无所知&#xff0c;有时便随意下载一个后&#xff0c;安装时却报『此版本与你的系统不兼容』的…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站