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

 

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

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

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

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 == NULL
	assert(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;  // 最后别忘了头尾指针置为 NULL
	pq->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  /  ptail

	for (int i = 1; i <= 5; ++i) {  // 入队列 几个元素： 1 2 3 4 5
		QueuePush(&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;  // 最后别忘了头尾指针置为 NULL
	pq->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 次

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/563688.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

查询服务器上所有SQL SERVER数据库中是否包含某个字段，且该字段是否包含某个值

查询服务器上所有SQL SERVER数据库中是否包含某个字段，且该字段是否包含某个值

公司有一堆相同类别的客户&#xff0c;每个客户都部署了相同的一套系统&#xff0c;每套系统对应一个相同结构的数据库&#xff0c;昨天老板让查一下手机号码177xxxxx248是属于哪个客户的客户。 我要查的这个号码来自于oa_member表中的phone字段&#xff0c;我需要对所有的数据…
阅读更多...
2024年51cto视频如何提取

2024年51cto视频如何提取

2024年&#xff0c;对于如何提取51cto网站上的视频&#xff0c;许多人都选择在该平台购买自己所需的学习视频。然而&#xff0c;在51cto网页上观看视频将消耗用户的流量。为了解决这一问题&#xff0c;我开发了名为小白51cto工具的软件&#xff0c;使用户能够轻松将视频下载到本…
阅读更多...
【图解计算机网络】网络协议分层解析

【图解计算机网络】网络协议分层解析

网络协议分层解析 网络协议分层应用层传输层网络层数据链路层 TCP/IP分层模型通讯示例 网络协议分层 网络协议分层一共有OSI七层网络协议&#xff0c;TCP/IP四层网络网络协议&#xff0c;还有五层网络协议。 七层由于分层太多过于复杂&#xff0c;实际应用中并没有使用&#x…
阅读更多...
解析deb与rpm文件的操作技巧

解析deb与rpm文件的操作技巧

欢迎来到我的博客&#xff0c;代码的世界里&#xff0c;每一行都是一个故事 解析deb与rpm文件的操作技巧 前言deb文件介绍与操作deb 文件介绍特点和用途在 Debian、Ubuntu 系统中使用 deb 文件进行软件安装和管理安装 deb 文件处理依赖问题更新和卸载使用 APT 进行管理 deb文件…
阅读更多...
学习笔记：Vue3（图片明天处理）

学习笔记：Vue3（图片明天处理）

文章目录 1.概述1.1定义1.2特性1.3组合式API 2.基本用例-项目搭建3.项目目录介绍3.1概述3.2查看文件 4.组合式API4.1概述4.2新的API风格4.2.1概述4.2.2写法4.2.3基本用例-Setup选项使用4.2.4基本用例-语法糖写法&#xff08;重点&#xff09;4.2.5执行时机4.2.6代码特点 4.3响应…
阅读更多...
C++从入门到精通——模板

C++从入门到精通——模板

模板 前言一、泛型编程二、函数模板函数模板的概念函数模板格式示例 函数模板的原理函数模板的实例化隐式实例化显式实例化示例 auto做模板函数的返回值模板参数的匹配原则总结 三、类模板类模板的定义格式类模板的实例化 前言 C模板是C语言中的一种泛型编程技术&#xff0c;可…
阅读更多...
《星尘传说》游戏完整源码（源码+引擎+客户端+服务端+教程+工具），云盘下载

《星尘传说》游戏完整源码（源码+引擎+客户端+服务端+教程+工具），云盘下载

《星尘传说》是一款奇幻类大型多人在线角色扮演电脑客户端游戏&#xff0c;该游戏设置有两大阵营&#xff0c;六个国家以及22个职业&#xff0c;采用3D卡通风格&#xff0c; 有兴趣的&#xff0c;可以架设个外网&#xff0c;让大家一起玩。 《星尘传说》游戏完整源码&#xff0…
阅读更多...
采用分治法求含n个实数序列中的最大元素和次大元素（C语言）

采用分治法求含n个实数序列中的最大元素和次大元素（C语言）

目录 实验内容&#xff1a; 实验过程&#xff1a; 1.算法设计 2.程序清单 3.复杂度分析 4.运行结果 实验内容&#xff1a; 设计一个程序&#xff0c;采用分治法求含n个实数序列中的最大元素和次大元素&#xff0c;并分析算法的时间复杂度。 实验过程&#xff1a; 1.算法…
阅读更多...
如何增强Java GCExcel API 的导入和导出性能

如何增强Java GCExcel API 的导入和导出性能

前言 GrapeCity Documents for Excel (以下简称GcExcel) 是葡萄城公司的一款服务端表格组件&#xff0c;它提供了一组全面的 API 以编程方式生成 Excel (XLSX) 电子表格文档的功能&#xff0c;支持为多个平台创建、操作、转换和共享与 Microsoft Excel 兼容的电子表格&#xf…
阅读更多...
[计算机效率] 网站推荐：图片编辑类

[计算机效率] 网站推荐：图片编辑类

4.4 图片编辑类 在数字化时代&#xff0c;图片编辑已成为我们生活和工作中不可或缺的一部分。为了帮助大家更高效、更专业地进行图片编辑&#xff0c;这里推荐一系列优质的在线图片编辑网站。 这些网站不仅拥有直观易用的操作界面&#xff0c;更提供了丰富的编辑功能和素材资源…
阅读更多...
jenkins 部署 vue 项目

jenkins 部署 vue 项目

jenkins 部署 vue 项目 环境 系统&#xff1a;CentOS7.9 Jenkins&#xff1a;最新LTS版本 nginx: 1.24.x gitLab: 打包机&#xff1a;jenkins所在服务器 目标机器&#xff1a;nginx所在服务器 jenkins部署配置 关键脚本 #node -v #已经安装node_module就无需执行install安…
阅读更多...
快排非递归与计数排序

快排非递归与计数排序

感谢大佬的光临各位&#xff0c;希望和大家一起进步&#xff0c;望得到你的三连&#xff0c;互三支持&#xff0c;一起进步 个人主页&#xff1a;LaNzikinh-CSDN博客 收入专栏:初阶数据结构_LaNzikinh篮子的博客-CSDN博客 文章目录 前言一.快速排序非递归二.数据结构栈与内存栈…
阅读更多...
【埋点探针】微信小程序SDK安装

【埋点探针】微信小程序SDK安装

一、下载微信小程序SDK埋点代码 选择Wechat&#xff0c;复制sdk代码 在项目根目录下&#xff0c;创建sdk文件&#xff0c;webfunny.event.js 二、在app.js文件中&#xff0c;引入埋点SDK代码 首先引入sdk代码 require("./webfunny.event.js")引入兼容代码&#x…
阅读更多...
职业技能鉴定服务中心（新闻系统+证书查询系统）

职业技能鉴定服务中心（新闻系统+证书查询系统）

后端采用ThinkPHP8&#xff0c;最新tp框架 前端采用divcss布局 数据库采用MySQL 采用三种技术实现新闻系统和证书查询系统 源码&#xff1a;git clone https://gitee.com/3539949703/certificate-website.git 效果图如下&#xff1a;
阅读更多...
一套在线画图工具（突突图 Procviz）

一套在线画图工具（突突图 Procviz）

突突图(Procviz)是一款面向跨平台作图平台。支持流程图、思维导图、框架图、组织架构图、ER图、网络拓扑图等。实现了多团体同时协作&#xff0c;实时同步&#xff0c;解决跨地域合作作图的问题。平台提供了丰富的模板和素材库&#xff0c;轻松完成作图&#xff0c;效率翻倍。 …
阅读更多...
docker pull速度慢解决办法

docker pull速度慢解决办法

在使用 Docker 时遇到拉取镜像速度慢的问题&#xff0c;可以使用国内的镜像源可以提高下载速度。 使用阿里镜像加速器 Docker 配置文件位于 /etc/docker/daemon.json。如果文件不存在&#xff0c;可以手动创建它。将以下内容添加到配置文件中&#xff1a; 整体复制执行命令&…
阅读更多...
【设计模式】单例模式｜最常用的设计模式

【设计模式】单例模式｜最常用的设计模式

写在前面 单例模式是最常用的设计模式之一&#xff0c;虽然简单&#xff0c;但是还是有一些小坑点需要注意。本文介绍单例模式并使用go语言实现一遍单例模式。 单例模式介绍 简介 单例模式保证一个类仅有一个实例&#xff0c;并提供一个访问它的全局访问点。 使用场景&#…
阅读更多...
web自动化系列-selenium的3种弹框操作(十二)

web自动化系列-selenium的3种弹框操作(十二)

在进行功能测试时 &#xff0c;经常会遇到出现各种的弹出的提示 &#xff0c;比如删除数据给出提示 、做某个操作时也会弹框给出一些友好提示 &#xff0c;因为这些弹框都是做web操作时的一些常用组件 &#xff0c;所以&#xff0c;selenium就不得不支持这些组件 。 1.弹框介绍…
阅读更多...
HarmonyOS开发环境搭建 移动开发 鸿蒙开发 ArkTS

HarmonyOS开发环境搭建 移动开发 鸿蒙开发 ArkTS

&#x1f4dc;目录 &#x1f4a1; 环境搭建 &#x1f680;安装nodejs &#x1f935;安装ohpm &#x1f354;安装SDK &#x1f4a5;Emulator安装 &#x1f336;️新建ArkTs项目 &#x1f3c6;️ArkTS语言 ✨️基本语法 &#x1f388; 声明式UI描述 &#x1f371;组件 …
阅读更多...
【C语言__函数栈帧的创建和销毁__复习篇9】

【C语言__函数栈帧的创建和销毁__复习篇9】

目录 前言 一、知识补充 二、分析创建和销毁的过程 三、前言问题回答 前言 本篇主要讨论以下问题&#xff1a; 1. 编译器什么时候为局部变量分配的空间 2. 为什么局部变量的值是随机的 3. 函数是怎么传参的&#xff0c;传参的顺序是怎样的 4. 形参和实参是什么关系 5. 函数…
阅读更多...
最新文章

Copyright @ 2022~2023