数据结构栈和堆列

目录

栈：

栈的概念：

栈的实现：

栈接口的实现：

1.初始化栈：

2.入栈：

3.出栈：

4. 获取栈顶元素：

5.获取栈中有效数据的个数：

 6.检测栈是否为空，如果为空返回非零结果，如果不为空返回0：

 7.销毁栈：

队列：

队列的概念：

队列的实现：

接口的实现：

1.初始化队列：

2. 队尾入队列：

3.队头出队列：

4.获取队列头部元素：

 5.获取队列尾元素：

6.获取队列中有效数据个数：

7.检测队列是否为空，如果为空返回非零结果，如果非空返回0：

8.销毁队列：

栈：

栈的概念：

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

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

栈的实现：

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

C语言单链表-CSDN博客  C语言实现顺序表(增,删,改,查)-CSDN博客 0基础小白学C语言看这一篇就够了(C语言详讲万字！！！)_用c++设计一个程序,实现输入任意一个数(不大于10的5次方),计算从1加到这个数-CSDN博客

栈接口的实现：

栈和顺序表一样，可以做成动态的也可以做成静态的，因为静态的一般是用在那种给定长度的地方，所以这里使用动态的实现栈。

实现之前我们需要各个文件，分别是头文件"Stack.h"，以及两个源文件"Stack.c"和"Test.c"，他们的作用如下:

  • Stack.h：栈的结构体，头文件引用，接口函数的声明。
  • Stack.c：接口函数的实现。
  • Test.c：测试各个函数的功能。

如下我们先来展示各种接口的声明Stack.h：

#pragma once

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

typedef int STDataType;
typedef struct Stack {
	STDataType*a;
	int top;
	int capacity;
}ST;

void STInit(ST* ps);
void STDestroy(ST* ps);
void STPush(ST*ps,STDataType x);
void STPop(ST* ps);
STDataType STTop(ST* ps);

int STSize(ST* ps);
bool STEmpty(ST* ps);
1.初始化栈：

把传递进来的第一个栈的置空和值为0

void STInit(ST* ps) {
	assert(ps);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
2.入栈：

入栈之前判断栈的大小是否足够，如果足够那么直接将数据存入对应的位置然后有效值++就行，如果空间不够那么需要扩容，如果扩容失败直接报错误信息。

void STPush(ST* ps, STDataType x) {
	assert(ps);
	if (ps->top==ps->capacity) {
		int newCapacity = ps->capacity * 2 == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp==NULL) {
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = x;
	ps -> top++;
}
3.出栈：

首先断言以下以免出现栈都没有还在出栈，然后有效数据减减就行了。

void STPop(ST* ps) {
	assert(ps);
	assert(ps->top > 0);
	--ps->top;
}
4. 获取栈顶元素：

直接返回数据没啥好说的。

STDataType STTop(ST* ps) {
	assert(ps);
	assert(ps->top > 0);
	return  ps->a[ps->top - 1];
}
5.获取栈中有效数据的个数：

直接返回栈顶元素。

int STSize(ST* ps) {
	assert(ps);
	return ps->top;
}
 6.检测栈是否为空，如果为空返回非零结果，如果不为空返回0：

返回类型是一个布尔型也就是不是false就是true。

bool STEmpty(ST* ps) {
	assert(ps);
	return ps->top == 0;
}
 7.销毁栈：

把栈释放之后然后把指针置空，值值为0.

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

如下是全代码的示例Stack.c:

#include"Stack.h"

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

void STPush(ST* ps, STDataType x) {
	assert(ps);
	if (ps->top==ps->capacity) {
		int newCapacity = ps->capacity * 2 == 0 ? 4 : ps->capacity * 2;
		STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);
		if (tmp==NULL) {
			perror("realloc fail");
			exit(-1);
		}
		ps->a = tmp;
		ps->capacity = newCapacity;
	}
	ps->a[ps->top] = x;
	ps -> top++;
}

void STPop(ST* ps) {
	assert(ps);
	assert(ps->top > 0);
	--ps->top;
}
STDataType STTop(ST* ps) {
	assert(ps);
	assert(ps->top > 0);
	return  ps->a[ps->top - 1];
}
int STSize(ST* ps) {
	assert(ps);
	return ps->top;
}
bool STEmpty(ST* ps) {
	assert(ps);
	return ps->top == 0;
}

如下我们用Test.c文件测试整个代码运行是否正常:

#include"Stack.h"

void TestStack1() {
	ST st;
	STInit(&st);
	STPush(&st, 1);
	STPush(&st, 2);
	STPush(&st, 3);
	STPush(&st, 4);
	STPush(&st, 5);

	while (!STEmpty(&st)) {
		printf("%d ",STTop(&st));
		STPop(&st);
	}
	printf("\n"); 

	STDestroy(&st);
}
int main() {
	TestStack1();
	return 0;
}

队列：

队列的概念：

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

队列的实现：

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

接口的实现：

我们首先创建一个头文件"Queue.h"和两个源文件分别是"Queue.c"跟"Test.c"，他们的作用为:

  • Queue.h:头文件的引用接口函数的声明，以及栈的结构体。
  • Queue.c:接口的实现。
  • Test.c：测试每个接口。

如下代码是Queue.h中所有接口以及头文件引用的代码：

#pragma once

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

typedef int QDataType;
typedef struct QueueNode {
	struct QueueNode* next;
	QDataType data;
}QNode;

typedef struct Queue {
	QNode* head;
	QNode* tail;
	int size;
}Que;


void QueueInit(Que* pq);
void QueueDestroy(Que* pq);
void QueuePush(Que*pq,QDataType x);
void QueuePop(Que* pq);
QDataType QueueFront(Que* pq);
QDataType QueueBack(Que* pq);
bool QueueEmpty(Que* pq);
int QueueSize(Que* p);
1.初始化队列：

把拿到的头指针和尾指针置空，然后把其值置为0...

void QueueInit(Que* pq) {
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}
2. 队尾入队列：

先使用malloc创建出一个队列，然后判断创建是否成功，如若成功执行下列代码，首先把指针置空然后给数据赋值，最后判断一下是第几个元素如果是第一个那么直接让头指针和尾指针都指向它即可，如果不是那么需要改变尾指针的指向，然后有效数据加加。

void QueuePush(Que* pq, QDataType x) {
	assert(pq);
	QNode* newnode = malloc(sizeof(QNode));
	if (newnode == NULL) {
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail==NULL) {
		pq->head = pq->tail = newnode;
	}
	else {
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}
3.队头出队列：

出数据大致原理就是保存第一个然后让头指针指向下一个然后再把之前那个释放了，最后有效数据个数减减即可。

void QueuePop(Que* pq) {

	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->head->next == NULL) {
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else {
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}
4.获取队列头部元素：

队头有一个指针head直接拿取即可。

QDataType QueueFront(Que* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}
 5.获取队列尾元素：

队尾有一个指针也就是tail直接拿取即可。

QDataType QueueBack(Que* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}
6.获取队列中有效数据个数：

直接拿取有效数据size即可。

int QueueSize(Que* pq) {
	assert(pq);
	return pq->size;
}
7.检测队列是否为空，如果为空返回非零结果，如果非空返回0：

首先断言，返回时是一个表达式用来判断是否是真还是假。

bool QueueEmpty(Que* pq) {
	assert(pq);
	return pq->head == NULL;
}
8.销毁队列：

使用循环从队列的头部一直释放即可，最后把传进来的pq指针置空。

void QueueDestroy(Que* pq) {
	assert(pq);
	QNode* cur = pq->head;
	while (cur) {
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

下列是队列接口实现的全部代码Queue.c中的：

#include"Queue.h"

void QueueInit(Que* pq) {
	assert(pq);
	pq->head = pq->tail = NULL;
	pq->size = 0;
}



void QueueDestroy(Que* pq) {
	assert(pq);
	QNode* cur = pq->head;
	while (cur) {
		QNode* next = cur->next;
		free(cur);
		cur = next;
	}
	pq->head = pq->tail = NULL;
	pq->size = 0;
}

void QueuePush(Que* pq, QDataType x) {
	assert(pq);
	QNode* newnode = malloc(sizeof(QNode));
	if (newnode == NULL) {
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	if (pq->tail==NULL) {
		pq->head = pq->tail = newnode;
	}
	else {
		pq->tail->next = newnode;
		pq->tail = newnode;
	}
	pq->size++;
}

void QueuePop(Que* pq) {

	assert(pq);
	assert(!QueueEmpty(pq));

	if (pq->head->next == NULL) {
		free(pq->head);
		pq->head = pq->tail = NULL;
	}
	else {
		QNode* next = pq->head->next;
		free(pq->head);
		pq->head = next;
	}
	pq->size--;
}
QDataType QueueFront(Que* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->head->data;
}


QDataType QueueBack(Que* pq) {
	assert(pq);
	assert(!QueueEmpty(pq));

	return pq->tail->data;
}

bool QueueEmpty(Que* pq) {
	assert(pq);
	return pq->head == NULL;
}
int QueueSize(Que* pq) {
	assert(pq);
	return pq->size;
}

然后test.c测试代码是否能够正常运行:

#include"Queue.h"

void TestQueue() {
	Que q;
	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);

	while (!QueueEmpty(&q)) {
		printf("%d ", QueueFront(&q));
		QueuePop(&q);
	}
	printf("\n");

	QueueDestroy(&q);
}

int main() {
	TestQueue();
}

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

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

相关文章

搜索二维矩阵 II - LeetCode 热题 21

搜索二维矩阵 II - LeetCode 热题 21

大家好&#xff01;我是曾续缘&#x1f497; 今天是《LeetCode 热题 100》系列 发车第 21 天 矩阵第 4 题 ❤️点赞 &#x1f44d; 收藏 ⭐再看&#xff0c;养成习惯 搜索二维矩阵 II 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性&…
阅读更多...
20240402—Qt如何通过动态属性设置按钮样式？

20240402—Qt如何通过动态属性设置按钮样式？

前言 正文 1、点击UI文件 2、选择Bool型或是QString 3、设置后这里出现动态属性 4、这qss文件中绑定该动态属性 QPushButton[PopBlueBtn"PopBlueBtn"]{background-color:#1050B7;color:#FFFFFF;font-size:20px;font-family:Source Han Sans CN;//思源黑体 CNbor…
阅读更多...
Ansys Zemax | 如何将光栅数据从Lumerical导入至OpticStudio（上）

Ansys Zemax | 如何将光栅数据从Lumerical导入至OpticStudio（上）

附件下载 联系工作人员获取附件 本文介绍了一种使用Ansys Zemax OpticStudio和Lumerical RCWA在整个光学系统中精确仿真1D/2D光栅的静态工作流程。将首先简要介绍方法。然后解释有关如何建立系统的详细信息。 本篇内容将分为上下两部分&#xff0c;上部将首先简要介绍方法工…
阅读更多...
01 Python进阶：正则表达式

01 Python进阶：正则表达式

re.match函数 使用 Python 中的 re 模块时&#xff0c;可以通过 re.match() 函数来尝试从字符串的开头匹配一个模式。以下是一个简单的详解和举例&#xff1a; import re# 定义一个正则表达式模式 pattern r^[a-z] # 匹配开头的小写字母序列# 要匹配的字符串 text "h…
阅读更多...
程序的编译、链接过程分析（简洁浓缩版）！

程序的编译、链接过程分析（简洁浓缩版）！

《嵌入式工程师自我修养/C语言》系列——程序的编译、链接过程分析&#xff08;简洁浓缩版&#xff09;&#xff01; 一、程序的编译1.1 预编译指令 pragma1.2 编译过程概述1.3 符号表和重定位表 二、程序的链接2.1 分段组装2.2 符号决议2.2.1 强符号与弱符号2.2.2 GNU编译器的…
阅读更多...
了解与生成火焰图

了解与生成火焰图

目录 一、如何看懂火焰图 1、基本特征 2、基本分类 二、如何生成火焰图 1、捕获调用栈 2、折叠栈 3、转换为 svg 格式 4、展示 svg 一、如何看懂火焰图 1、基本特征 &#xff08;1&#xff09;纵轴&#xff1a;即每一列代表一个调用栈&#xff0c;每一个格子代表一个函…
阅读更多...
智能仓储变革在即，从业者该何去何从？

智能仓储变革在即，从业者该何去何从？

导语 大家好&#xff0c;我是智能仓储物流技术研习社的社长&#xff0c;你的老朋友&#xff0c;老K。行业群 新书《智能物流系统构成与技术实践》 随着2024年的到来&#xff0c;物流和仓储行业正处于一个技术革命的关键时刻。人工智能&#xff08;AI&#xff09;的融入不仅预示…
阅读更多...
【二叉树】Leetcode 437. 路径总和 III【中等】

【二叉树】Leetcode 437. 路径总和 III【中等】

路径总和 III 给定一个二叉树的根节点 root &#xff0c;和一个整数 targetSum &#xff0c;求该二叉树里节点值之和等于 targetSum 的 路径 的数目。 路径 不需要从根节点开始&#xff0c;也不需要在叶子节点结束&#xff0c;但是路径方向必须是向下的&#xff08;只能从父节…
阅读更多...
Zabbix6 - Centos7部署Grafana可视化图形监控系统配置手册手册

Zabbix6 - Centos7部署Grafana可视化图形监控系统配置手册手册

Zabbix6 - Centos7部署Grafana可视化图形监控系统配置手册手册 概述&#xff1a; Grafana是一个开源的数据可视化和监控平台。其特点&#xff1a; 1&#xff09;丰富的可视化显示插件&#xff0c;包括热图、折线图、饼图&#xff0c;表格等&#xff1b; 2&#xff09;支持多数据…
阅读更多...
[源码] Android 上的一些快捷方式，如通知、快捷方式等

[源码] Android 上的一些快捷方式，如通知、快捷方式等

目录 一、通知0. 配置权限1. 测试发送通知代码2. 打开通知设置界面代码3. 前台服务创建常驻通知 二、快捷方式1. 测试添加动态快捷方式代码 三、开发者图块四、桌面小部件 基于jetpack compose 框架的使用代码 一、通知 参见 官方文档 0. 配置权限 <uses-permission andr…
阅读更多...
REST API的指纹验证机制

REST API的指纹验证机制

前端或者客户端涉及数据相关的请求都是不安全的&#xff0c;从某种意义上只能通过一些手段降低请求不被容易使用。本来来介绍一种基于 JWT 的指纹机制。 关于 JWT 令牌机制就不详细介绍了。在 JWT 令牌中包含系统 JWT 指纹可以带来安全改进&#xff0c;而不会给用户带来任何不…
阅读更多...
RocketMQ 消费者源码解读：消费过程、负载原理、顺序消费原理

RocketMQ 消费者源码解读：消费过程、负载原理、顺序消费原理

B站学习地址 上一遍学习了三种常见队列的消费原理&#xff0c;本次我们来从源码的角度来证明上篇中的理论。 1、准备 RocketMQ 版本 <!-- RocketMQ --> <dependency><groupId>org.apache.rocketmq</groupId><artifactId>rocketmq-spring-boot-s…
阅读更多...
yolov5关键点检测-实现溺水检测与警报提示（代码+原理）

yolov5关键点检测-实现溺水检测与警报提示（代码+原理）

基于YOLOv5的关键点检测应用于溺水检测与警报提示是一种结合深度学习与计算机视觉技术的安全监控解决方案。该项目通常会利用YOLOv5强大的实时目标检测能力&#xff0c;并通过扩展或修改网络结构以支持人体关键点检测&#xff0c;来识别游泳池或其他水域中人们的行为姿态。 项…
阅读更多...
常关型p-GaN栅AlGaN/GaN HEMT作为片上电容器的建模与分析

常关型p-GaN栅AlGaN/GaN HEMT作为片上电容器的建模与分析

来源&#xff1a;Modeling and Analysis of Normally-OFF p-GaN Gate AlGaN/GaN HEMT as an ON-Chip Capacitor&#xff08;TED 20年&#xff09; 摘要 提出了一种精确基于物理的解析模型&#xff0c;用于描述p-GaN栅AlGaN/GaN高电子迁移率晶体管&#xff08;HEMT&#xff09…
阅读更多...
【Linux】Vim编辑器

【Linux】Vim编辑器

专栏文章索引&#xff1a;Linux 目录 在Vim编辑器中&#xff0c;一个Tab键相当于几个空格&#xff1f; 在Vim编辑器中&#xff0c;一个Tab键相当于几个空格&#xff1f; 在Vim编辑器中&#xff0c;默认情况下&#xff0c;一个Tab键相当于8个空格。 这是Vim的默认设置&#x…
阅读更多...
【C++】哈希之位图

【C++】哈希之位图

目录 一、位图概念二、海量数据面试题 一、位图概念 假如有40亿个无重复且没有排序的无符号整数&#xff0c;给一个无符号整数&#xff0c;如何判断这个整数是否在这40亿个数中&#xff1f; 我们用以前的思路有这些&#xff1a; 把这40亿个数遍历一遍&#xff0c;直到找到为…
阅读更多...
鸿蒙OS元服务开发：【（Stage模型）设置悬浮窗】

鸿蒙OS元服务开发：【（Stage模型）设置悬浮窗】

一、设置悬浮窗说明 悬浮窗可以在已有的任务基础上&#xff0c;创建一个始终在前台显示的窗口。即使创建悬浮窗的任务退至后台&#xff0c;悬浮窗仍然可以在前台显示。通常悬浮窗位于所有应用窗口之上&#xff1b;开发者可以创建悬浮窗&#xff0c;并对悬浮窗进行属性设置等操…
阅读更多...
frp内网穿透之（反向代理nginx）

frp内网穿透之（反向代理nginx）

通过公网 https 连接访问内网&#xff08;局域网&#xff09;本地http服务如下&#xff1a; 1.准备工作 ​ 想要实现内网穿透功能首先我们需要准备&#xff1a; 一台公网服务器&#xff08;用作frps的服务端&#xff09;一台需要做转发的内网服务器&#xff08;用作frpc的客…
阅读更多...
D-迷恋网游（遇到过的题，做个笔记）

D-迷恋网游（遇到过的题，做个笔记）

我的代码&#xff1a; #include <iostream> using namespace std; int main() {int a, b, c; //a表示内向&#xff0c;b表示外向&#xff0c;c表示无所谓cin >> a >> b >> c; //读入数 if (b % 3 0 || 3-b % 3 < c) //如果外向的人能够3人组成…
阅读更多...
Golang Channel底层实现原理

Golang Channel底层实现原理

1、本文讨论Channel的底层实现原理 首先&#xff0c;我们看Channel的结构体 简要介绍管道结构体中&#xff0c;几个关键字段 在Golang中&#xff0c;管道是分为有缓冲区的管道和无缓冲区的管道。 这里简单提一下&#xff0c;缓冲区大小为1的管道和无缓冲区的管道的区别&…
阅读更多...
最新文章

Copyright @ 2022~2023