深入理解数据结构(3)：栈和队列详解

标头风景图片

  • 文章主题：顺序表和链表详解🌱
  • 所属专栏：深入理解数据结构📘
  • 作者简介：更新有关深入理解数据结构知识的博主一枚，记录分享自己对数据结构的深入解读。😄
  • 个人主页：[₽]的个人主页🔥🔥

栈和队列详解

  • 前言
  • 栈
    • 栈的概念及结构
    • 栈的实现
  • 队列
    • 队列的概念及结构
    • 队列的实现
  • 结语

前言

上文我们已经讲完了线性表中最基本的、最常用的顺序表和链表，这一次博主为大家带来基于顺序表和链表实现的线性表中也是十分常用的数据结构栈和队列的详解，希望能够让你对数据结构有一个更加深入的理解。

栈

栈的概念及结构

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。
压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈/弹栈。出数据也在栈顶。
栈的后进先出

栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小，最简单。
栈的数组实现
静态数组栈
下面是定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈

// 下面是定长的静态栈的结构，实际中一般不实用，所以我们主要实现下面的支持动态增长的栈
typedef int STDataType;
#define N 10
typedef struct Stack
{STDataType _a[N];int _top; // 栈顶
}Stack;

动态数组栈
Stack.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{STDataType* _a;int _top;		// 栈顶int _capacity;  // 容量 
}Stack;
// 初始化栈 
void StackInit(Stack* ps);
// 入栈 
void StackPush(Stack* ps, STDataType data);
// 出栈 
void StackPop(Stack* ps);
// 获取栈顶元素 
STDataType StackTop(Stack* ps);
// 获取栈中有效元素个数 
int StackSize(Stack* ps);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
int StackEmpty(Stack* ps);
// 销毁栈 
void StackDestroy(Stack* ps);

Stack.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Stack.h"
void StackInit(Stack* ps)
{assert(ps);// 栈区数组未创建，赋成NULLps->_a = NULL;ps->_capacity = 0;// 表示top指向栈顶元素ps->_top = -1;// 表示top指向栈顶元素的下一个//ps->_top = 0
}
void StackPush(Stack* ps, STDataType data)
{assert(ps);// 栈区数据已满，扩容if (ps->_top + 1 == ps->_capacity){// 确定扩容后的新容量，如果是 0 就扩容为 4 ，如果已经扩过容了就将容量在增加一个原来这么多，即扩大为原来的两倍int newcapacity = ps->_capacity == 0 ? 4 : ps->_capacity * 2;// 扩容STDataType* tmp = (STDataType*)realloc(ps->_a, newcapacity * sizeof(STDataType));// 扩容失败打印失败原因后返回if (tmp == NULL){perror("realloc fail");return;}// 未失败将容量更新成新容量，数据指针更新成新指针ps->_capacity = newcapacity;ps->_a = tmp;}// 插入数据ps->_top++;ps->_a[ps->_top] = data;
}
void StackPop(Stack* ps)
{assert(ps);// 栈不为空时才能删除数据assert(ps->_top + 1 > 0);// 栈顶元素坐标下移，删除数据ps->_top--;
}
STDataType StackTop(Stack* ps)
{assert(ps);// 不为空，为空弹不出数据来进行访问，并且访问会导致数组越界assert(ps->_top + 1 > 0);// 返回栈顶元素值return ps->_a[ps->_top];
}
int StackSize(Stack* ps)
{assert(ps);// 返回栈中有效元素个数（栈顶元素 +1 即为栈中有效元素个数）return ps->_top + 1;
}
int StackEmpty(Stack* ps)
{assert(ps);// 为空则返回非 0 的真return ps->_top + 1 == 0;
}
void StackDestroy(Stack* ps)
{assert(ps);// 数据内存释放，再将记录数据的各值清空free(ps->_a);ps->_a = NULL;ps->_capacity = 0;ps->_top = -1;
}

Test.c

#include "Stack.h"
void StackTest1()
{// 初始化栈Stack S1;StackInit(&S1);// 数据入栈StackPush(&S1, 1);StackPush(&S1, 2);StackPush(&S1, 3);StackPush(&S1, 4);StackPush(&S1, 5);// 销毁栈StackDestroy(&S1);// 检测是否销毁成功if (S1._a == NULL && S1._capacity == 0 && S1._top == -1)printf("销毁成功！\n");elseprintf("销毁失败。\n");
}
void StackTest2()
{// 初始化栈Stack S1;StackInit(&S1);// 数据入栈StackPush(&S1, 1);StackPush(&S1, 2);StackPush(&S1, 3);StackPush(&S1, 4);StackPush(&S1, 5);// 从栈顶读取数据后弹出栈中数据while (!StackEmpty(&S1)){printf("%d ", StackTop(&S1));StackPop(&S1);}printf("\n");// 销毁栈StackDestroy(&S1);
}
void StackTest3()
{// 初始化栈Stack S1;StackInit(&S1);// 栈为空时也弹出数据StackPop(&S1);// 销毁栈StackDestroy(&S1);
}
int main()
{StackTest3();return 0;
}

队列

队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头
入队：队列的插入操作叫做入队，入数据在队尾。
出队：队列的删除操作叫做出队。出数据在队头。
（栈和对列都是将出数据的地方叫作顶/头）
队列的出队入队

队列的实现

队列也可以数组和链表的结构实现，使用链表（带头的单链表）的结构实现更优一些(时间复杂度O(1)，比数组来说在队头删除数据更加简洁)，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低(时间复杂度为O(N))。
带头单链表实现的队列
队列
Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int QDataType;
// 链式结构：表示队列 
typedef struct QListNode
{struct QListNode* _next;QDataType _data;
}QNode;// 队列的结构 
typedef struct Queue
{QNode* _front;QNode* _rear;int _size;
}Queue;// 初始化队列 
void QueueInit(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
void QueueInit(Queue* q)
{assert(q);// 首尾指针都赋成NULL，元素个数赋0q->_front = q->_rear = NULL;q->_size = 0;
}
void QueueDestroy(Queue* q)
{assert(q);// 释放队列数据内存QNode* cur = q->_front;while (cur){QNode* tmp = cur;cur = cur->_next;free(tmp);}// 将队列中的首尾指针数据赋成NULL，队列元素个数也置为0q->_front = q->_rear = NULL;q->_size = 0;
}
void QueuePush(Queue* q, QDataType data)
{assert(q);// 创建新节点QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("maloc fail");return;}newnode->_data = data;newnode->_next = NULL;// 无节点if (q->_front == NULL){q->_front = q->_rear = newnode;}// 有节点else{q->_rear->_next = newnode;q->_rear = newnode;}// 队尾入数据时总元素个数加一q->_size++;
}
void QueuePop(Queue* q)
{assert(q);// 无节点assert(q->_front);// 有节点QNode* tmp = q->_front;q->_front = q->_front->_next;free(tmp);// 一个节点时，尾指针因为释放节点变成野指针，需要置空if (q->_front == NULL)q->_rear = NULL;// 队头出数据时总元素个数减一q->_size--;
}
QDataType QueueFront(Queue* q)
{assert(q);// 无节点assert(q->_front);// 有节点return q->_front->_data;
}
QDataType QueueBack(Queue* q)
{assert(q);// 无节点assert(q->_front);// 有节点return q->_rear->_data;
}
int QueueSize(Queue* q)
{assert(q);// 直接将储存队列主要数据的结构体中的元素个数拿出来返回return q->_size;
}
int QueueEmpty(Queue* q)
{assert(q);return q->_size == 0;
}

Test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"
void QueueTest1()
{// 队列初始化Queue Q1;QueueInit(&Q1);// 队尾入数据QueuePush(&Q1, 1);QueuePush(&Q1, 2);QueuePush(&Q1, 3);QueuePush(&Q1, 4);QueuePush(&Q1, 5);// 销毁队列QueueDestroy(&Q1);if (Q1._front == NULL && Q1._rear == NULL && Q1._size == 0)printf("销毁成功！\n");elseprintf("销毁失败。\n");
}void QueueTest2()
{// 队列初始化Queue Q1;QueueInit(&Q1);// 队尾入数据QueuePush(&Q1, 1);QueuePush(&Q1, 2);QueuePush(&Q1, 3);QueuePush(&Q1, 4);QueuePush(&Q1, 5);// 打印队列中的数据printf("Queue: \n");while (!QueueEmpty(&Q1)){printf("%d ", QueueFront(&Q1));QueuePop(&Q1);}printf("\n");// 销毁队列QueueDestroy(&Q1);
}void QueueTest3()
{// 队列初始化Queue Q1;QueueInit(&Q1);// 队尾入数据QueuePush(&Q1, 1);QueuePush(&Q1, 2);QueuePush(&Q1, 3);QueuePush(&Q1, 4);QueuePush(&Q1, 5);// 打印队列中的数据printf("Queue: \n");while (!QueueEmpty(&Q1)){printf("%d ", QueueFront(&Q1));QueuePop(&Q1);}printf("\n");// 无节点从队列中弹出数据QueuePop(&Q1);// 销毁队列QueueDestroy(&Q1);
}void QueueTest4()
{// 队列初始化Queue Q1;QueueInit(&Q1);// 队尾入数据QueuePush(&Q1, 1);QueuePush(&Q1, 2);QueuePush(&Q1, 3);QueuePush(&Q1, 4);QueuePush(&Q1, 5);// 打印队尾中的数据printf("BackNum: \n%d\n", QueueBack(&Q1));// 打印队列中的数据printf("Queue: \n");while (!QueueEmpty(&Q1)){printf("%d ", QueueFront(&Q1));QueuePop(&Q1);}printf("\n");// 销毁队列QueueDestroy(&Q1);
}void QueueTest5()
{// 队列初始化Queue Q1;QueueInit(&Q1);// 队尾入数据QueuePush(&Q1, 1);QueuePush(&Q1, 2);QueuePush(&Q1, 3);QueuePush(&Q1, 4);QueuePush(&Q1, 5);// 打印队列中的数据个数printf("QueueSize: \n%d\n", QueueSize(&Q1));// 打印队列中的数据printf("Queue: \n");while (!QueueEmpty(&Q1)){printf("%d ", QueueFront(&Q1));QueuePop(&Q1);}printf("\n");// 销毁队列QueueDestroy(&Q1);
}int main()
{QueueTest5();return 0;
}

环形队列
另外扩展了解一下，实际中我们有时还会使用一种队列叫循环队列。如操作系统中的生产者消费者模型中就会使用循环队列。环形队列可以使用数组实现，也可以使用循环链表实现（差别不是很大，并且环形队列的元素个数是固定的，但也可以不是在栈区的静态数组实现的，其可用在动态区用长度不变的数组来实现内存大小不变的效果，可理解成动态数组大小不变所实现的仿静态效果，并且虽逻辑结构上两种环形队列都相接，数组型的环形队列物理结构上首尾不相接，链表物理结构上相接）。
环形队列逻辑图
通常为区分队头和队尾，会在数组中多加一个元素来既防止数组越界，又能够解决因空和满索引条件相同而造成无法判断的假溢出问题（此时环形队列容量为数组总元素个数减一）：
数组环形队列实现的底层逻辑图

结语

以上就是博主对栈和队列的详解，😄希望对你的数据结构的学习有所帮助！看都看到这了，点个小小的赞或者关注一下吧（当然三连也可以~），你的支持就是博主更新最大的动力！让我们一起成长，共同进步！

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

【研发日记】Matlab/Simulink开箱报告(十一)——Requirements Toolbox

【研发日记】Matlab/Simulink开箱报告(十一)——Requirements Toolbox

目录 前言 Requirements Toolbox 编写需求 需求联接设计 需求跟踪开发进度 追溯性矩阵 分析和应用 总结 前言 见《开箱报告&#xff0c;Simulink Toolbox库模块使用指南&#xff08;六&#xff09;——S-Fuction模块&#xff08;TLC&#xff09;》 见《开箱报告&#x…
阅读更多...
25Ramdisk 启动模式简介

25Ramdisk 启动模式简介

Ramdisk 启动模式简介 ramdisk是一种虚拟磁盘技术,我们的PE系统几乎都是使用ramdisk方式从计算机启动的.那么,ramdisk有哪些特点呢? Ramdisk 将内存虚拟为一个磁盘 Ramdisk技术会将你的一部分内存虚拟成一块磁盘分区.使用U盘启动pe系统时,打开pe系统里的文件资源管理器,你会看…
阅读更多...
实验三智能手机互联网程序设计（微信程序方向）实验报告

实验三智能手机互联网程序设计（微信程序方向）实验报告

实验目的和要求 请编写下方商品列表页面&#xff0c;展示商品名称和价格&#xff1b; 二、实验步骤与结果&#xff08;给出对应的代码或运行结果截图&#xff09; Index.WXML <view class"shop" wx:for"{{10}}"> <vie…
阅读更多...
vue3全局控制Element plus所有组件的文字大小

vue3全局控制Element plus所有组件的文字大小

项目框架vue-右上角有控制全文的文字大小 实现&#xff1a; 只能控制element组件的文字及输入框等大小变化&#xff0c;如果是自行添加div,text, span之类的控制不了。 配置流程 APP.vue 使用element的provide&#xff0c;包含app <el-config-provider :locale"loca…
阅读更多...
JavaSE：继承和多态（下篇）

JavaSE：继承和多态（下篇）

目录 一、前言 二、多态 &#xff08;一&#xff09;多态的概念 &#xff08;二&#xff09;多态实现条件 &#xff08;三&#xff09;多态的优缺点 三、重写 &#xff08;一&#xff09;重写的概念 &#xff08;二&#xff09;重写的规则 &#xff08;三&#xff09;重…
阅读更多...
2024年京东云主机租用价格_京东云服务器优惠价格表

2024年京东云主机租用价格_京东云服务器优惠价格表

2024年京东云服务器优惠价格表&#xff0c;轻量云主机优惠价格5.8元1个月、轻量云主机2C2G3M价格50元一年、196元三年&#xff0c;2C4G5M轻量云主机165元一年&#xff0c;4核8G5M云主机880元一年&#xff0c;游戏联机服务器4C16G配置26元1个月、4C32G价格65元1个月、8核32G费用…
阅读更多...
Sentinel入门流控编码方式

Sentinel入门流控编码方式

系列文章目录 文章目录 系列文章目录前言前言 前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站，这篇文章男女通用，看懂了就去分享给你的码吧。 随着微服务的流行，服务和服务之间的稳定性变得越来越重要。Sentinel 以流…
阅读更多...
安科瑞路灯安全用电云平台解决方案【电不起火、电不伤人】

安科瑞路灯安全用电云平台解决方案【电不起火、电不伤人】

背景介绍 近年来 &#xff0c;随着城市规模的不断扩大 &#xff0c;路灯事业蓬勃发展。但有的地方因为观念、技术、管理等方面不完善 &#xff0c;由此引发了一系列安全问题。路灯点多面广 &#xff0c;一旦漏电就极容易造成严重的人身安全事故。不仅给受害者家庭带来痛苦 &am…
阅读更多...
【Docker笔记02】【常用软件安装】

【Docker笔记02】【常用软件安装】

一、前言 本系列是根据 B 站 尚硅谷 Docker 视频 学习记录笔记。因为没有视频课件&#xff0c;部分内容摘自 https://www.yuque.com/tmfl/cloud/dketq0。 本系列仅为自身学习笔记记录使用&#xff0c;记录存在偏差&#xff0c;推荐阅读原视频内容或本文参考笔记。 本文主要介…
阅读更多...
输出1到10的阶乘--C语言

输出1到10的阶乘--C语言

#include<stdio.h> int fac(int n){if(n<1){return 1;}elsereturn fac(n-1)*n; } int main(){int i, result;for(i1;i<10;i){resultfac(i);printf("%d!%d\n",i,result);}} 输出结果&#xff1a;
阅读更多...
2024 MCM数学建模美赛2024年A题复盘，思路与经验分享：资源可用性与性别比例 | 性别比例变化是否对生态系统中的其他生物如寄生虫提供优势（五）

2024 MCM数学建模美赛2024年A题复盘，思路与经验分享：资源可用性与性别比例 | 性别比例变化是否对生态系统中的其他生物如寄生虫提供优势（五）

审题 第四问让我们探究性别比例变化是否对生态系统中的其他生物如寄生虫提供优势。这里我们可以把问题简化一下&#xff0c;只探究性别比例会不会对寄生虫提供优势。因为考虑太多生物&#xff0c;会使模型更复杂&#xff0c;我这个水平处理不了这么复杂的问题&#xff0c;是我…
阅读更多...
保研线性代数机器学习基础复习1

保研线性代数机器学习基础复习1

1.什么是代数&#xff08;algebra&#xff09;? 为了形式化一个概念&#xff0c;构建出有关这个概念的符号以及操作符号的公式。 2.什么是线性代数&#xff08;linear algebra&#xff09;&#xff1f; 一项关于向量以及操作向量的公式的研究。 3.举一些向量的例子&#x…
阅读更多...
瑞吉外卖实战学习--8、人员禁用和启用

瑞吉外卖实战学习--8、人员禁用和启用

前言 1、通过前端页面查看接口 会发现请求方式是put 请求接口是employee 2、检查页面传值 根据浏览器的请求可以看到传值为id和status 2、写put请求&#xff0c;添加修改时间和修改人的id然后传回给后台 /*** 启用和禁用员工账号* param request* param employee* return…
阅读更多...
基于Java实现宠物领养救助交流平台设计和实现

基于Java实现宠物领养救助交流平台设计和实现

基于Java实现宠物领养救助交流平台设计和实现 博主介绍&#xff1a;多年java开发经验&#xff0c;专注Java开发、定制、远程、文档编写指导等,csdn特邀作者、专注于Java技术领域 作者主页 央顺技术团队 Java毕设项目精品实战案例《1000套》 欢迎点赞 收藏 ⭐留言 文末获取源码联…
阅读更多...
二维码门楼牌管理应用平台：创新管理与服务的全新方式

二维码门楼牌管理应用平台：创新管理与服务的全新方式

文章目录 前言一、二维码门楼牌管理应用平台的建设背景二、二维码门楼牌管理应用平台的功能特点三、切换功能在城市管理中的应用四、二维码门楼牌管理应用平台的未来展望 前言 在数字化时代的浪潮中&#xff0c;二维码技术以其便捷、高效的特点&#xff0c;正逐渐渗透到我们生…
阅读更多...
SpringBoot集成WebSocket实现简单的多人聊天室

SpringBoot集成WebSocket实现简单的多人聊天室

上代码—gitee下载地址&#xff1a; https://gitee.com/bestwater/Spring-websocket.git下载代码&#xff0c;连上数据库执行SQL&#xff0c;就可以运行&#xff0c;最终效果
阅读更多...
金融汽车科技LLM

金融汽车科技LLM

汇丰银行 众安保险 1. AIGC重塑保险价值链 小额高频 2.构建智能应用的技术方案演进 增加微服务 长记忆&#xff1a;向量库短记忆&#xff1a;对话历史&#xff0c;思考路径&#xff0c;执行历史 中台架构设计 蔚来汽车在大模型的应用实践 公司介绍 应用架构 应用实践 4.大…
阅读更多...
基于单片机的自动浇灌系统的设计

基于单片机的自动浇灌系统的设计

本文设计了一款由单片机控制的自动浇灌系统。本设计的硬件电路采用AT89C51单片机作为主控芯片，采用YL-69土壤湿度传感器检测植物的湿度。通过单片机将采集湿度值与设定值分析处理后，控制报警电路和水泵浇灌电路的开启，从而实现植物的自动浇灌。 1 设计目的 随着生活水平的…
阅读更多...
Python API(happybase)操作Hbase案例

Python API(happybase)操作Hbase案例

一、Windows下安装Python库&#xff1a;happybase pip install happybase -i https://pypi.tuna.tsinghua.edu.cn/simple 二、 开启HBase的Thrift服务 想要使用Python API连接HBase&#xff0c;需要开启HBase的Thrift服务。所以&#xff0c;在Linux服务器上&#xff0c;执行如…
阅读更多...
Lucene及概念介绍

Lucene及概念介绍

Lucene及概念介绍 基础概念倒排索引索引合并分析查询语句的构成 基础概念 Document&#xff1a;我们一次查询或更新的载体&#xff0c;对比于实体类 Field&#xff1a;字段&#xff0c;是key-value格式的数据&#xff0c;对比实体类的字段 Item&#xff1a;一个单词&#xff0…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023