数据结构——栈与队列的实现（全码）

一  栈的概念

        栈是一种特殊的线性表，栈内数据遵循先进后出(LIFO)的原则，对于栈，只能在同一侧进行入栈和出栈操作。

入栈操作和出栈操作是在栈的同一侧进行的，如图示：

对于栈这种数据类型，我们可以采用链表或者数组来实现，但是我们一般采取数组的形式进行实现。

 二  栈的实现

1.栈的声明

对于一个用数组形式来实现的栈来说，我们需要声明:

指向栈的有效地址指针，栈顶(栈的有效空间)top,  栈的最大容量capacity

typedef int TypeData;
typedef struct Stack {TypeData* a;int top;      //有效个数int capacity;  //最大空间
}ST;

这里top为什么时栈的有效个数呢？因为我们让top指向了当前数组存在有效数据的最大下标+1的位置，这样top更加直观的表达当前栈内的元素

 2.栈的初始化

在一个栈创建后，需要对栈进行初始化后才能进行使用，对于栈的初始状态：

指向数组首元素地址的指针为NULL

栈初始的最大容量为0

栈顶top的指向为数组为0的下标，也就是当前栈的有效数据个数为0

void STInit(ST* ps)
{	assert(ps);ps->a = NULL;ps->capacity = ps->top = 0;
}

初始化后栈的图示如下： 

 

3.栈的入栈

        当我们往栈中入数据时，我们不能一昧的往里面入数据，在每次入数据前需要考虑当前栈的容量是否已经满了，如果当前栈的容量已满，我们需要先将栈的最大容量扩充后再进行入栈操作。

在扩充最大容量操作时，我们应当使用realloc函数，因为我们需要保留原本栈中存放的数据

在空栈时入栈，那么第一次扩充的栈的大小是4个数据类型空间（也可以是8个，10个等）

如果栈中本来就有数据，那么当栈满时，新栈的最大容量为旧栈的两倍（或整数倍）

void STPush(ST* ps, TypeData x)
{assert(ps);//检查空间是否足够if (ps->capacity == ps->top) {int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//创建newcapacity个空间ST* tmp = (ST*)realloc(ps->a, sizeof(TypeData) * newcapacity);//如果开辟空间失败if (tmp == NULL) {perror("realloc");exit(-1);}ps->capacity = newcapacity;ps->a = tmp;}//空间足够ps->a[ps->top++] = x;
}

 

 

 4.栈的出栈前提

当进行出栈操作时，需要判定栈是否为空，如果栈为空（也就是没有数据），则无法出栈。

        当栈顶为0时，说明当前栈中无数据，返回true，否则返回false 

bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}

 

 

5.栈的出栈

在栈的出栈操作前需要判断当前栈中是否存有数据，否则不能进行出栈操作

通过栈顶指针-1即可完成出栈操作

//出栈
void STPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));--ps->top;
}

 

 

6.取栈顶元素

    取栈顶元素前和出栈操作一样，需要判断当前栈是否为空，否则无法取栈顶元素

    取栈顶元素返回的是top-1位置的数据，并非top位置

TypeData STTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));//栈为空栈时无法取栈顶元素return ps->a[ps->top - 1];
}

 

 

 

7.获取栈的有效个数

    直接返回top即可，因为top不仅代表了栈顶，还代表了当前栈中的有效个数

//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}

8.栈的销毁

栈的销毁和顺序表基本一致：

void STDestroy(ST* ps)
{assert(ps);if (ps->a)free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}

 

 9.栈的全码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int TypeData;
typedef struct Stack {TypeData* a;int top;      //有效个数int capacity;  //最大空间
}ST;//初始化
void STInit(ST* ps)
{	assert(ps);ps->a = NULL;ps->capacity = ps->top = 0;
}//销毁
void STDestroy(ST* ps)
{assert(ps);if (ps->a)free(ps->a);ps->a = NULL;ps->top = ps->capacity = 0;
}//入栈
void STPush(ST* ps, TypeData x)
{assert(ps);//检查空间是否足够if (ps->capacity == ps->top) {int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;//创建newcapacity个空间ST* tmp = (ST*)realloc(ps->a, sizeof(TypeData) * newcapacity);//如果开辟空间失败if (tmp == NULL) {perror("realloc");exit(-1);}ps->capacity = newcapacity;ps->a = tmp;}//空间足够ps->a[ps->top++] = x;
}//检查是否为空栈
bool StackEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}//出栈
void STPop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));--ps->top;
}//取栈顶元素
TypeData STTop(ST* ps)
{assert(ps);assert(!StackEmpty(ps));//栈为空栈时无法取栈顶元素return ps->a[ps->top - 1];
}//获取栈中有效元素个数
int STSize(ST* ps)
{assert(ps);return ps->top;
}
int main(){return 0;}

三  队列的概念

队列是一种只允许在一侧入数据操作，另一侧出数据操作的线性表，具有先进先出的的原则

在入数据操作的一端称作队尾，在出数据的一端称作队头

而对于队列的底层，我们可以选择数组或者链表来实现，在这里我们使用链表来实现，因为采用数组来实现是，在出队操作后数组需要相继往前移动一位，这样才能使后面的的数据接着出队，因此采用数组的话在出队操作时效率会比链表低

队列的内部数据用链表来表示：

 

1.队列的声明

在 上面队列的概念中我们了解到，队列的底层由链表来实现，而队列有队头和队尾，因此队列的结构体声明有些许不同，可以理解为队列由两部分组成：链表和队列本身，因此我们需要声明两个结构体：

//队列的在链表的基础上实现，所以结构体有两个，一个是链表结点(头删尾插)
typedef int TypeData;//链表结点结构声明
typedef struct QueueNode {TypeData data;struct QueueNode* next;
}Node;
//队列本身的声明
typedef struct Queue {struct QueueNode* phead;//队头struct QueueNode* ptail;//队尾int size;//记录队列的元素个数，每次入队+1，出队-1
}Queue;

2.队列的初始化

当我们创建一个队列时，队列中是不存在数据的，也就是不存在链表结点，因此我们在初始化时不需要初始化链表结点结构体：

//队列初始化
void QueueInit(Queue* ps) {assert(ps);ps->phead = ps->ptail = NULL;ps->size = 0;
}

初始化时，队尾指针和队头指针应当为空，因为此时队列中还不存在数据（结点）

初始化后图示：

 

3.队列的入队 

在队列的入队操作中，其实是对队列中链表的尾插操作

入队步骤：

1）创建新结点

2）在结点插入时需要判断当前队列是否为空（也就是链表是否为空），如果队列为空，那么新创建的结点就是链表的头结点，此时队尾指针和队头指针都指向头结点

3）如果当前队列不为空，那么直接在原队列上进行尾插，即在链表进行尾插，原链表最后一个结点被尾指针指向，所以原最后一个结点的指针指向新结点，原尾指针更新指向新结点

4）记录队列元素个数的size +1

//队列的入队，尾插
void QueuePush(Queue* ps, TypeData x) {//申请新结点Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL) {perror("malloc");exit(1);}newNode->data = x;newNode->next = NULL;//两种情况，队列为空与不为空if (ps->phead == NULL) {ps->phead = ps->ptail = newNode;}else {//队列不为空ps->ptail->next = newNode;ps->ptail = newNode;}ps->size++;
}

4.队列的出队前提

队列的出队与栈一样，在出队前对队列判断当前队列是否为空，只有队列非空的时候才能进行出队操作

//判断队列是否为空
bool QueueEmpty(Queue* ps) {//头节点为空证明队列为空return ps->phead == NULL;
}

 5.队列的出队

对于队列的出队操作，其实就是链表的头删

       先记录下队头结点的下一个结点Next，再释放队头结点并将队头结点指向队头结点的下一个结点Next,最后再将记录队列元素size成员-1

//队列出队，头删
void QueuePop(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));Queue* Next = ps->phead->next;free(ps->phead);ps->phead = Next;ps->size--;
}

但是这样子其实考虑的并不完全，如果队列中只有一个结点，队尾指针和队头 指针都指向该结点，那么 Next的指向为NULL，当结点释放后，队头指针指向Next达到了置空的作用，但是队尾指针却没有置空，那么此时队尾指针就成为了野指针，这是不被允许的！

因此我们需要分两种情况进行讨论：队列只有一个结点和队列有多个结点

怎样判断队列是否只有一个结点：当队头指针和队尾指针的指向相同时

//队列出队，头删
void QueuePop(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));//如果队列只有一个结点if (ps->phead == ps->ptail) {free(ps->phead);ps->phead = ps->ptail = NULL;}else {//队列有多个结点Queue* Next = ps->phead->next;free(ps->phead);ps->phead = Next;}ps->size--;
}

6.取队头元素

    无需多言，队头指针指向的数据就是队头元素，直接返回即可

//取队头元素
TypeData QueueFront(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));return ps->phead->data;
}

7.取队尾元素

    无需多言，队尾指针指向的元素就是队尾元素，直接返回即可

//取队尾元素
TypeData QueueBack(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));return ps->ptail->data;
}

 8.队列的销毁

利用指针del指向要删除的结点，指针Next记录删除结点的下一个结点，当del为空时证明队列已经销毁，再将队列所有的指针置空，队列有效个数置0

//队列的销毁
void DestoryQueue(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));Node* del = ps->phead;while (del) {Queue* Next = del->next;free(del);del = Next;}ps->phead = ps->ptail = del = NULL;ps->size = 0;
}

9.获取队列的有效元素个数

    直接返回结构体成员变量size即可

TypeData QueueNums(Queue* ps) {return ps->size;
}

10.队列的全码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//队列的在链表的基础上实现，所以结构体有两个，一个是链表结点(头删尾插)
typedef int TypeData;//链表结点结构声明
typedef struct QueueNode {TypeData data;struct QueueNode* next;
}Node;typedef struct Queue {struct QueueNode* phead;struct QueueNode* ptail;int size;
}Queue;//队列初始化
void QueueInit(Queue* ps) {assert(ps);ps->phead = ps->ptail = NULL;ps->size = 0;
}//队列的入队，尾插
void QueuePush(Queue* ps, TypeData x) {//申请新结点Node* newNode = (Node*)malloc(sizeof(Node));if (newNode == NULL) {perror("malloc");exit(1);}newNode->data = x;newNode->next = NULL;//两种情况，队列为空与不为空if (ps->phead == NULL) {ps->phead = ps->ptail = newNode;}else {//队列不为空ps->ptail->next = newNode;ps->ptail = newNode;}ps->size++;
}//判断队列是否为空
bool QueueEmpty(Queue* ps) {//头节点为空证明队列为空return ps->phead == NULL;
}//队列出队，头删
void QueuePop(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));//如果队列只有一个结点if (ps->phead == ps->ptail) {free(ps->phead);ps->phead = ps->ptail = NULL;}else {//队列有多个结点Queue* Next = ps->phead->next;free(ps->phead);ps->phead = Next;}ps->size--;
}//取队头元素
TypeData QueueFront(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));return ps->phead->data;
}//取队尾元素
TypeData QueueBack(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));return ps->ptail->data;
}//队列的销毁
void DestoryQueue(Queue* ps) {assert(ps);assert(!QueueEmpty(ps));Node* del = ps->phead;while (del) {Queue* Next = del->next;free(del);del = Next;}ps->phead = ps->ptail = del = NULL;ps->size = 0;
}TypeData QueueNums(Queue* ps) {return ps->size;
}

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

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

GSLAM——一个通用的SLAM架构和基准

GSLAM——一个通用的SLAM架构和基准

GSLAM: A General SLAM Framework and Benchmark 开源地址 摘要&#xff1a; SLAM技术最近取得了许多成功&#xff0c;并吸引了高科技公司的关注。然而&#xff0c;如何同一现有或新兴算法的界面&#xff0c;一级有效地进行关于速度、稳健性和可移植性的基准测试仍然是问题。本…
阅读更多...
数据库-分库分表

数据库-分库分表

什么是分库分表 分库分表是一种数据库优化策略。 目的&#xff1a;为了解决由于单一的库表数据量过大而导致数据库性能降低的问题 分库&#xff1a;将原来独立的数据库拆分成若干数据库组成 分表&#xff1a;将原来的大表(存储近千万数据的表)拆分成若干个小表 什么时候考虑分…
阅读更多...
mybatis自定义类型处理器

mybatis自定义类型处理器

mybatis自定义类型处理器 其实使用MySQL或Oracle数据库很少会遇到自定义类型处理器的情况&#xff0c;之前是因为项目中使用了PGSQL才接触到这块的&#xff0c;这里简单做一下记录 要创建一个自定义的类型处理器&#xff0c;就需要继承BaseTypeHandler类或者实现TypeHandler接…
阅读更多...
深度学习--------------------------------使用注意力机制的seq2seq

深度学习--------------------------------使用注意力机制的seq2seq

目录 动机加入注意力Bahdanau注意力的架构 总结Bahdanau注意力代码带有注意力机制的解码器基本接口实现带有Bahdanau注意力的循环神经网络解码器测试Bahdanau注意力解码器该部分总代码 训练从零实现总代码简洁实现代码 将几个英语句子翻译成法语该部分总代码 将注意力权重序列进…
阅读更多...
CVSS 4.0 学习笔记

CVSS 4.0 学习笔记

通用漏洞评分系统（CVSS）捕获了主要技术软件、硬件和固件漏洞的特征。其输出包括数字分数，表明与其他漏洞。 以下因素可能包括但不限于：监管要求、客户数量受影响、因违约造成的金钱损失、生命或财产受到威胁，或潜在漏洞的声誉影响。这些因素在CVSS评估范围之外。 CVSS的好…
阅读更多...
基于PHP猫咖私人影院系统【附源码】

基于PHP猫咖私人影院系统【附源码】

效果如下&#xff1a; 系统首页界面 用户注册界面 包厢信息界面 零食信息界面 管理员登录界面 包厢预订界面 猫咪信息界面 研究背景 近年来&#xff0c;随着生活品质的提升和个性化消费需求的增长&#xff0c;猫咖和私人影院等新兴休闲娱乐方式逐渐受到年轻人的青睐。猫咖结合…
阅读更多...
招联金融校招内推2025

招联金融校招内推2025

【投递方式】 直接扫下方二维码&#xff0c;或点击内推官网https://wecruit.hotjob.cn/SU61025e262f9d247b98e0a2c2/mc/position/campus&#xff0c;使用内推码 igcefb 投递&#xff09; 【招聘岗位】 后台开发 前端开发 数据开发 数据运营 算法开发 技术运维 软件测试 产品策…
阅读更多...
复现文章：R语言复现文章画图

复现文章：R语言复现文章画图

文章目录 介绍数据和代码图1图2图6附图2附图3附图4附图5附图6 介绍 文章提供画图代码和数据&#xff0c;本文记录 数据和代码 数据可从以下链接下载&#xff08;画图所需要的所有数据&#xff09;&#xff1a; 百度云盘链接: https://pan.baidu.com/s/1peU1f8_TG2kUKXftkpYq…
阅读更多...
人机协作：科技与人类智慧的融合

人机协作：科技与人类智慧的融合

随着科技的飞速发展&#xff0c;越来越多的领域开始借助人工智能&#xff08;AI&#xff09;和自动化技术来提升工作效率。人机协作&#xff08;Human-Machine Collaboration&#xff09;这一概念逐渐成为现代技术进步的核心。它不仅改变了我们的工作方式&#xff0c;也在重新定…
阅读更多...
基于SpringBoot“花开富贵”花园管理系统【附源码】

基于SpringBoot“花开富贵”花园管理系统【附源码】

效果如下&#xff1a; 系统注册页面 系统首页界面 植物信息详细页面 后台登录界面 管理员主界面 植物分类管理界面 植物信息管理界面 园艺记录管理界面 研究背景 随着城市化进程的加快和人们生活质量的提升&#xff0c;越来越多的人开始追求与自然和谐共生的生活方式&#xf…
阅读更多...
基于YOLOv8-deepsort算法的智能车辆目标检测车辆跟踪和车辆计数

基于YOLOv8-deepsort算法的智能车辆目标检测车辆跟踪和车辆计数

关于深度实战社区 我们是一个深度学习领域的独立工作室。团队成员有&#xff1a;中科大硕士、纽约大学硕士、浙江大学硕士、华东理工博士等&#xff0c;曾在腾讯、百度、德勤等担任算法工程师/产品经理。全网20多万粉丝&#xff0c;拥有2篇国家级人工智能发明专利。 社区特色…
阅读更多...
中国当代哲学家思想家教育家颜廷利：真正问题意识体现在哪些方面

中国当代哲学家思想家教育家颜廷利：真正问题意识体现在哪些方面

在《升命学说》这部划时代的著作中&#xff0c;二十一世纪的杰出哲学家颜廷利教授提出了一个引人深思的观点。他巧妙地将阿拉伯数字“5”与汉字“吾”联系起来&#xff0c;指出两者发音相似&#xff0c;而“吾”字代表着自我。在儿童识字教学中&#xff0c;教师们常以创意的方式…
阅读更多...
Linux操作系统——概念扫盲I

Linux操作系统——概念扫盲I

目录 虚拟机概念刨析 在那之前&#xff0c;询问什么是虚拟化&#xff1f; 现在来看看什么是虚拟机 虚拟机有啥好的 小差&#xff1a;那JVM也叫Java Virtual Machine&#xff0c;有啥区别呢&#xff1f; Reference 虚拟机概念刨析 我们下面来简单聊聊虚拟机这个概念。对于…
阅读更多...
物联网开发者必读：从HTTP到MQTT，八大协议全解码！

物联网开发者必读：从HTTP到MQTT，八大协议全解码！

我是小米，一个喜欢分享技术的29岁程序员。如果你喜欢我的文章，欢迎关注我的微信公众号“软件求生”，获取更多技术干货！ Hello 大家好，我是小米，一个喜欢研究和分享技术的IT宅。今天咱们聊点不一样的——物联网（IoT）中的各种协议！最近在研究IoT的过程中，我发现物联网领…
阅读更多...
基于ssm vue uniapp实现的爱心小屋公益机构智慧管理系统

基于ssm vue uniapp实现的爱心小屋公益机构智慧管理系统

博主介绍&#xff1a;专注于Java&#xff08;springboot ssm 等开发框架&#xff09; vue .net php phython node.js uniapp 微信小程序 等诸多技术领域和毕业项目实战、企业信息化系统建设&#xff0c;从业十五余年开发设计教学工作☆☆☆ 精彩专栏推荐订阅☆☆☆☆☆不然…
阅读更多...
基于PHP的校园二手书交易管理系统

基于PHP的校园二手书交易管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的校园二手书交易管理系统 一 介绍 此二手书交易管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。系统角色分为用户和管理员。 技术栈&#xff1a;phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注…
阅读更多...
窗口系统与图形绘制接口

窗口系统与图形绘制接口

个人博客:Sekyoro的博客小屋 个人网站:Proanimer的个人网站 当我们想要进行底层图形应用(GUI)开发时,往往需要用到窗口系统和图形库,这里简单介绍一下 视窗系统(window system)与通信协议 下面内容主要针对Unix-like操作系统 视窗系统是以使用视窗作为主要特征之一的图形用…
阅读更多...
设计模式01-类图及设计原理(Java)

设计模式01-类图及设计原理(Java)

一、设计模式综述 1.设计模式基本概念 设计模式&#xff08;Design Pattern&#xff09;是前辈们对代码开发经验的总结&#xff0c;是解决特定问题的一系列套路。它不是语法规定&#xff0c;而是一套用来提高代码可复用性、可维护性、可读性、稳健性以及安全性的解决方案。 …
阅读更多...
Linux 系统成为隐秘“Perfctl”加密挖矿恶意软件的目标

Linux 系统成为隐秘“Perfctl”加密挖矿恶意软件的目标

Aqua Security 的研究人员上周透露&#xff0c;数以千计的 Linux 系统可能感染了极难追踪且持久的“perfctl”&#xff08;或“ perfcc ”&#xff09;加密挖掘恶意软件&#xff0c;许多其他系统仍然面临被入侵的风险。 在观察到的所有攻击中&#xff0c;恶意软件都被用来运行…
阅读更多...
C++ 非STL数据结构学习——1.4 图

C++ 非STL数据结构学习——1.4 图

一般而言&#xff0c;图的实现有邻接矩阵和邻接表两种。 1. 邻接矩阵 #include <iostream> #include <vector>class Graph { private:int V; // 顶点数量std::vector<std::vector<int>> adjMatrix; // 邻接矩阵std::vector<bool> visited; // 记…
阅读更多...
最新文章

Copyright @ 2022~2023