栈与队列的故事

​​​​​​​


目录

​编辑​​​​​​​

一、栈

1.1栈的概念及结构

1.2栈的实现

1、实现支持动态增长的栈

2、初始化栈

3、入栈

4、出栈

5、获取栈顶元素

6、检测栈是否为空

7、获取栈中有效元素个数

8、销毁栈

9、测试

1.3源码

二、队列

2.1队列的概念及结构

2.2队列的实现

1、链式结构:表示队列

2、队列的结构

3、初始化队列

4、队尾入队列

5、队头出队列

6、获取队列队头元素

7、获取队列队尾元素

8、获取队列中有效元素个数

9、检测队列是否为空

10、销毁队列

11、测试

2.3源码


一、栈

1.1栈的概念及结构

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

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

1.2栈的实现

栈的实现一般可以使用数组或者链表实现:

  • 对于链表而言又有双向链表和单链表,如果用双向链表实现,栈顶既可以是尾,也可以是头。如果用单链表实现,栈顶只能是头,因为单链表尾插容易,尾删却比较麻烦;而头插头删都很容易。
  • 相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

1、实现支持动态增长的栈

typedef int STDataType;

typedef struct stack
{
	STDataType* arr;
	int top;      //栈顶
	int capacity; //容量
}ST;

2、初始化栈

因为这个结构体肯定不可能为空,所以我们直接先断言它。然后,这里还有一个要特别注意的点,如果我们初始化时top给0,那top指向的就是栈顶元素的下一个位置;如果top给-1,那top就指向栈顶元素

void STInit(ST* pst)
{
	assert(pst);

	pst->arr = NULL;
	pst->capacity = 0;

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

3、入栈

入栈时如果空间不够,先扩容;因为top此时是指向栈顶元素的下一个位置,所以我们直接将要入栈的元素x放在top位置,然后让top指向下一个位置就行。

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->arr, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->arr = tmp;
		pst->capacity = newcapacity;
	}

	pst->arr[pst->top] = x;
	pst->top++;

    //如果top初始化时为-1,入栈时就要top先++,再将元素放进去
	//pst->top++;
	//pst->arr[pst->top] = x;
}

4、出栈

在出栈时要注意如果top为0就不能在删除了,所以要断言一下。

void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);

	pst->top--;
}

5、获取栈顶元素

因为top是指向栈顶元素的下一个位置,所以要获取栈顶元素只需要top-1就行。

STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);

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

6、检测栈是否为空

如果栈为空,那top就等于0,表达式的结果就为真;如果表达式的结果为假,就代表栈不为空。

bool STEmpty(ST* pst)
{
	assert(pst);

	return pst->top == 0;
}

7、获取栈中有效元素个数

int STSize(ST* pst)
{
	assert(pst);

	return pst->top;
}

8、销毁栈

void STDestroy(ST* pst)
{
	assert(pst);

	free(pst->arr);
	pst->arr = NULL;

	pst->top = pst->capacity = 0;
}

9、测试

int main()
{
	ST s;
	STInit(&s);
	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);
	STPush(&s, 4);
	STPush(&s, 5);
	while (!STEmpty(&s))
	{
		printf("%d ", STTop(&s));
		STPop(&s);
	}
	printf("\n");
	STDestroy(&s);

	return 0;
}

1.3源码

🌻Stack.h

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>


typedef int STDataType;

typedef struct stack
{
	STDataType* arr;
	int top;      //栈顶
	int capacity; //容量
}ST;

//初始化
void STInit(ST* pst);
//销毁栈
void STDestroy(ST* pst);
//入栈
void STPush(ST* pst, STDataType x);
//出栈
void STPop(ST* pst);
//获取栈顶元素
STDataType STTop(ST* pst);
//检测栈是否为空,如果为空,返回真;如果不为空,返回假
bool STEmpty(ST* pst);
//获取栈中有效元素个数
int STSize(ST* pst);

🌻Stack.c

#include "stack.h"

//初始化
void STInit(ST* pst)
{
	assert(pst);

	pst->arr = NULL;
	pst->capacity = 0;

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

    //表示top指向栈顶元素
	//pst->top = -1;
}

//销毁栈
void STDestroy(ST* pst)
{
	assert(pst);

	free(pst->arr);
	pst->arr = NULL;

	pst->top = pst->capacity = 0;
}

//入栈
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->arr, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->arr = tmp;
		pst->capacity = newcapacity;
	}
    
    //如果top初始化时为0,入栈时就要先将元素放进去,再将top++
	pst->arr[pst->top] = x;
	pst->top++;

	//如果top初始化时为-1,入栈时就要top先++,再将元素放进去
	//pst->top++;
	//pst->arr[pst->top] = x;
}

//出栈
void STPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);

	pst->top--;
}

//获取栈顶元素
STDataType STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);

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

//检测栈是否为空,如果为空,返回真;如果不为空,返回假
bool STEmpty(ST* pst)
{
	assert(pst);

	return pst->top == 0;
}

//获取栈中有效元素个数
int STSize(ST* pst)
{
	assert(pst);

	return pst->top;
}

二、队列

2.1队列的概念及结构

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

  • 入队列:进行插入操作的一端称为队尾
  • 出队列:进行删除操作的一端称为队头

2.2队列的实现

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

1、链式结构:表示队列

typedef int QDataType;

//链式结构:表示队列
typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;

2、队列的结构

因为队列需要队头和队尾两个指针,所以为了方便管理,我们可以把它俩放在一个结构体里边。

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

3、初始化队列

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

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

4、队尾入队列

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

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

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

5、队头出队列

出队时得考虑两种情况,一种是队列为空,另一种是队列中只有一个节点;如果队列为空,我们只需断言一下就行。如果队列中只有一个节点,我们先保存当前节点,然后让头指针指向下一个节点,接着free掉保存的节点,这时如果头指针是指向空的,我们就把尾指针也置空。

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

	QNode* del = pq->phead;
	pq->phead = pq->phead->next;
	free(del);
	del = NULL;

	if (pq->phead == NULL)
	{
		pq->ptail = NULL;
	}

    pq->size--;
}

6、获取队列队头元素

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

	return pq->phead->val;
}

7、获取队列队尾元素

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

	return pq->ptail->val;
}

8、获取队列中有效元素个数

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

	return pq->size;
}

9、检测队列是否为空

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

	return pq->phead == NULL;
}

10、销毁队列

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;
}

11、测试

int main()
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);
	while (!QueueEmpty(&q))
	{
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");
	QueueDestroy(&q);
	return 0;
}

2.3源码

🌻Queue.h

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int QDataType;

//链式结构:表示队列
typedef struct QueueNode
{
	QDataType val;
	struct QueueNode* next;
}QNode;

//队列的结构
typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

//初始化队列
void QueueInit(Queue* pq);
//队尾入队列
void QueuePush(Queue* pq, QDataType x);
//队头出队列
void QueuePop(Queue* pq);
//获取队列队头元素
QDataType QueueFront(Queue* pq);
//获取队列队尾元素
QDataType QueueBack(Queue* pq);
//获取队列中有效元素个数
int QueueSize(Queue* pq);
//检测队列是否为空
bool QueueEmpty(Queue* pq);
//销毁队列
void QueueDestroy(Queue* pq);

🌻Queue.c

#include "queue.h"

//初始化队列
void QueueInit(Queue* pq)
{
	assert(pq);

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

//队尾入队列
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);

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

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

//队头出队列
void QueuePop(Queue* pq)
{
	assert(pq);
	//空
	assert(pq->phead);

	QNode* del = pq->phead;
	pq->phead = pq->phead->next;
	free(del);
	del = NULL;

	if (pq->phead == NULL)
	{
		pq->ptail = NULL;
	}

	pq->size--;
}

//获取队列队头元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	//空
	assert(pq->phead);

	return pq->phead->val;
}

//获取队列队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	//空
	assert(pq->ptail);

	return pq->ptail->val;
}

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

	return pq->size;
}

//检测队列是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->phead == NULL;
}

//销毁队列
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/446217.html

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

相关文章

【AI辅助研发】-开端:未来的编程范式

编程的四种范式 面向机器编程范式 面向机器编程范式是最原始的编程方式&#xff0c;它直接针对计算机硬件进行操作。程序员需要了解计算机的内部结构、指令集和内存管理等细节。在这种范式下&#xff0c;编程的主要目标是编写能够直接控制计算机硬件运行的机器代码。面向机器…

Babel:现代JavaScript的桥梁

&#x1f90d; 前端开发工程师、技术日更博主、已过CET6 &#x1f368; 阿珊和她的猫_CSDN博客专家、23年度博客之星前端领域TOP1 &#x1f560; 牛客高级专题作者、打造专栏《前端面试必备》 、《2024面试高频手撕题》 &#x1f35a; 蓝桥云课签约作者、上架课程《Vue.js 和 E…

【Prometheus】PromQL

数据类型 即时向量&#xff08;instant vector&#xff09; node_cpu_seconds_total{instance"ahoj-dev-ubuntu-virtualbox",mode"idle"} 区间向量&#xff08;range vector&#xff09; node_cpu_seconds_total{instance"ahoj-dev-ubuntu-virtu…

java正则表达式概述及案例

前言&#xff1a; 学习了正则表达式&#xff0c;记录下使用心得。打好基础&#xff0c;daydayup! 正则表达式 什么是正则表达式 正则表达式由一些特定的字符组成&#xff0c;代表一个规则。 正则表达式的功能 1&#xff1a;用来校验数据格式是否合规 2&#xff1a;在一段文本…

针对娃哈哈和农夫山泉,AI是如何看待的

娃哈哈和农夫山泉事件是中国饮料行业的两个重要事件。娃哈哈和农夫山泉都是中国知名的饮料品牌&#xff0c;两者之间的竞争一直存在。以下是对这两个事件的介绍&#xff1a; 1. 娃哈哈事件&#xff1a;娃哈哈是中国最大的饮料生产企业之一&#xff0c;也是中国最具影响力的品牌…

.Net6使用JWT认证和授权

文章目录 目的实现案例一.项目所需包&#xff1a;二.配置项目 appsettings.json 文件&#xff1a;三.创建Model文件夹&#xff0c;添加AppConfig类和UserRole类1.AppConfig类获取appsettings.json文件中的值2.UserRole类用于区分用户信息和权限 四.主体代码案例&#xff1a;1.L…

C++的类与对象(三):构造函数、析构函数、对象的销毁顺序

目录 类的6个默认成员函数 构造函数 语法 特性 析构函数 特性 对象的销毁顺序​​​​​​​​​​​​​​ 类的6个默认成员函数 问题&#xff1a;一个什么成员都没的类叫做空类&#xff0c;空类中真的什么都没有吗&#xff1f; 基本概念&#xff1a;任何类在什么都不…

[MRCTF2020]Transform1

a[33]"9,10,15,23,7,24,12,6,1,16,3,17,32,29,11,30,27,22,4,13,19,20,21,2,25,5,31,8,18,26,28,14" b[33]"103,121,123,127,117,43,60,82,83,121,87,94,93,66,123,45,42,102,66,126,76,87,121,65,107,126,101,60,92,69,111,98,77" python代码 a3 [103…

three.js 射线Ray,三维空间中绘制线框

效果&#xff1a; 代码&#xff1a; <template><div><el-container><el-main><div class"box-card-left"><div id"threejs"></div> <div>{{ res1 }}</div> <div>{{ res2 }}</div><…

一图看懂Redis持久化机制!

持久化策略 Redis 提供了两种持久化策略&#xff1a; RDB (Redis Database Snapshot) 持久化机制&#xff0c;会在一段时间内生成指定时间点的数据集快照(snapshot) AOF&#xff08;Append Only File&#xff09; 持久化机制&#xff0c;记录 server 端收到的每一条写命令&am…

nmcli绑定bond双网卡(active-backup模式)

安装包 apt-get install network-manager apt install net-tools当前网卡mac地址IP都不一样 创建名为“jbl”的新连接&#xff0c;并将其模式设置为“active-backup” nmcli connection add type bond ifname jbl mode active-backup添加物理网卡到bond(JBL),两个物理网卡添加…

linux操作系统虚拟机的环境配置

目录 一、虚拟机安装&#xff08;类似硬件的安装&#xff09; &#xff08;1&#xff09;创建虚拟机 &#xff08;2&#xff09;创建虚拟机 二、IP和主机名称配置 1、设置VM上的IP 2、设置我们电脑上VMnet8的IP 3、设置虚拟机上的IP 主机名称映射 以下是设置主机名映射…

【异常处理】sbt构建Chisel库时出现extracting structure failed:build status:error的解决办法

文章目录 报错背景&#xff1a;解决思路&#xff1a;①IDEA中配置本地的SBT进行下载②更改下载源为华为的镜像站1. 修改sbtconfig.txt2. 增加repositories文件 ③查看报错信息 总结整理的Scala-Chisel-Chiseltest版本信息对应表 报错背景&#xff1a; 最近在写Chisel时&#x…

JavaScript基础5之作用域、执行上下文的顺序执行、可执行代码、执行上下文栈

JavaScript基础 作用域思考 执行上下文顺序执行可执行代码执行上下文栈案例一案例二case1:case2 作用域 作用域&#xff1a;程序源代码中定义变量的区域。作用域规定了如何查找变量&#xff0c;也就是确定当前执行代码对变量的访问权限。作用域分类&#xff1a;静态作用域&…

哈希表|242.有效的字母异位词

力扣题目链接 bool isAnagram(char* s, char* t) {int len_s strlen(s), len_t strlen(t);if(len_s ! len_t) {return false;}int table[26];memset(table, 0, sizeof(table));for(int i 0; i < len_s; i) {table[s[i] - a];}for(int i 0; i < len_t; i) {table[t[i…

二,几何相交---4,BO算法---(1)接近性和可分离性

提了三个观点 1&#xff0c;如果一条直线&#xff08;比如竖直&#xff09;可以分开两个线段&#xff0c;则这两个线段不相交 2&#xff0c;只需要观察与隔离线相交的几个线段 3&#xff0c;从左向右扫描线只需要观察每个线段的两个端点和一些可能的相交点。

2024年【化工自动化控制仪表】新版试题及化工自动化控制仪表考试试题

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 化工自动化控制仪表新版试题是安全生产模拟考试一点通总题库中生成的一套化工自动化控制仪表考试试题&#xff0c;安全生产模拟考试一点通上化工自动化控制仪表作业手机同步练习。2024年【化工自动化控制仪表】新版试…

Qt 中Json文件的操作

Json文件的读取 QFile file("data.json"); //准备好的文件file.open(QIODevice::ReadOnly|QIODevice::Text);QByteArray arr file.readAll();QJsonDocument jsonDoc QJsonDocument::fromJson(arr);QJsonObject jsonObj jsonDoc.object();qint32 id jsonObj["…

沁恒蓝牙芯片CH582:蓝牙OTA升级技术详解与应用探索

文章目录 一、前言1.WCH 蓝牙空中升级&#xff08;BLE OTA&#xff09;概述2. WCH BLE SDK DFU 工作原理&#xff08;方式一&#xff09; 二、移植程序1.找到BackUpgrade_OTA例程2.添加文件到工程2.1 添加文件2.2 如何添加 3.修改APP工程3.1 修改peripheral_main.c文件3.2 修改…

Leetcode 59.螺旋矩阵Ⅱ

1.题目 2.思路 &#xff08;借用代码随想录的图&#xff09; 1.我们将转一圈看作一个循环&#xff08;1->2->3->4->5->6->7->8 这是一个循环&#xff09; 2.在这个循环里&#xff0c;我们要画四条边&#xff08;上右下左&#xff09; 填充上行从左到右 填…