数据结构与算法——详谈栈和队列

目录

一：栈

1.1：栈的概念结构与实现

1.1.1：栈的概念结构

1.1.2：栈的实现

1.2：栈的各个功能实现

1.2.1：对栈进行初始化

1.2.2：判空栈

1.2.3：入栈

1.2.4：出栈

1.2.5：获取栈顶元素

1.2.6：获取栈内元素个数

1.2.7；销毁栈

1.3：栈的源代码

1.3.1：Stack _Func.h 代码实现

1.3.2：Stack _Func.c 代码实现

1.3.3：Stack _Main.c 代码实现

二：队列

2.1：队列的概念结构与实现

2.1.1：队列的概念及结构

2.2.2：队列的实现

2.2：队列的各个功能实现

2.2.1：初始化队列

2.2.2：队列进行判空

2.2.3：入对（对队列进行插入数据）

2.2.4：出队（删除队列元素）

2.2.5：获取队头元素

2.2.6：获取队尾元素

2.2.7：获取队列内元素个数

2.2.8：销毁队列

2.3：队列实现的源代码

2.3.1：Queue_Func.h 代码实现

2.3.2：Queue_Func.c 代码实现

2.3.3：Queue_Main.c 代码实现

一：栈

1.1：栈的概念结构与实现

1.1.1：栈的概念结构

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

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。
出栈：栈的删除操作叫做出栈。出数据也在栈顶。 

形象数据演示入栈/出栈过程：

1.1.2：栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

数组的结构实现： 

并且在实际应用中，我们一般主要实现支持动态增长的栈：

// 实现一个栈
typedef int STDatatype;
typedef struct Stack
{STDatatype* a;int top;			// 栈顶int capacity;		// 容量
}ST;

1.2：栈的各个功能实现

1.2.1：对栈进行初始化

因为栈是使用数组来实现的，所以在对栈进行操作之前必须要先对栈进行初始化（此处将栈顶的初始值置为0）。

1.2.2：判空栈

当栈顶top==0时，该函数返回true，否则返回false。

1.2.3：入栈

因为栈是由数组来实现的，所以当数据进行入栈的时候一定要对栈的容量进行检查。当容量满的时候需要进行扩容。

1.2.4：出栈

1.2.5：获取栈顶元素

因为栈顶原本初始值为0，即先放入数据后，top++。所以获取栈顶元素时获取的是top-1的位置的数据。

1.2.6：获取栈内元素个数

1.2.7；销毁栈

1.3：栈的源代码

1.3.1：Stack _Func.h 代码实现

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>// 实现一个栈
typedef int STDatatype;
typedef struct Stack
{STDatatype* a;int top;			// 栈顶int capacity;		// 容量
}ST;// 初始化栈
void ST_Init(ST* pst);// 判空
bool ST_Empty(ST* pst);// 入栈
void ST_Push(ST* pst, STDatatype x);// 出栈
void ST_Pop(ST* pst);// 获取栈顶元素
STDatatype ST_Top(ST* pst);// 获取栈内元素个数
int ST_Size(ST* pst);// 销毁栈
void ST_Destroy(ST* pst);

1.3.2：Stack _Func.c 代码实现

#include"Stack_Func.h"// 初始化栈
void ST_Init(ST* pst)
{pst->a = NULL;pst->capacity = 0;pst->top = 0;
}// 判空
bool ST_Empty(ST* pst)
{return pst->top == 0;
}// 入栈
void ST_Push(ST* pst, STDatatype x)
{// 增容if (pst->capacity == pst->top){int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;STDatatype* tmp = (STDatatype*)realloc(pst->a, sizeof(STDatatype) * newcapacity);if (tmp == NULL){perror("ST_Push realloc fail");return;}pst->a = tmp;pst->capacity = newcapacity;}// 入栈pst->a[pst->top] = x;pst->top++;
}// 出栈
void ST_Pop(ST* pst)
{assert(!ST_Empty(pst));pst->top--;
}// 获取栈顶元素
STDatatype ST_Top(ST* pst)
{assert(!ST_Empty(pst));return pst->a[pst->top - 1];
}// 获取栈内元素个数
int ST_Size(ST* pst)
{return pst->top;
}// 销毁栈
void ST_Destroy(ST* pst)
{free(pst->a);pst->a = NULL;pst->capacity = pst->top = 0;
}

1.3.3：Stack _Main.c 代码实现

#include"Stack_Func.h"int main()
{ST st;// 初始化栈ST_Init(&st);// 入栈ST_Push(&st, 1);ST_Push(&st, 2);ST_Push(&st, 3);ST_Push(&st, 4);ST_Push(&st, 11);ST_Push(&st, 33);ST_Push(&st, 22);ST_Push(&st, 55);printf("栈内元素个数： = > %d\n", ST_Size(&st));while (!ST_Empty(&st)){printf("%d ", ST_Top(&st));ST_Pop(&st);}printf("\n");ST_Destroy(&st);}

运行结果：

二：队列

2.1：队列的概念结构与实现

2.1.1：队列的概念及结构

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

入队列：进行插入操作的一端称为队尾。

出队列：进行删除操作的一端称为队头。

 队列结构：

2.2.2：队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

队列实现情况：

所以对于描述一个队列，就可以这样：

// 实现一个队列
typedef int QEDatatype;// 队列结点
typedef struct QENode
{QEDatatype data;struct QENode* next;
}QENode;// 队列
typedef struct Queue
{QENode* phead;    // 指向队头的指针QENode* ptail;    // 指向队尾的指针int size;         // 描述队列内元素个数
}QE;

2.2：队列的各个功能实现

2.2.1：初始化队列

在没有操作队列时，队列的头指针和尾指针都应置为NULL，且size = 0。

2.2.2：队列进行判空

2.2.3：入对（对队列进行插入数据）

因为每次入队入的都是一个队列结点，所以入队之前应malloc出一个结点用来入队。并且入队时只能在队尾进行入队。入队后将队尾指针指向该队列新插入的一个结点（队尾结点）。

2.2.4：出队（删除队列元素）

出队之前要先对队列进行判空处理，然后将队头指针指向其下一个结点（注意：当该队列只有一个数据进行出队操作时，应将队头指针和队尾指针同时置为NULL）。

2.2.5：获取队头元素

2.2.6：获取队尾元素

2.2.7：获取队列内元素个数

2.2.8：销毁队列

2.3：队列实现的源代码

2.3.1：Queue_Func.h 代码实现

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>// 实现一个队列
typedef int QEDatatype;typedef struct QENode
{QEDatatype data;struct QENode* next;
}QENode;typedef struct Queue
{QENode* phead;QENode* ptail;int size;
}QE;// 判空
bool QE_Empty(QE* pqe);// 初始化队列
void QE_Init(QE* pqe);// 入队
void QE_Push(QE* pqe, QEDatatype x);// 出队
void QE_Pop(QE* pqe);// 获取队头元素
QEDatatype QE_Head(QE* pqe);// 获取队尾元素
QEDatatype QE_Tail(QE* pqe);// 获取队列元素个数
int QE_Size(QE* pqe);// 销毁队列
void QE_Destroy(QE* pqe);

2.3.2：Queue_Func.c 代码实现

#include"Queue_Func.h"// 判空
bool QE_Empty(QE* pqe)
{return pqe->size == 0;
}// 初始化队列
void QE_Init(QE* pqe)
{pqe->phead = pqe->ptail = NULL;pqe->size = 0;
}// 获取一个队列结点
QENode* Buy_Node(QEDatatype x)
{QENode* newnode = (QENode*)malloc(sizeof(QENode));if (newnode == NULL){perror("Buy_Node malloc fail");return NULL;}newnode->data = x;newnode->next = NULL;return newnode;
}// 入队
void QE_Push(QE* pqe, QEDatatype x)
{QENode* newnode = Buy_Node(x);if (QE_Empty(pqe)){pqe->phead = pqe->ptail = newnode;}else{pqe->ptail->next = newnode;pqe->ptail = newnode;}pqe->size++;
}// 出队
void QE_Pop(QE* pqe)
{assert(!QE_Empty(pqe));QENode* cur = pqe->phead;if (pqe->phead == pqe->ptail){pqe->phead = pqe->ptail = NULL;}else{pqe->phead = cur->next;}free(cur);pqe->size--;
}// 获取队头元素
QEDatatype QE_Head(QE* pqe)
{assert(!QE_Empty(pqe));return pqe->phead->data;
}// 获取队尾元素
QEDatatype QE_Tail(QE* pqe)
{assert(!QE_Empty(pqe));return pqe->ptail->data;
}// 获取队列元素个数
int QE_Size(QE* pqe)
{return pqe->size;
}// 销毁队列
void QE_Destroy(QE* pqe)
{QENode* cur = pqe->phead;while (cur != pqe->ptail){QENode* curnext = cur->next;free(cur);cur = curnext;}free(cur);pqe->phead = pqe->ptail = NULL;pqe->size = 0;
}

2.3.3：Queue_Main.c 代码实现

#include"Queue_Func.h"int main()
{QE qn;// 初始化队列QE_Init(&qn);// 插入数据QE_Push(&qn, 1);QE_Push(&qn, 2);QE_Push(&qn, 3);QE_Push(&qn, 4);QE_Push(&qn, 5);QE_Push(&qn, 6);QE_Push(&qn, 7);QE_Push(&qn, 8);printf("数据元素个数：=> %d\n", QE_Size(&qn));while (!QE_Empty(&qn)){printf("%d ", QE_Head(&qn));QE_Pop(&qn);}// 销毁队列QE_Destroy(&qn);}

运行结果：

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

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

相关文章

一文读懂AI安全治理框架

一文读懂AI安全治理框架

随着AI的发展以及研究&#xff0c;我们总会提到AI带来的一些潜在威胁&#xff0c;但截止目前我还没有完全的梳理过AI到底有哪些潜在的风险&#xff0c;今天就来一一看一下&#xff01;陆续补齐。
阅读更多...
自动化中验证码的操作笔记，懂的赶紧收藏！

自动化中验证码的操作笔记，懂的赶紧收藏！

在自动化测试的过程中&#xff0c;验证码一直被视为一个“拦路虎”。很多测试人员在做接口或UI自动化时都会遇到验证码的阻碍&#xff0c;导致测试无法继续进行。今天&#xff0c;我们就来讨论如何在自动化过程中破解验证码&#xff0c;快速绕过这道关卡&#xff0c;轻松完成自…
阅读更多...
LVM硬盘挂载

LVM硬盘挂载

LVM硬盘挂载 一、基础概念 sda/sdb/nvme0n1/nvme0n2&#xff1a; 硬盘的命名方式&#xff0c;中括号的字母为第三位按不同硬盘的加载顺序排序。sda1/sda2/sdb1&#xff1a; 第4位为分区号&#xff0c;数字为不同分区的依序命名lvm: LVM是一种逻辑卷管理器&#xff0c;允许管理…
阅读更多...
黑马头条day1 环境搭建 SpringCloud微服务（注册发现，服务调用，网关）

黑马头条day1 环境搭建 SpringCloud微服务（注册发现，服务调用，网关）

Nacos 环境搭建 Vmvare打开已经安装好的虚拟机镜像环境 使用findshell作为链接工具 和MobaXterm差不多 初始工程搭建 项目导入到idea 里边 这个项目都是用的比较老的东西 jdk1.8 甚至把仓库也提供好了 主体机构 common 就是通用的配置 feign 是对外的接口 model …
阅读更多...
css五种定位总结

css五种定位总结

在 CSS 中&#xff0c;定位&#xff08;Positioning&#xff09;主要有五种模式&#xff0c;每种模式的行为和特点不同&#xff0c;以下是 static、relative、absolute、fixed 和 sticky 五种定位方式的对比总结&#xff1a; 1. static&#xff08;默认定位&#xff09; 特性…
阅读更多...
“中秋快乐”文字横幅的MATLAB代码生成

“中秋快乐”文字横幅的MATLAB代码生成

中秋快乐呀朋友们&#xff01;&#xff01;&#xff01; 给大家带来一个好玩的代码&#xff0c;能够生成“中秋快乐”的横幅文字&#xff0c;比较简单&#xff0c;当然你也可以根据自己的需求去更改文字和背景&#xff0c;废话不多说&#xff0c;直接展示。 文字会一直闪烁&…
阅读更多...
计算机毕业设计 基于SpringBoot框架的网上蛋糕销售系统的设计与实现 Java实战项目 附源码+文档+视频讲解

计算机毕业设计 基于SpringBoot框架的网上蛋糕销售系统的设计与实现 Java实战项目 附源码+文档+视频讲解

博主介绍&#xff1a;✌从事软件开发10年之余&#xff0c;专注于Java技术领域、Python人工智能及数据挖掘、小程序项目开发和Android项目开发等。CSDN、掘金、华为云、InfoQ、阿里云等平台优质作者✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精…
阅读更多...
基于Springboot+vue的音乐网站

基于Springboot+vue的音乐网站

随着信息技术在管理上越来越深入而广泛的应用&#xff0c;管理信息系统的实施在技术上已逐步成熟。本文介绍了音乐网站的开发全过程。通过分析音乐网站管理的不足&#xff0c;创建了一个计算机管理音乐网站的方案。文章介绍了音乐网站的系统分析部分&#xff0c;包括可行性分析…
阅读更多...
如何在Mac上安装多个Python环境

如何在Mac上安装多个Python环境

如何在Mac上安装多个Python环境 简介 在你的Mac上使用多个Python环境可以对项目管理很有帮助，特别是在同时处理不同Python版本或不同的包需求时。在这篇文章中，我们将向你展示如何在Mac上轻松地安装和管理多个Python环境。 一. 安装Conda Conda是一个包管理和环境管理系统…
阅读更多...
深度学习 之 常见损失函数简介：名称、作用及用法

深度学习 之 常见损失函数简介：名称、作用及用法

引言 在机器学习和深度学习中&#xff0c;损失函数&#xff08;Loss Function&#xff09;是模型训练过程中一个不可或缺的部分。它用来度量模型预测结果与真实值之间的差异&#xff0c;从而指导模型参数的优化。合理选择损失函数对于提高模型的准确性和泛化能力至关重要。本文…
阅读更多...
代码随想录训练营第36天|二维背包

代码随想录训练营第36天|二维背包

1049. 最后一块石头的重量 II class Solution { public:int lastStoneWeightII(vector<int>& stones) {int sumaccumulate(stones.begin(),stones.end(),0);int targetsum/2;vector<int> dp(target1,0);for(auto& stone: stones){for(int itarget; i>s…
阅读更多...
Ansible——Playbook基本功能

Ansible——Playbook基本功能

文章目录 一、Ansible Playbook介绍1、Playbook的简单组成1&#xff09;“play”2&#xff09;“task”3&#xff09;“playbook” 2、Playbook与ad-hoc简单对比区别联系 3、YAML文件语法&#xff1a;1. 基本结构2. 数据类型3. 列表4. 字典&#xff08;映射&#xff09;5. 注释…
阅读更多...
免费表格图片识别成表格小工具

免费表格图片识别成表格小工具

自动提取图片中的文字&#xff0c;并按照表格的格式整理好 需要的自取吧&#xff0c;下载地址&#xff1a;https://pan.quark.cn/s/f4b1ac62b808
阅读更多...
问题：博途与kepserver通讯，kepserver读取变量数为啥对不上呢

问题：博途与kepserver通讯，kepserver读取变量数为啥对不上呢

回答&#xff1a; 1500中该变量为浮点数&#xff0c;在kepserver选择成DWORD当DINT显示了&#xff0c;将数据类型设成与1500一致。 #PLC##西门子工业支持中心##西门子##博途#工控人加入PLC工业自动化精英社群
阅读更多...
C#图像爬虫实战：从Walmart网站下载图片

C#图像爬虫实战：从Walmart网站下载图片

无论是电子商务网站、社交媒体平台还是新闻门户&#xff0c;图像都扮演着至关重要的角色。对于开发者来说&#xff0c;能够自动化地从这些网站下载图片是一项非常有用的技能。本文将介绍如何使用C#语言和CsQuery库来创建一个图像爬虫&#xff0c;专门用于从Walmart网站下载图片…
阅读更多...
牛客周赛 Round 59(思维、构造、数论)

牛客周赛 Round 59(思维、构造、数论)

文章目录 牛客周赛 Round 59(思维、构造、数论)A. TDB. 你好&#xff0c;这里是牛客竞赛C. 逆序数&#xff08;思维&#xff09;D. 构造mex&#xff08;构造&#xff09;E. 小红的X型矩阵F. 小红的数组回文值&#xff08;数论、范德蒙恒等式&#xff09; 牛客周赛 Round 59(思维…
阅读更多...
数字IC设计\FPGA 职位经典笔试面试整理--语法篇 Verilog System Verilog(部分)

数字IC设计\FPGA 职位经典笔试面试整理--语法篇 Verilog System Verilog(部分)

注&#xff1a; 资料都是基于网上一些博客分享和自己学习整理而成的 Verilog 1. 数据类型 Verilog一共有19种数据类型 基础四种数据类型&#xff1a;reg型&#xff0c;wire型&#xff0c;integer型&#xff0c;parameter型 reg型   reg类型是寄存器数据类型的关键字。寄存…
阅读更多...
新手学习Python第十一天，准备今天全部学完系列

新手学习Python第十一天，准备今天全部学完系列

——早上07&#xff1a;30到达实验室&#xff0c;开始学习&#xff0c;中秋小长假已过&#xff0c;心已收—— 一、__new__与__init__创建对象的过程 class Person(object):def __new__(cls,*args,**kwargs): *表示位置参数&#xff0c;**表示关键字参数print(__new__被调用…
阅读更多...
快来尝尝，超赞的食家巷一窝丝

快来尝尝，超赞的食家巷一窝丝

一窝丝&#xff0c;这个名字听起来就充满了诗意和神秘。当你第一次见到它时&#xff0c;定会被它那精致的外形所吸引。纤细如丝&#xff0c;盘绕在一起&#xff0c;宛如一个精美的艺术品。那丝丝缕缕&#xff0c;散发着淡淡的麦香味&#xff0c;仿佛在诉说着古老的故事。 制作食…
阅读更多...
Imagen论文简要解析

Imagen论文简要解析

Imagen论文简要解析 文章 Photorealistic Text-to-Image Diffusion Models with Deep Language Understanding 具有深度语言理解能力的逼真文本到图像扩散模型 https://arxiv.org/pdf/2205.11487 摘要 文章介绍了一种名为Imagen的文本到图像扩散模型&#xff0c;该模型在理…
阅读更多...
最新文章

Copyright @ 2022~2023