【数据结构（C语言）】浅谈栈和队列

目录

文章目录

前言

一、栈

1.1 栈的概念及结构

1.2 栈的实现

1.2.1. 支持动态增长的栈的结构

1.2.2 初始化栈

1.2.3 入栈

1.2.4 出栈

1.2.5 获取栈顶元素

1.2.6 获取栈中有效元素个数

1.2.7 检查栈是否为空

1.2.8 销毁栈

二、队列

2.1 队列的概念及结构

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.2.9 销毁队列

总结

一、栈

1.1 栈的概念及结构

栈（Stack）是一种线性数据结构，它可以看作是一种特殊的列表。栈只能在一端进行插入和删除操作，这一端被称为栈顶（Top）。栈按照后进先出（LIFO, Last In First Out）的原则进行操作，即最后一个进栈的元素最先被弹出。栈可以用数组或链表实现。栈的主要操作包括压栈（进栈/入栈）（Push）和弹栈（出栈）（Pop），还有取栈顶元素（Top）和判断栈是否为空（Empty）等。栈在编程中常用于函数调用、表达式求值、括号匹配等场景。

1.2 栈的实现

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。所以我们这里使用数组实现栈。用数组实现也分为静态的和动态的，静态的实际中一般不实用，所以我们实现动态的。

1.2.1. 支持动态增长的栈的结构

这里我们声明一个结构体，一个成员为指针a，用来存放开辟空间的首地址（即动态数组），一个成员top用来存放栈顶位置，还有一个成员capacity用来存放开辟的空间大小，方便数组扩容。

代码如下：

typedef int StDataType;

typedef struct Stack
{
	StDataType* a;
	int top;		// 标识栈顶位置的
	int capacity;
}St;

1.2.2 初始化栈

将结构体中的指针a赋值为NULL，将capacity赋值为0，将top赋值为0，表示top指向栈顶元素的下一个位置（也可以赋值为-1，表示top指向栈顶元素，这里我们使用第一种）。

代码如下：

void StInit(St* pst)
{
	assert(pst);

	pst->a = NULL;
	pst->capacity = 0;
	//表示top指向栈顶元素的下一个位置
	pst->top = 0;

	//表示top指向栈顶元素，如果为-1，后面的代码也要改
	//pst->top = -1;
}

1.2.3 入栈

入栈之前要先判断开辟的空间满了没，如果满了，可以使用realloc（）函数重新分配数组大小，然后再将元素插入top所指向的位置，最后将top+1。

代码如下：

void StPush(St* pst, StDataType x)
{
	assert(pst);

	if (pst->top == pst->capacity)
	{
		int newCapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;
		StDataType* tmp = (StDataType*)realloc(pst->a, newCapacity * sizeof(StDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		pst->a = tmp;
		pst->capacity = newCapacity;
	}

	pst->a[pst->top] = x;
	pst->top++;
}

1.2.4 出栈

先要确保栈中有元素，可以使用断言，如果有，则只需要top-1就行。

代码如下：

void StPop(St* pst)
{
	assert(pst);
	assert(pst->top > 0);

	pst->top--;
}

1.2.5 获取栈顶元素

先确保栈中有元素，然后直接返回top-1所指向位置的元素即可。

代码如下：

StDataType StTop(St* pst)
{
	assert(pst);
	assert(pst->top > 0);

	return pst->a[pst->top - 1];
}

1.2.6 获取栈中有效元素个数

因为top指向栈顶元素的下一个位置，其大小刚好为元素的个数，所以直接返回top即可。

代码如下：

int StSize(St* pst)
{
	assert(pst);

	return pst->top;
}

1.2.7 检查栈是否为空

判断top是否为0，为0即为空。

代码如下：

bool StEmpty(St* pst)
{
	assert(pst);

	return pst->top == 0;
}

1.2.8 销毁栈

先将动态分配的内存释放了，再将结构体中的成员赋值为初始化栈时所赋值的值就行。

代码如下：

void StDestroy(St* pst)
{
	assert(pst);

	free(pst->a);
	pst->a = NULL;
	pst->top = 0;
	pst->capacity = 0;
}

二、队列

2.1 队列的概念及结构

队列（Queue）是一种遵循先进先出（First In First Out，FIFO）原则的数据结构，即最先插入队列的元素最先被取出。队列具有两个端点，一个是队头（Head），一个是队尾（Tail），入队操作（enqueue）在队尾进行，出队操作（dequeue）在队头进行。队列的应用领域很广，例如实现任务调度、消息传递、缓冲区等。常见队列的实现包括：单向队列、双向队列和循环队列等。我们这里主要讨论单向队列。

2.2 队列的实现

我们这里实现的是最基础的单向队列，双向队列和循环队列各位读者可另行了解。队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低（因为要整体把元素往前移，时间复杂度为O(n)，虽然在算法中用数组模拟实现队列可以使用头尾双指针使时间复杂度变成O(1),但这样做出队的同时也把空间浪费了）。

2.2.1 队列的结构

因为使用链表实现队列，所以先声明一个队列的结点的结构体，其成员跟链表的声明一致，有两个成员，一个为数据val，另一个为next指针。然后为了后面实现的方便，再声明一个队列结构体，其成员包括队头指针phead和队尾指针ptail以及一个记录队列大小的整形size。

代码如下：

typedef int QDataType;

typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

2.2.2 初始化队列

将队头指针phead和队尾指针ptail赋值为NULL，将size赋值为0。

代码如下：

void QueueInit(Queue* pq)
{
	assert(pq);

	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

2.2.3 入队

先动态申请一个新结点，将要入队的元素赋给新结点的val，再将新结点的next指针指向NULL。然后判断这个队列是否为空，如果为空，则将队头指针phead和队尾指针ptail都指向新结点；如果不为空，则只要改变队尾指针ptail就行，即先将队尾指针ptail指向的结点的next指针指向新结点，再将队尾指针ptail指向新结点。最后将size+1就行了。

代码如下：

void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

	QNode* newNode = (QNode*)malloc(sizeof(QNode));
	if (newNode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newNode->val = x;
	newNode->next = NULL;

	if (pq->phead == NULL)
	{
		pq->phead = pq->ptail = newNode;
	}
	else
	{
		pq->ptail->next = newNode;
		pq->ptail = newNode;
	}
	
	pq->size++;
}

2.2.4 出队

先要确保队列中有结点，可以使用断言。然后再判断队列中是否只有一个结点，如果是，则释放这个结点后，要将队头指针phead和队尾指针ptail都指向NULL；如果不是，则只需要将队头指针phead指向它所指向的结点的下一个结点，并将它原来所指向的结点释放就行。最后将size-1。

代码如下：

void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->phead);

	if (pq->phead == pq->ptail)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QNode* tmp = pq->phead;
		pq->phead = pq->phead->next;
		free(tmp);
	}

	pq->size--;
}

2.2.5 获取队头元素

先确保队列有结点，再返回队头指针phead所指向的结点的值val。

代码如下：

QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead);

	return pq->phead->val;
}

2.2.6 获取队尾元素

先确保队列有结点，再返回队尾指针ptail所指向的结点的值val。

代码如下：

QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->ptail);

	return pq->ptail->val;
}

2.2.7 获取队列中有效元素个数

直接返回size。

代码如下：

int QueueSize(Queue* pq)
{
	assert(pq);

	return pq->size;
}

2.2.8 检查队列是否为空

判断队头指针phead是否为NULL。

代码如下：

bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->phead == NULL;
}

2.2.9 销毁队列

先遍历释放队列中的每一个结点，再将队列结构体中的成员赋值为初始化队列时所赋值的值就行。

代码如下：

void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}

	pq->phead = pq->ptail = NULL;
	pq->size = 0;
}

总结

以上就是关于栈和队列的基本概念和操作。通过这篇文章，希望大家能够更好地理解关于栈和队列的原理和实现，并在实际编程中灵活运用它们。

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

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

相关文章

[BJDCTF2020]The mystery of ip1

[BJDCTF2020]The mystery of ip1

提示 ssti模板注入head头x-forwarded-for 每一次做题的最开始流程都大致因该是 信息收集找可以操控的地方 查看hint页面的源代码又发现它提示说 ####你知道为什么会知道你的ip吗 查看flag页面 从刚才给我的提示以及他这里显示的我的ip，大概找到了我可操作的可控点 …
阅读更多...
Spark---基于Yarn模式提交任务

Spark---基于Yarn模式提交任务

Yarn模式两种提交任务方式 一、yarn-client提交任务方式 1、提交命令 ./spark-submit --master yarn --class org.apache.spark.examples.SparkPi ../examples/jars/spark-examples_2.11-2.3.1.jar 100 或者 ./spark-submit --master yarn–client --class org.apache.s…
阅读更多...
学习.NET验证模块FluentValidation的基本用法（续1：其它常见用法）

学习.NET验证模块FluentValidation的基本用法（续1：其它常见用法）

FluentValidation模块支持链式验证方法调用，也就是说，除了 RuleFor(r > r.UserName).NotEmpty()调用方式之外，还可以将对单个属性的多种验证函数以链式调用方式串接起来，比如UserName属性不能为空，长度在5~10之间&a…
阅读更多...
北京数字孪生赋能工业制造，加速推进制造业数字化转型

北京数字孪生赋能工业制造，加速推进制造业数字化转型

随着新一代信息技术与实体经济深度融合进程的加快，企业数字化转型需求的提升，政策的持续支持，数字孪生将为工业制造、未来生活带来无限的可能。在制造业数字化大变革时代，以5G、大数据、物联网、人工智能等为代表的工业4.0&#x…
阅读更多...
职场Excel：求和家族，不简单

职场Excel：求和家族，不简单

说到excel函数，很多人第一时间想到的就是求和函数sum。作为excel入门级函数，sum的确是小白级的，以至于很多人对求和函数有点“误解”，觉得求和函数太简单了。 但是，你可能不知道，sum只是excel求和家族里的一…
阅读更多...
二叉树的顺序结构及实现

二叉树的顺序结构及实现

目录 1 二叉树的顺序结构2. 堆的概念及结构3 .堆的实现(小堆) 1 二叉树的顺序结构 普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，…
阅读更多...
1.测试基础

1.测试基础

目录 一、测试基础 1.软件测试中基础信息定义 2.测试主流技能 3.常见的测试分类 3.1按阶段划分 3.2按代码可见度划分 3.3其他 4.测试模型 5.测试流程 6.测试用例 二、用例设计方法 2.1等价类 2.2 边界值 2.3判定表法 2.4场景法 2.5错误推测法 三、缺陷管理 1…
阅读更多...
HTB Codify WriteUp

HTB Codify WriteUp

Codify 2023年11月7日 20:59:48user nmap ➜ Codify nmap -A 10.10.11.239 Starting Nmap 7.80 ( https://nmap.org ) at 2023-11-07 21:00 CST Nmap scan report for bogon (10.10.11.239) Host is up (0.14s latency). Not shown: 997 closed ports PORT STATE SERVI…
阅读更多...
Centos上安装Docker和DockerCompose

Centos上安装Docker和DockerCompose

安装Docker Docker可以运行在MAC，Windows，CtenOS,UBUNTU等操作系统上。目前主流的版本有Docker CE和Docker EE，CE是免费的开源Docker版本，适用于开发人员和小型团队，EE是适用于企业的容器化解决方案。它基于Docker CE…
阅读更多...
Linux进程通信——信号（一）

Linux进程通信——信号（一）

原理 对于 Linux来说，实际信号是软中断，许多重要的程序都需要处理信号。 信号，为 Linux 提供了一种处理异步事件的方法。比如，终端用户输入了ctrlc来中断程序，会通过信号机制停止一个程序。 概述 信号的名字和编号 …
阅读更多...
如何实现在公网下使用navicat图形化工具远程连接本地内网的MariaDB数据库

如何实现在公网下使用navicat图形化工具远程连接本地内网的MariaDB数据库

公网远程连接MariaDB数据库【cpolar内网穿透】 文章目录 公网远程连接MariaDB数据库【cpolar内网穿透】1. 配置MariaDB数据库1.1 安装MariaDB数据库1.2 测试局域网内远程连接 2. 内网穿透2.1 创建隧道映射2.2 测试随机地址公网远程访问3. 配置固定TCP端口地址3.1 保留一个固定的…
阅读更多...
京东数据分析（京东大数据）：2023年10月京东手机行业品牌销售排行榜

京东数据分析（京东大数据）：2023年10月京东手机行业品牌销售排行榜

鲸参谋监测的京东平台10月份手机市场销售数据已出炉！ 根据鲸参谋平台的数据显示，今年10月份，京东平台手机行业的销量约340万，环比增长约11%，同比则下滑约2%；销售额为108亿，环比增长约17%&#x…
阅读更多...
MAV3D：从文本描述中生成三维动态场景

MAV3D：从文本描述中生成三维动态场景

Singer U, Sheynin S, Polyak A, et al. Text-to-4d dynamic scene generation[J]. arXiv preprint arXiv:2301.11280, 2023. MAV3D 是 Meta AI 研究者们提出的一种从文本描述生成三维动态场景的方法。从所提供的文本生成的动态视频输出可以从任何摄像机位置和角度查看&#xf…
阅读更多...
2023亚太杯数学建模C题思路代码 - 我国新能源电动汽车的发展趋势

2023亚太杯数学建模C题思路代码 - 我国新能源电动汽车的发展趋势

1 赛题 问题C 我国新能源电动汽车的发展趋势 新能源汽车是指以先进技术原理、新技术、新结构的非常规汽车燃料为动力来源( 非常规汽车燃料指汽油、柴油以外的燃料），将先进技术进行汽车动力控制和驱动相结 合的汽车。新能源汽车主要包括四种类型&#x…
阅读更多...
嵌入式系统在工业自动化中的应用

嵌入式系统在工业自动化中的应用

嵌入式系统在工业自动化中的应用非常广泛，它们通过集成控制和实时响应能力，实现了生产线的自动化、智能化和高效化。以下将详细介绍嵌入式系统在工业自动化中的几个重要应用领域，并提供一些示例代码。 1. PLC（可编程逻辑控制器&a…
阅读更多...
思维模型 潘多拉效应

思维模型 潘多拉效应

本系列文章 主要是 分享 思维模型 ，涉及各个领域，重在提升认知。越是禁止，越是好奇。 1 潘多拉效应的应用 1.1 潘多拉效应在管理中的应用 通用电气公司曾经推出了一项名为“六西格玛”的管理方法，该方法旨在通过优化业务流程和提…
阅读更多...
leetcode 343.整数拆分 198.打家劫舍（动态规划）

leetcode 343.整数拆分 198.打家劫舍（动态规划）

OJ链接 &#xff1a;leetcode 343.整数拆分 代码&#xff1a; class Solution {public int integerBreak(int n) {int[] dp new int[n1];//每个n&#xff0c;拆分多个整数乘积的最大值dp [0] 0;dp [1] 1; for(int i 2 ; i<n; i){for(int j 0 ; j < i; j){dp[i] Ma…
阅读更多...
【开源】基于Vue.js的天然气工程运维系统的设计和实现

【开源】基于Vue.js的天然气工程运维系统的设计和实现

项目编号&#xff1a; S 022 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S022&#xff0c;文末获取源码。} 项目编号&#xff1a;S022&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 系统角色分类2.2 核心功能2.2.1 流程…
阅读更多...
【Java】初识JDBC

【Java】初识JDBC

&#x1f33a;个人主页&#xff1a;Dawn黎明开始 &#x1f380;系列专栏&#xff1a;Java ⭐每日一句&#xff1a;向阳而生&#xff0c;逐光而行 &#x1f4e2;欢迎大家&#xff1a;关注&#x1f50d;点赞&#x1f44d;评论&#x1f4dd;收藏⭐️ 文章目录 &#x1f4cb;前言 …
阅读更多...
Springmvc实现增删改差

Springmvc实现增删改差

一、包结构 二、各层代码 (1)数据User public class User {private Integer id;private String userName;private String note;public User() {super();}public User(Integer i, String userName, String note) {super();this.id i;this.userName userName;this.note note;…
阅读更多...
最新文章

Copyright @ 2022~2023