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

ops/2024/9/19 18:56:25/ 标签: 数据结构, 链表, 队列, 单链表

 

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

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

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

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/ops/15138.html

相关文章

css3中有哪些伪类？

css3中有哪些伪类？

CSS3中有很多伪类&#xff0c;以下是一些常见的伪类&#xff1a; :hover&#xff1a;用于选择鼠标悬停在元素上的状态。:active&#xff1a;用于选择被用户激活&#xff08;点击&#xff09;的元素。:focus&#xff1a;用于选择当前拥有焦点的元素&#xff08;例如输入框&…
阅读更多...
掌握未来通信技术：5G核心网基础入门

掌握未来通信技术：5G核心网基础入门

&#x1f525;个人主页&#xff1a;Quitecoder &#x1f525;专栏&#xff1a;5GC笔记仓 朋友们大家好&#xff0c;本篇文章是我们新内容的开始&#xff0c;我们本篇进入5GC的学习&#xff0c;希望大家多多支持&#xff01; 目录 一.核心网的演进2G核心网2.5G核心网3G核心网4G…
阅读更多...
尾矿库安全监测：仪器埋设与维护的关键要求

尾矿库安全监测：仪器埋设与维护的关键要求

尾矿库作为矿业生产的重要组成部分&#xff0c;其安全运营对于保障人员生命安全和环境保护具有至关重要的意义。为了确保尾矿库的安全运行&#xff0c;及时发现潜在的安全隐患&#xff0c;必须采取有效的安全监测措施。本文将重点探讨尾矿库安全监测仪器的埋设及维护要求。 一、…
阅读更多...
Python 全栈安全（二）

Python 全栈安全（二）

原文&#xff1a;annas-archive.org/md5/712ab41a4ed6036d0e8214d788514d6b 译者&#xff1a;飞龙 协议&#xff1a;CC BY-NC-SA 4.0 第二部分&#xff1a;认证与授权 本书的第二部分是最具商业价值的部分。我这样说是因为它充满了大多数系统需要具备的实用工作流示例&#xf…
阅读更多...
代码随想录第34天: 贪心part03

代码随想录第34天: 贪心part03

力扣 1005.K次取反后最大化的数组和 class Solution {public int largestSumAfterKNegations(int[] nums, int k) {// 将基本类型的int数组转换成IntStream&#xff0c;以便进行流操作。nums Arrays.stream(nums)// 将IntStream中的int元素转换&#xff08;装箱&#xff09;为…
阅读更多...
怎样快速打造二级分销小程序

怎样快速打造二级分销小程序

乔拓云是一个专门开发小程序模板的平台&#xff0c;致力于帮助商家快速上线自己的小程序。通过套用乔拓云提供的精美模板&#xff0c;商家无需具备专业的技术背景&#xff0c;也能轻松打造出功能齐全、美观大方的小程序。 在乔拓云的官网&#xff0c;商家可以免费注册账号并登录…
阅读更多...
SpringBoot 集成 WebSocket

SpringBoot 集成 WebSocket

前言 最近在做一个 WebSocket 通信服务的软件&#xff0c;所以必须跟着学一学。 1、WebSocket 概述 一般情况下&#xff0c;我们的服务器和服务器之间可以发送请求&#xff0c;但是服务器是不能向浏览器去发送请求的。因为设计之初并没有想到以后会出现服务端频繁向客户端发送…
阅读更多...
2024年华为OD机试真题-寻找最优的路测线路-Python-OD统一考试（C卷D卷）

2024年华为OD机试真题-寻找最优的路测线路-Python-OD统一考试（C卷D卷）

题目描述： 评估一个网络的信号质量，其中一个做法是将网络划分为栅格，然后对每个栅格的信号质量计算。路测的时候，希望选择一条信号最好的路线（彼此相连的栅格集合）进行演示。现给出R行C列的整数数组Cov，每个单元格的数值S即为该栅格的信号质量（已归一化，无单位，值越大…
阅读更多...
面试八股——常见数据结构

面试八股——常见数据结构

二叉搜索树 在二叉搜索树中&#xff0c;对于任意一个节点&#xff0c;左子树中的所有节点的值都小于该节点的值&#xff0c;右子树所有节点的值都大于该节点的值。 红黑树 红黑树是一种自平衡的二叉搜索树。 红黑树包含以下性质&#xff1a; 散列表 散列表的工作原理&#x…
阅读更多...
EasyUI-Resizable 可调整尺寸

EasyUI-Resizable 可调整尺寸

<div id"rr" style"width:100px;height:100px;border:1px solid #ccc;"></div>$(#rr).resizable({maxWidth:800,maxHeight:600 }); 属性 名称 类型 描述 默认值 disabled boolean 如果设置为 true&#xff0c;则禁止调整尺寸。 false …
阅读更多...
vue 请求php接口 header 传自定义参数 提示cors 跨域问题

vue 请求php接口 header 传自定义参数 提示cors 跨域问题

前端地址 http://192.168.0.125:4021 请求后端地址的时候报 from origin http://192.168.0.125:4021 has been blocked by CORS policy: Request header field userid is not allowed by Access-Control-Allow-Headers in preflight response. 大概意思是请求 header里有个…
阅读更多...
数据结构 - 顺序表

数据结构 - 顺序表

一. 线性表的概念 线性表&#xff08;linear list&#xff09;是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构&#xff0c;常见的线性表&#xff1a;顺序表、链表、栈、队列、字符串... 线性表在逻辑上是线性结构&#xff0c;也就说是连续的…
阅读更多...
极限电流型氧气传感器的压力补偿

极限电流型氧气传感器的压力补偿

在氧浓度恒定的条件下&#xff0c;对极限电流氧气传感器在不同压力下测试数据进行分析发现&#xff0c;气压变化将导致传感器测量值与真实值存在测试误差较大。针对该问题&#xff0c;提出了极限电流氧气传感器低压条件下压力补偿方法&#xff0c;并进行了实验验证。压力补偿后…
阅读更多...
AIGC技术的探索与展望：跨界融合与科技变革

AIGC技术的探索与展望：跨界融合与科技变革

文章目录 前言一、AIGC技术的现状与特点二、AIGC技术在各个领域的应用三、AIGC技术对未来社会的影响四、AIGC技术的可能发展方向 前言 随着科技的飞速发展&#xff0c;人工智能与大数据的结合日益紧密&#xff0c;AIGC&#xff08;人工智能生成内容&#xff09;技术作为这一领域…
阅读更多...
力扣——位运算系列

力扣——位运算系列

【LeetCode 137. 只出现一次的数字 II】 这题有两个思路&#xff1a; 1&#xff09;逐位考虑&#xff1b; 2&#xff09;状态机&#xff1b; 先来看逐位考虑的思路&#xff1a; 如果对于 nums 中的每个数只观察某一位&#xff0c;因为除了一个数&#xff08;后用 a 来代称&…
阅读更多...
Docker容器：docker基础

Docker容器：docker基础

目录 一.docker前言 云计算服务模式 关于 docker 产品 虚拟化产品有哪些&#xff1f; ① 寄居架构 ② 源生架构 虚拟化技术概述 主流虚拟化产品对比 1. VMware系列 2. KVM/OpenStack 3. Xen 4. 其他半/全虚拟化产品 二. docker 的相关知识 1. docker 的概念 doc…
阅读更多...
用斐波那契数列感受算法的神奇（21亿耗时0.02毫秒）

用斐波那契数列感受算法的神奇（21亿耗时0.02毫秒）

目录 一、回顾斐波那契数列 二、简单递归方法 &#xff08;一&#xff09;解决思路 &#xff08;二&#xff09;代码展示 &#xff08;三&#xff09;性能分析 三、采用递归HashMap缓存 &#xff08;一&#xff09;解决思路 &#xff08;二&#xff09;代码展示 &…
阅读更多...
基于adb操作安卓手机封装的python库

基于adb操作安卓手机封装的python库

import re import shlex import subprocessclass ADBClient:def __init__(self, ip, port):"""初始化ADBClient实例。:param ip: 远程设备的IP地址。:param port: 远程设备的端口号。"""self.ip ipself.port portdef is_app_running(self, pac…
阅读更多...
git版本库瘦身你知道吗

git版本库瘦身你知道吗

1.问题缘由 新开发一个git项目时&#xff0c;可能会使用之前的代码库作为基准&#xff0c;并且之前的代码库中可能有许多git提交记录&#xff08;.git文件夹下面有许多提交记录存储&#xff09;。这时需要处理以下2种情况。 1&#xff09;远程代码库中还未上传git提交记录&am…
阅读更多...
使用FunASR处理语音识别

使用FunASR处理语音识别

FunASR是阿里的一个语音识别工具&#xff0c;比SpeechRecognition功能多安装也很简单&#xff1b; 官方介绍&#xff1a;FunASR是一个基础语音识别工具包&#xff0c;提供多种功能&#xff0c;包括语音识别&#xff08;ASR&#xff09;、语音端点检测&#xff08;VAD&#xff…
阅读更多...
最新文章

Copyright @ 2022~2023

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