【数据结构】——栈|队列（基本功能）

目录

栈

基本概念

栈的常见基本操作 

栈的存储

 ✌栈的基本操作实现

栈的构建

栈的初始化 

入栈

打印栈 

出栈

获取栈顶元素

 获取栈的有效元素个数

判断栈是否为空

 销毁栈

 队列

基本概念

队列的常见基本操作

✌队列的基本操作实现

队列的构建

初始化

入队列

出队列

 获取头部元素

获取队尾元素

获取有效元素个数

判断是否为空

销毁队列

栈

基本概念

定义： 是只允许在一端进行插入或删除的线性表；

栈顶：线性表允许进行插入删除的那一端。
空栈：不含任何元素的空表。 

栈是先进后出的的线性表

栈的常见基本操作 

InitStack(&S)：           初始化一个空栈S。
StackEmpty(S)：        判断一个栈是否为空，若栈为空则返回true，否则返回false。
Push(&S, x)：             进栈（栈的插入操作），若栈S未满，则将x加入使之成为新栈顶。
Pop(&S, &x)：            出栈（栈的删除操作），若栈S非空，则弹出栈顶元素，并用x返回。
GetTop(S, &x)：         读栈顶元素，若栈S非空，则用x返回栈顶元素。
DestroyStack(&S)：    栈销毁，并释放S占用的存储空间（“&”表示引用调用）。

栈的存储

 栈的存储方式有两种：顺序栈和链栈，即栈的顺序存储和链式存储。

采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的元素，同时附设一个指针（top）指示当前栈顶的位置。

 ✌栈的基本操作实现

栈的构建

因为使用的是顺序栈，所以可以定义动态增长的数组，既然是数组了，自然有空间是否足够的问题，所以要定义个容量 capacity，栈顶top

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType* arr;	
	int top;		// 栈顶
	int capacity;  // 容量 
}Stack;

栈的初始化 

 这里的top可以定义成0或者-1，不过后面的操作需要稍微变化；

// 初始化栈 
void StackInit(Stack* ps)
{
	assert(ps);
	assert(ps);
	ps->arr = NULL;
	ps->capacity = 0;
	ps->top = -1;	//表示栈顶元素
}

入栈

这里注意top的不同，因为是顺序栈，所以要检查容量是否足够

// 入栈 
void StackPush(Stack* ps, STDataType data)
{
	//检查容量
	if (ps->top + 1 == ps->capacity)	//top表示的是栈顶元素，先++top,再插入的，所以检查+1位置是否可用
	{
		int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
		STDataType* newnode = (STDataType*)realloc(ps->arr,sizeof(STDataType) * newcapacity);
		assert(newnode);	//七匹狼式检查是否开辟成功
		ps->arr = newnode;
		ps->capacity = newcapacity;
	}
	ps->top++;
	ps->arr[ps->top] = data;
}

打印栈 

//打印
void StackPrint(Stack* ps)
{
	assert(ps);
	int i = ps->top;
	while (i>=0)
	{
		printf("%d ", ps->arr[i]);
		i--;
	}
	printf("\n");
}

出栈

// 出栈 
void StackPop(Stack* ps)
{
	assert(ps);
	assert(ps->top >= 0);
	ps->top--;
}

获取栈顶元素

// 获取栈顶元素 
STDataType StackTop(Stack* ps)
{
	assert(ps);
	assert(ps->top >= 0);
	return ps->arr[ps->top];
}

 获取栈的有效元素个数

// 获取栈中有效元素个数 
int StackSize(Stack* ps)
{
	assert(ps);
	assert(ps->top >= 0);
	return ps->top + 1;
}

判断栈是否为空

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
bool StackEmpty(Stack* ps)
{
	assert(ps);
	if (ps->top < 0)	//为空
	{
		return true;
	}
	else
	{
		return false;
	}
}

 销毁栈

// 销毁栈 
void StackDestroy(Stack* ps)
{
	assert(ps);
	ps->capacity = 0;
	ps->top = -1;
	free(ps->arr);
	ps->arr = NULL;
}

 队列

基本概念

定义：队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。

队列是一种先进先出（First In First Out）的线性表，简称FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。

队列的常见基本操作

InitQueue(&Q)：           初始化队列，构造一个空队列Q。
QueueEmpty(Q)：        判队列空，若队列Q为空返回true，否则返回false。
EnQueue(&Q, x)：       入队，若队列Q未满，将x加入，使之成为新的队尾。
DeQueue(&Q, &x)：     出队，若队列Q非空，删除队头元素，并用x返回。
GetHead(Q, &x)：        读队头元素，若队列Q非空，则将队头元素赋值给x。

✌队列的基本操作实现

队列的构建

typedef int QueueDataType;
// 链式结构：表示队列 
typedef struct QueueNode
{
	QueueDataType val;
	struct QueueNode* next;
}QNode;

// 队列的结构 
typedef struct Queue
{
	QNode* head;
	QNode* tail;
	int size;	//队列的长度大小
}Queue;

初始化

// 初始化队列 
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->head = NULL;
	pq->tail = NULL;
	pq->size = 0;
}

入队列

// 队尾入队列 
void QueuePush(Queue* pq, QueueDataType data)
{
	assert(pq);
	//开辟空间
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)	//检查是否开辟成功
	{
		perror("malloc fail");
		return;
	}
	newnode->val = data;
	newnode->next = NULL;

	if (pq->tail == NULL)	//空队列情况
	{
		pq->tail = pq->head = newnode;	
	}
	else
	{
		pq->tail->next = newnode;	//链接新结点
		pq->tail = newnode;		//队尾 更新位置
	}
	pq->size++;		//长度+
}

出队列

// 队头出队列 
void QueuePop(Queue* pq)
{
	assert(pq);
	QNode* tmp = pq->head;
	pq->head = pq->head->next;

	free(tmp);
	tmp = NULL;

	if (pq->head == NULL) //此时链表已经为空，队尾tail是野指针
	{
		pq->tail = NULL;
	}
	pq->size--;
}

 获取头部元素

// 获取队列头部元素 
QueueDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->head);	//检查队头，不为空说明有数据存放
	return pq->head->val;
}

获取队尾元素

// 获取队列队尾元素 
QueueDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->tail);	//检查队尾，不为空说明有数据存放
	return pq->tail->val;
}

获取有效元素个数

// 获取队列中有效元素个数 
int QueueSize(Queue* pq)
{
	assert(pq);
	return pq->size;
}

判断是否为空

// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(Queue* pq)
{
	assert(pq);
	return pq->head == NULL;
}

销毁队列

// 销毁队列 
void QueueDestroy(Queue* pq)
{
	assert(pq);
	QNode* tmp = pq->head;
	while (tmp)
	{
		QNode* next = tmp->next;
		free(tmp);
		tmp = NULL;
		tmp = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

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

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

相关文章

不再只是android，华为自爆Harmony将对标iOS

不再只是android，华为自爆Harmony将对标iOS

今年10月&#xff0c;华为官方宣布&#xff0c;鸿蒙OS 4升级设备数量已突破1亿&#xff0c;成为史上升级最快的鸿蒙OS版本。 日前&#xff0c;据数码博主“定焦数码”消息&#xff0c;大厂技术员工做适配&#xff0c;通过线下沟通时&#xff0c;华为反复提到一个问题&#xff…
阅读更多...
实战技巧：为Android应用设置独立的多语言

实战技巧：为Android应用设置独立的多语言

原文链接 实战技巧&#xff1a;为Android应用设置独立的多语言 通常情况下多语言的设置都在系统设置中&#xff0c;应用需要做的就是提供本应用所使用的字串的多语言翻译&#xff0c;使用时使用R.string.app_name类似的引用&#xff0c;然后系统会根据用户在系统设置中的选项来…
阅读更多...
不瞒各位，不安装软件也能操作Xmind文档

不瞒各位，不安装软件也能操作Xmind文档

大家好&#xff0c;我是小悟 作为搞技术的一个人群&#xff0c;时不时就要接收产品经理发过来的思维脑图&#xff0c;而此类文档往往是以Xmind编写的&#xff0c;如果你的电脑里面没有安装Xmind的话&#xff0c;不好意思&#xff0c;是打不开这类后缀结尾的文档。 打不开的话…
阅读更多...
【雷电模拟器桥接问题解决方法】

【雷电模拟器桥接问题解决方法】

1.ROOT权限开启 2.开启网络桥接模式&#xff0c;选择静态IP设置&#xff0c;点击安装桥接网卡&#xff0c;填写IP地址&#xff08;注意&#xff1a;IP地址要与host主机在同一IP段内&#xff09; 3.重启后 adb shell就能进入到模拟器控制台中了&#xff0c;如果出现以下内容&…
阅读更多...
进程程序替换和shell实现

进程程序替换和shell实现

先前fork说创建子进程执行代码&#xff0c;如何让子进程执行和父进程完全不一样的代码?程序替换。 一 单进程替换演示 1 execl函数使用 最近转到在vs code下写代码&#xff0c;之前也在xhell下用过execl函数&#xff0c;所以才想写篇博客总结总结&#xff0c;没想到在vs code…
阅读更多...
（C语言）计算n的阶乘

（C语言）计算n的阶乘

要求使用双精度 #include<stdio.h> double factorial(int n) {if(n 1)return 1;return n * factorial(n-1); } int main() {int n ;double res;scanf("%d",&n);res factorial(n);printf("%lf",res); return 0; } 运行截图&#xff1a; 注&am…
阅读更多...
oops-framework框架 之 界面管理(三)

oops-framework框架 之 界面管理(三)

引擎&#xff1a; CocosCreator 3.8.0 环境&#xff1a; Mac Gitee: oops-game-kit 注&#xff1a; 作者dgflash的oops-framework框架QQ群&#xff1a; 628575875 回顾 在上文中主要通过oops-game-kit大家了一个新的模版项目&#xff0c; 主要注意项是resources目录下的两个文…
阅读更多...
Python Opencv实践 - Yolov3目标检测

Python Opencv实践 - Yolov3目标检测

本文使用CPU来做运算&#xff0c;未使用GPU。练习项目&#xff0c;参考了网上部分资料。 如果要用TensorFlow做检测&#xff0c;可以参考这里 使用GPU运行基于pytorch的yolov3代码的准备工作_little han的博客-CSDN博客文章浏览阅读943次。记录一下自己刚拿到带独显的电脑&a…
阅读更多...
卷积神经网络（CNN）：艺术作品识别

卷积神经网络（CNN）：艺术作品识别

文章目录 一、前言一、设置GPU二、导入数据1. 导入数据2. 检查数据3. 配置数据集4. 数据可视化 三、构建模型四、编译五、训练模型六、评估模型1. Accuracy与Loss图2. 混淆矩阵3. 各项指标评估 一、前言 我的环境&#xff1a; 语言环境&#xff1a;Python3.6.5编译器&#xf…
阅读更多...
继承 多态 拆箱装箱 128陷阱 枚举类

继承 多态 拆箱装箱 128陷阱 枚举类

继承 在java里一个类只能继承一个类&#xff0c;但可以被多个类继承&#xff1b;c里一个类可以继承多个类&#xff1b; 子类可以使用父类的方法&#xff1b; 在java中&#xff0c;Object是所有类的父类&#xff1b; equals方法比较的是对象是否指向同一个地方&#xff0c;这个方…
阅读更多...
原生横向滚动条 吸附 页面底部

原生横向滚动条 吸附 页面底部

效果图 /** 横向滚动条 吸附 页面底部 */ export class StickyHorizontalScrollBar {constructor(options {}) {const { el, style } optionsthis.createScrollbar(style)this.insertScrollbar(el)this.setScrollbarSize()this.onEvent()}/** 创建滚轴组件元素 */createS…
阅读更多...
Windows下打包C++程序无法执行：无法定位程序输入点于动态链接库

Windows下打包C++程序无法执行：无法定位程序输入点于动态链接库

1、问题描述 环境&#xff1a;CLionCMakeMinGW64遇到问题&#xff1a;打包的exe无法运行&#xff0c;提示无法定位程序输入点于动态链接库。 2、解决思路 ​ 通过注释头文件的方式&#xff0c;初步定位问题是因为使用了#include <thread> 多线程库引起的。而且exe文件…
阅读更多...
外包干了2个月，技术倒退2年。。。。。

外包干了2个月，技术倒退2年。。。。。

先说一下自己的情况&#xff0c;本科生&#xff0c;20年通过校招进入深圳某软件公司&#xff0c;干了接近4年的功能测试&#xff0c;今年国庆&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测试…
阅读更多...
如何创建maven项目的多模块项目

如何创建maven项目的多模块项目

Maven多模块项目是指一个Maven项目中包含多个子模块&#xff0c;每个子模块又是一个独立的Maven项目&#xff0c;但它们之间可以存在依赖关系。Maven多模块项目可以方便地管理多个子模块的依赖和构建过程&#xff0c;同时也可以提高项目的可维护性和可扩展性。创建maven项目的父…
阅读更多...
ChatGPT发布一年后，搜索引擎的日子还好吗？

ChatGPT发布一年后，搜索引擎的日子还好吗？

导读&#xff1a;生成式AI&#xff0c;搜索引擎的终结者还是进化加速器 ChatGPT发布刚刚一年&#xff0c;互联网世界已经换了人间。 2023年&#xff0c;以ChatGPT和大模型为代表的生成式AI浪潮对全球互联网、云计算、人工智能领域都带来巨大冲击。而且生成式AI在各行各业的应用…
阅读更多...
深入理解JVM虚拟机第二十七篇：详解JVM当中InvokeDynamic字节码指令，Java是动态类型语言么？

深入理解JVM虚拟机第二十七篇：详解JVM当中InvokeDynamic字节码指令，Java是动态类型语言么？

😉😉 学习交流群： ✅✅1：这是孙哥suns给大家的福利！ ✨✨2：我们免费分享Netty、Dubbo、k8s、Mybatis、Spring...应用和源码级别的视频资料 🥭🥭3：QQ群：583783824 📚📚 工作微信：BigTreeJava 拉你进微信群，免费领取！ 🍎🍎4：本文章内容出自上述：Sp…
阅读更多...
[ROS2] --- ROS diff ROS2

[ROS2] --- ROS diff ROS2

1 ROS存在的问题 一旦Ros Master主节点挂掉后&#xff0c;就会造成整个系统通信的异常,通信基于TCP实现&#xff0c;实时性差、系统开销大对Python3支持不友好&#xff0c;需要重新编译消息机制不兼容没有加密机制、安全性不高 2 ROS and ROS2架构对比 ROS和ROS2架构如下图所…
阅读更多...
Redis实战篇笔记（最终篇）

Redis实战篇笔记（最终篇）

Redis实战篇笔记&#xff08;七&#xff09; 文章目录 Redis实战篇笔记&#xff08;七&#xff09;前言达人探店发布和查看探店笔记点赞点赞排行榜 好友关注关注和取关共同关注关注推送关注推荐的实现 总结 前言 本系列文章是Redis实战篇笔记的最后一篇&#xff0c;那么到这里…
阅读更多...
如何使用cpolar内网穿透工具实现公网SSH远程访问Deepin

如何使用cpolar内网穿透工具实现公网SSH远程访问Deepin

文章目录 前言1. 开启SSH服务2. Deppin安装Cpolar3. 配置ssh公网地址4. 公网远程SSH连接5. 固定连接SSH公网地址6. SSH固定地址连接测试 前言 Deepin操作系统是一个基于Debian的Linux操作系统&#xff0c;专注于使用者对日常办公、学习、生活和娱乐的操作体验的极致&#xff0…
阅读更多...
卷积神经网络（CNN）：乳腺癌识别.ipynb

卷积神经网络（CNN）：乳腺癌识别.ipynb

文章目录 一、前言一、设置GPU二、导入数据1. 导入数据2. 检查数据3. 配置数据集4. 数据可视化 三、构建模型四、编译五、训练模型六、评估模型1. Accuracy与Loss图2. 混淆矩阵3. 各项指标评估 一、前言 我的环境&#xff1a; 语言环境&#xff1a;Python3.6.5编译器&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023