栈(使用顺序表构建)

P. S.:以下代码均在VS2019环境下测试,不代表所有编译器均可通过。
P. S.:测试代码均未展示头文件stdio.h的声明,使用时请自行添加。

  

目录

  • 1、栈的概念
  • 2、栈的数组构建方法
    • 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 栈内数据的数量
  • 3、完整代码展示
  • 4、结语

1、栈的概念


  栈:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。栈中的数据元素遵守后进先出LIFO(Last In First Out)的原则。
   压栈:栈的插入操作叫做进栈/压栈/入栈,入数据在栈顶。
   出栈:栈的删除操作叫做出栈。出数据也在栈顶。
  通俗一点的理解就是,栈就像是一个羽毛球筒一样,先放进去的羽毛球,最后才能拿出来,反而后放进去的可以先拿出来,也就是我们上面提到的LIFO:Last In First Out。

在这里插入图片描述


  而栈我们可以通过顺序表来构建,也可以通过链表来构建,本文讲述的是顺序表构建内容。

  下面进入正文。




2、栈的数组构建方法

2.1 前言


  构建栈的需求有三个文件,包括Stact.c(用来书写逻辑的内容)、Stact.h(用来书写逻辑的声明)、test.c(用来测试我们所书写的代码)。

2.2 正文


  我们先将我们的逻辑申明书写完成,这样后面的内容我们就可以按照逻辑声明的顺序一步一步完成。
  首先我们需要有一个顺序表如下,在书写的时候我们就直接将它重命名,以便我们后面代码的书写。
typedef struct Stact
{
	int* a;
	int top;
	int capacity;
}ST,*pST;//分别为结构体类型名,和结构体指针

  书写完会发现,我们结构体中的数组类型已经被定死了,如果我们以后想要往栈中存储不同类型的数据,需要一个一个在代码中查找 int 然后修改,十分麻烦,不如直接将类型重命名为一个新的名字,之后的代码中如果需要修改,则直接修改重命名的内容即可。

typedef int STDataType;
typedef struct Stact
{
	STDataType* a;
	int top;
	int capacity;
}ST,*pST;//分别为结构体类型名,和结构体指针

  在此之后,我们则需要在书写几个函数来执行我们的初始化,压栈,出栈,等操作。
  代码如下:

//初始化
void STInit(pST pst);
//顺序表的销毁
void STDestroy(pST pst);
//压栈
void STPush(pST pst, STDataType x);
//出栈
void STPop(pST pst);
//取栈顶数据
STDataType STTop(pST pst);
//栈判空
bool STEmpty(pST pst);
//栈的大小
int STSize(pST pst);

  下面我们对应其顺序一步一步书写

2.2.1 栈的初始化


  对于栈的初始化,代码如下:
void STInit(pST pst)
{
	assert(pst);
	pst->a = NULL;

	//让栈顶指向下一个位置
	pst->top = 0;

	//让栈顶指向当前位置
	//pst->top = -1;

	pst->capacity = 0;
}

  我们可以看到代码块中书写了两种方法,一种是让栈顶指向下一个位置,一种是让栈顶指向当前位置,两者皆可,本文采用的是令栈顶指向下一个位置的方法。


2.2.2 栈的销毁


  对于栈的销毁,代码如下:
void STDestroy(pST pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}

2.2.3 压栈


  对于数据的压栈,我们在开头就需要判断一下数组的空间是否足够,或者数组空间是否为NULL,如果不足或为NULL,我们需要对其进行空间开辟,使用 realloc 函数进行,其中我们知道本文采用的方法是将 top 指向下一个位置所处的下表,故代码如下:
void STPush(pST pst, STDataType x)
{
	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("STPush:realloc");
			return;
		}
		pst->a = tmp;
	}
	pst->a[pst->top] = x;
	pst->top++;
}

2.2.4 出栈


  对于出栈,就十分容易了,我们每一次压栈时使用的都是 top 来定位栈顶的位置,这里我们可以直接进行 top-- 操作,此时不用对栈顶的内容改变,下一次入栈时便会直接覆盖此时需要删除的内容。
  代码如下
void STPop(pST pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}

2.2.5 取栈顶数据


  取栈顶的数据代码如下:
STDataType STTop(pST pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst->a[pst->top - 1];
}

2.2.6 对栈内数组判断是否为空


  判空代码如下:
bool STEmpty(pST pst)
{
	assert(pst);
	return pst->top == 0;
}

2.2.7 栈内数据的数量


  查看栈内数据的数量的代码如下:
int STSize(pST pst)
{
	assert(pst);
	return pst->top;
}




3、完整代码展示


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


typedef int STDataType;

typedef struct Stact
{
	STDataType* a;
	int top;
	int capacity;
}ST,*pST;

//初始化
void STInit(pST pst);
//顺序表的销毁
void STDestroy(pST pst);
//压栈
void STPush(pST pst, STDataType x);
//出栈
void STPop(pST pst);
//取栈顶数据
STDataType STTop(pST pst);
//栈判空
bool STEmpty(pST pst);
//栈的大小
int STSize(pST pst);

  Stact.c:

#include "Stact.h"

//初始化
void STInit(pST pst)
{
	assert(pst);
	pst->a = NULL;

	//让栈顶指向下一个位置
	pst->top = 0;

	//让栈顶指向当前位置
	//pst->top = -1;

	pst->capacity = 0;
}


//顺序表的销毁
void STDestroy(pST pst)
{
	assert(pst);
	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}

//压栈
void STPush(pST pst, STDataType x)
{
	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("STPush:realloc");
			return;
		}
		pst->a = tmp;
	}
	pst->a[pst->top] = x;
	pst->top++;
}

//出栈
void STPop(pST pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}

//取栈顶数据
STDataType STTop(pST pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst->a[pst->top - 1];
}

//栈判空
bool STEmpty(pST pst)
{
	assert(pst);
	return pst->top == 0;
}

//栈的大小
int STSize(pST pst)
{
	assert(pst);
	return pst->top;
}

  test.c:

#include "Stact.h"

int main()
{
	// 入栈:1 2 3 4
	// 出栈:4 3 2 1  /  2 4 3 1
	ST s;
	STInit(&s);
	STPush(&s, 1);
	STPush(&s, 2);

	printf("%d ", STTop(&s));
	STPop(&s);

	STPush(&s, 3);
	STPush(&s, 4);

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

	STDestroy(&s);
}




4、结语


  十分感谢您观看我的原创文章。
  本文主要用于个人学习和知识分享,学习路漫漫,如有错误,感谢指正。
  如需引用,注明地址。

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

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

相关文章

工程绘图神器:Origin 2021软件安装与图像demo水印问题解决

目录 引言 正文 01-Origin软件简介 02-Origin软件安装 03-Origin软件复制图像带有水印问题解决 引言 注&#xff1a;本篇软件安装内容引用了微信公众号“软件管家”里的Origin 2021安装教程和…

[1726]java试飞任务规划管理系统Myeclipse开发mysql数据库web结构java编程计算机网页项目

一、源码特点 java试飞任务规划管理系统是一套完善的java web信息管理系统&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为 TOMCAT7.0,Myeclipse8.5开发&#xff0c;数据库为Mysql…

环境配置、内核配置、字符型驱动设备

配置交叉编译环境 arm-linux-gcc -v交叉编译 1、将版本配置为4.4.3 2、内核一部分 外设&#xff08;时钟配置、GPIO、串口&#xff09; 3、配置环境&#xff08;将板载设置为2440&#xff09; ubuntu下查看函数原码 ctag -R 路径 设置完成后进主 函数将光标停在函数名字处按…

Linux动态库与静态库解析

文章目录 一、引言二、C/C源文件的编译过程三、静态库1、静态库的定义和原理2、静态库的优缺点3、静态库的创建和使用a、创建静态库b、使用静态库 四、动态库1、动态库的定义和原理2、动态库的优缺点3、动态库的创建和使用示例a、创建动态库b、使用动态库 五、动静态库的比较 一…

KDTree空间搜索算法学习

目录 KDTree&#xff08;K-Dimensional Tree&#xff09;原理步骤空间索引建立例子[^1] 相关包案例[^2]数据KDTree 识别轨道衔接出行轨道衔接单车骑行范围分析结果保存 KDTree&#xff08;K-Dimensional Tree&#xff09;原理 将需要匹配的 K 维空间点建立 K 维树空间索引&…

Unet简单结构概述

总体结构代码 class UNet(nn.Module):def __init__(self, n_channels, n_classes, bilinearFalse):super(UNet, self).__init__()self.n_channels n_channelsself.n_classes n_classesself.bilinear bilinearself.inc (DoubleConv(n_channels, 64))self.down1 (Down(64, …

软件设计师-应用技术-数据结构及算法题4

考题形式&#xff1a; 第一题&#xff1a;代码填空 4-5空 8-10第二题&#xff1a;时间复杂度 / 代码策略第三题&#xff1a;拓展&#xff0c;跟一组数据&#xff0c;把数据带入代码中&#xff0c;求解 基础知识及技巧&#xff1a; 1. 分治法&#xff1a; 基础知识&#xff1…

取消vscode go保存时自动格式化代码

go:v1.22.0 vscode go 插件&#xff1a;v0.41.4 setting.json formatOnSave&#xff1a; 保存文件时&#xff0c;是否执行格式化 codeActiosnOnSave&#xff1a;保存文件时&#xff0c;是否执行某些操作 organizeImports: 不再改动import&#xff08;&#xff09;里面的包

分类规则挖掘(三)

目录 四、贝叶斯分类方法&#xff08;一&#xff09;贝叶斯定理&#xff08;二&#xff09;朴素贝叶斯分类器&#xff08;三&#xff09;朴素贝叶斯分类方法的改进 五、其它分类方法 四、贝叶斯分类方法 贝叶斯 (Bayes) 分类方法是以贝叶斯定理为基础的一系列分类算法的总称。贝…

python中numpy库使用

array数组 生成array数组 将list转化为array数组 import numpy as np np.array([1,2],typenp.int32)其中dtype定义的是元素类型&#xff0c;np.int32指32位的整形 如果直接定义dtypeint 默认的是32位整形。 zeors和ones方法 zeros()方法&#xff0c;该方法和ones()类似&a…

Qt——入门基础

目录 Qt入门第一个应用程序 main.cpp widget.h widget.cpp widget.ui .pro Hello World程序 对象树 编辑框 按钮 Qt 窗口坐标系 Qt入门第一个应用程序 main.cpp 这就像一开始学语言时都会打印一个“Hello World”一样&#xff0c;我们先来看看创建好一个项目后&…

ModuleNotFoundError: No module named ‘PyQt5‘

运行python程序的时候报错&#xff1a;ModuleNotFoundError: No module named ‘PyQt5‘ 这是因为没有安装pyqt5依赖包导致的&#xff0c;安装一下即可解决该问题。 安装依赖 pip install PyQt5 -i https://pypi.tuna.tsinghua.edu.cn/simple 这里是使用的清华镜像源进行安装…

数据库系统原理实验报告5 | 数据查询

整理自博主本科《数据库系统原理》专业课自己完成的实验报告&#xff0c;以便各位学习数据库系统概论的小伙伴们参考、学习。 专业课本&#xff1a; ———— 本次实验使用到的图形化工具&#xff1a;Heidisql 目录 一、实验目的 二、实验内容 1.找出读者所在城市是“shangh…

STM32G0存储器和总线架构

文章目录 前言一、系统架构二、存储器构成三、存储器地址映射四、存储器边界地址五、外设寄存器边界地址 前言 此文章是STM32G0 MCU的学习记录&#xff0c;并非权威&#xff0c;请谨慎参考。 STM32G0主流微控制器基于工作频率可达64 MHz的高性能Arm Cortex-M0 32位RISC内核。该…

GEE数据集——DeltaDTM 全球沿海数字地形模型数据集

DeltaDTM 全球沿海数字地形模型产品 简介 DeltaDTM 是全球沿岸数字地形模型&#xff08;DTM&#xff09;&#xff0c;水平空间分辨率为 1 弧秒&#xff08;∼30 米&#xff09;&#xff0c;垂直平均绝对误差&#xff08;MAE&#xff09;为 0.45 米。它利用 ICESat-2 和 GEDI …

内容安全(IPS入侵检测)

入侵检测系统&#xff08; IDS &#xff09;---- 网络摄像头&#xff0c;侧重于风险管理&#xff0c;存在于滞后性&#xff0c;只能够进行风险发现&#xff0c;不能及时制止。而且早期的IDS误报率较高。优点则是可以多点进行部署&#xff0c;比较灵活&#xff0c;在网络中可以进…

【java9】java9新特性之改进JavaDocs

Java9在JavaDocs方面的主要新特性是&#xff0c;其输出现在符合兼容HTML5标准。在之前的版本中&#xff0c;默认的HTML版本是 HTML4.01&#xff0c;但在Java9及之后的版本中&#xff0c;JavaDocs命令行工具将默认使用HTML5作为输出标记语言。这意味着&#xff0c;使用JavaDocs工…

Markdown 精简教程(胎教级教程)

文章目录 一、关于 Markdown1. 什么是 Markdown&#xff1f;2. 为什么要用 Markdown&#xff1f;3. 怎么用 Markdown&#xff1f;&#xff08;编辑软件&#xff09; 二、标题1. 常用标题写法2. 可选标题写法3. 自定义标题 ID4. 注意事项 三、段落四、换行五、字体选项1. 粗体2.…

跨境电商行业分析-商品出海的四大路径

1. 跨境电子商务模式和国内电子商务模式【区别】 最大的不同点有3个&#xff1a; 达成交易的双方是属于不同【关境】的交易主体商品通过众多电子商务平台/独立站等&#xff0c;进行支付结算通过国际物流的方式&#xff08;海运/铁路/空运/卡车&#xff09;进行报关、清关、派…

anconda创建虚拟环境,使用虚拟环境(基于win平台)

假设已经安装了anconda&#xff0c;打开anaconda的 shell。 查看已存在的虚拟环境&#xff0c;base是默认的&#xff0c;不用理会&#xff0c;后面的yolov5就是用户创建的 #查看有那些虚拟环境 (base) PS C:\Users\x> conda info -e # conda environments: # base …