【数组栈】实现

目录

栈的概念及其结构

栈的实现

数组栈

链式栈

 栈的常见接口实现

主函数Test.c

头文件&函数声明Stack.h

头文件

函数声明

函数实现Stack.c

初始化SLInit

扩容Createcapacity

压栈STPush

出栈STPop

栈顶元素STTop

判断栈是否为空STempty

栈内元素个数STSzie

数组栈空间释放STDestroy

数组栈总代码 


我们已经学习过了【线性表】中的顺序表和链表。今天开始进入栈和队列。栈和队列是顺序表和链表的延续,也是一种线性表(线性表在逻辑上也是连续的)。大体结构上都很相似,所以大家学习起来也会很容易的。但是栈和队列也有自己独特的性质,学习也需要特别注意哦。

栈的概念及其结构

:一种特殊的线性表,其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶,另一端称为栈底。

栈中的数据元素遵守 后进先出 / 后进先出 LIFO(Last In First Out)的原则

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

 

【先进后出/后进先出】可以类比【弹夹】

栈的实现

了解了栈的概念,如何实现栈呢?

根据前面博文我们可以【数组栈】和【链式栈】 

数组栈

数组栈比较简单,也是快速容易实现,首先就是【数组栈】实现。

链式栈

链式栈分为【单链表】和【双向链表】去实现栈。毋庸置疑,【双向链表实现】栈顶可以是尾巴,也可以是头,因为双向链表的头插/头删和尾插/尾删都是很方便的。

但是为了节省资源,我们用【单链表】该怎样去设计呢?

单链表实现栈栈顶只能是单链表头(头插/头删易),栈底只能是单链表尾(头删很复杂)

 

 栈的常见接口实现

  • 断言NULL/Pop==0情况
  • 改变结构体用指针
  • top的指向
  • 单个数据直接用,多个数据用结构体包含起来
  • 数组的数据访问用数组下标即可访问
  • pst和pst->a搞清楚!
  • 入栈顺序是只有一种,但是出栈顺序有多种!!

主函数Test.c

#include"Stack.h"
int main()
{
	ST pst;//创建结构体
	STInit(&pst);//传地址是修改结构体内部
	STPush(&pst, 1);
	STPush(&pst, 2);
	STPush(&pst, 3);
	STPush(&pst, 4);
	STPush(&pst, 5);
	while (!STempty(&pst))
	{
		printf("%d ", STTop(&pst));
		STPop(&pst);
	}
	STDestroy(&pst);
}

由于栈是其只允许在固定的一端进行插入和删除元素操作。所以栈的访问是必须先Pop弹出元素才能访问下一个元素。

	while (!STempty(&pst))
	{
		printf("%d ", STTop(&pst));
		STPop(&pst);
	}

头文件&函数声明Stack.h

头文件

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

函数声明

  • 创建结构体
typedef int STDatatype;
typedef struct Stack
{
	STDatatype* a;
	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);
  • 判断栈是否为NULL
bool STempty(ST* pst);
  • 栈内的元素个数 
int STSize(ST* pst);

函数实现Stack.c

初始化SLInit

 如果初始化 top=0:表示栈内元素的个数。作为a[top]指针指向栈顶元素的下一个。

 如果初始化 top=-1:表示数组元素的下标。作为a[top]指针指向栈顶元素。 

#include"Stack.h"
void STInit(ST* pst)
{
	assert(pst);
	pst->a = 0;
//表示top指向栈顶元素的下一个位置
	pst->top = 0;
//表示top指向栈顶元素
	//pst->top = -1;
	pst->capacity = 0;
}

扩容Createcapacity

void Createcapacity(ST* pst)
{
	//扩容
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
		ST* tmp = (ST*)realloc(pst->a, sizeof(ST) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
}

压栈STPush

void STPush(ST* pst, STDatatype x)
{
	assert(pst);
	Createcapacity(pst);
	pst->a[pst->top] = x;
	pst->top++;
}

出栈STPop

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

栈顶元素STTop

STDatatype STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst->a[pst->top-1];
}

判断栈是否为空STempty

bool STempty(ST* pst)
{
	assert(pst);
	return pst->top == 0;//为0就是true 为!=0就是为flase
}

栈内元素个数STSzie

int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}

数组栈空间释放STDestroy

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

数组栈总代码 

//Test.c
#include"Stack.h"
int main()
{
	ST pst;
	STInit(&pst);
	STPush(&pst, 1);
	STPush(&pst, 2);
	STPush(&pst, 3);
	STPush(&pst, 4);
	STPush(&pst, 5);
	while (!STempty(&pst))
	{
		printf("%d ", STTop(&pst));
		STPop(&pst);
	}
	STDestroy(&pst);
}
//Stack.h
#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int STDatatype;
typedef struct Stack
{
	STDatatype* a;
	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->a = 0;
	pst->top = 0;
	pst->capacity = 0;
}

void Createcapacity(ST* pst)
{
	//扩容
	if (pst->top == pst->capacity)
	{
		int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
		ST* tmp = (ST*)realloc(pst->a, sizeof(ST) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		pst->a = tmp;
		pst->capacity = newcapacity;
	}
}

void STPush(ST* pst, STDatatype x)
{
	assert(pst);
	Createcapacity(pst);
	pst->a[pst->top] = x;
	pst->top++;
}

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

STDatatype STTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst->a[pst->top-1];
}


bool STempty(ST* pst)
{
	assert(pst);
	return pst->top == 0;//为0就是true 为!=0就是为flase
}


int STSize(ST* pst)
{
	assert(pst);
	return pst->top;
}


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

✔✔✔✔✔最后,感谢大家的阅读,若有错误和不足,欢迎指正!各位小伙伴乖乖敲代码哦。 

代码---------→【唐棣棣 (TSQXG) - Gitee.com】

联系---------→【邮箱:2784139418@qq.com】

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

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

相关文章

ABB机 器 人 操 作 培 训

目 录 1 培训手册介绍 ---------------------------------------------2 2 系统安全与环境保护 ---------------------------------------------3 3 机器人综述 ---------------------------------------------5 4 机器人示教 --------------------------------------------12…

普通平衡树

题意&#xff1a;略&#xff0c;题中较清晰。 用二叉查找树来存储数据&#xff0c;为了增加效率&#xff0c;尽量使左子树和右子树的深度差不超过一&#xff0c;这样可以时间控制在logn&#xff0c;效率比较高。 右旋和左旋&#xff0c;目的是为了维护二叉树的操作&#xff0…

CSGO搬砖项目全面讲解 ,CSGO搬砖注意事项

Steam/CSGO游戏搬砖全套操作流程之如何选品&#xff08;第二课&#xff09; 一个游戏只要能搬&#xff0c;只要体量不够大&#xff0c;很快就会货币价格暴跌&#xff0c;直接凉凉。市面上的能稳定手动搬砖的游戏越来越少。所以对于兼职赚点外快的散人搬砖党来说&#xff0c;找一…

【Vue入门篇】基础篇—Vue指令,Vue生命周期

&#x1f38a;专栏【JavaSE】 &#x1f354;喜欢的诗句&#xff1a;更喜岷山千里雪 三军过后尽开颜。 &#x1f386;音乐分享【如愿】 &#x1f384;欢迎并且感谢大家指出小吉的问题&#x1f970; 文章目录 &#x1f354;Vue概述&#x1f384;快速入门&#x1f33a;Vue指令⭐v-…

微信小程序登录获取不到头像和昵称解决办法

微信小程序登录获取不到头像和昵称主要原因是&#xff1a;小程序wx.getUserProfile接口被收回&#xff01; 大家可以按照文档操作↓ PS&#xff1a; 针对小程序wx.getUserProfile接口将被收回后做出的授权调整 小程序文档中提出的调整说明 对于此次变化&#xff0c;现将小程…

如何满足BMW EDI项目的PKT需求?

近期宝马BMW&#xff08;以下简称BMW&#xff09;在其部分供应商之间试点推进PKT项目&#xff0c;BMW为什么要启动 PKT 计划呢&#xff1f; 业务系统全面升级统一全球所有宝马工厂的流程 宝马内部的物流供货流程 近期BMW PKT需求主要针对其内部物流供货流程展开&#xff1a; …

Android : Spinner(列表选项框) + BaseAdapter -简单应用

​​容器与适配器&#xff1a;​​​​​ http://t.csdnimg.cn/ZfAJ7 示例图&#xff1a; 实体类 Demo.java package com.example.mygridviewadapter.entity;public class Demo {private String text;private int img;public Demo(String text, int img) {this.text…

QQ怎么备份聊天记录?3个方法教你快速备份!

QQ聊天记录作为用户和亲人、好友以及同事之间沟通的凭证&#xff0c;可以帮助我们回忆起过去的交流内容。如果我们不小心误删了QQ聊天记录或者更换了新手机&#xff0c;那么这时候就需要备份聊天记录。qq怎么备份聊天记录呢&#xff1f;本文将介绍3个简单方法&#xff0c;帮助您…

Oracle-客户端连接报错ORA-12545问题

问题背景: 用户在客户端服务器通过sqlplus通过scan ip登陆访问数据库时&#xff0c;偶尔会出现连接报错ORA-12545: Connect failed because target host or object does not exist的情况。 问题分析&#xff1a; 首先&#xff0c;登陆到连接有问题的客户端数据库上&#xff0c;…

va-Q-tec实现温度敏感产品运输过程质量控制温控无忧

摘要&#xff1a;温度敏感产品运输对供应链全流程的温度质量要求较高&#xff0c;往往需要借助特殊的温湿度监测技术产品。va-Q-tec与虹科Comet合作&#xff0c;采用虹科Comet的U系列温度记录仪&#xff0c;为集装箱运输过程提供完整的温控包装解决方案。 一、客户背景 va-Q-…

算法通关村第十二关-白银挑战字符串经典题目

大家好我是苏麟 , 今天带来字符串相关的题目 . 大纲 反转问题字符串反转K个一组反转仅仅反转字母反转字符串中的单词 反转问题 字符串反转 描述 : 编写一个函数&#xff0c;其作用是将输入的字符串反转过来。输入字符串以字符数组 s的形式给出。 题目 : LeetCode 344. 反转…

【PPspliT】ppt转pdf-保留过渡动画

网址 http://www.maxonthenet.altervista.org/ppsplit.php 下载安装 使用 再次打开ppt&#xff0c;就能在上方的选项栏里头看到了&#xff1a;

【Unity】接入MAX聚合广告SDK Applovin + GoogleAdmob

版本&#xff1a; Unity&#xff1a;2019.4.35f1gradle plugin: 4.2.0 &#xff08;实际要7.0 对应build_tools:34.0.0) gradle: 6.7.1 &#xff08;实际要7.0 对应build_tools:34.0.0) jdk: 1.8.0_241build_tools: 34.0.0 ndk: android-ndk-r19 文档&#xff1a; 6.0.1(Andro…

使用宝塔安装Alist

废话不多说&#xff0c;直接上教程&#xff0c;根据我的步骤一步一步来&#xff0c;肯定可以成功&#xff01; 我这边使用一键安装的时候&#xff0c;一致报错&#xff0c;提示证书过期&#xff0c;无奈我就开始了手动安装&#xff0c;下面的教程也是手动安装的教程 首先&…

RabbitMQ安装说明

注意: 本次安装以 CentOS 7为例 1、 准备软件 erlang 18.3 1.el7.centos.x86_64.rpm socat 1.7.3.2 5.el7.lux.x86_64.rpm rabbitmq server 3.6.5 1.noarch.rpm 2、安装Erlang rpm -ivh erlang-18.3-1.el7.centos.x86_64.rpm 3.、安装RabbitMQ 安装 rpm -ivh socat-1.7.3.2-…

码云 -- 本地代码上传到码云

1. 在码云上创建远程仓库 复制远程仓库地址 2. 在本地代码上创建 git 仓库 在本地代码文件夹上&#xff0c;打开git 命令窗口 输入初始化命令&#xff0c;创建 git 仓库 git init3. 给 git 仓库添加远程仓库 继续输入 git 命令 git remote add origin 远程仓库地址4. 按 git 的…

提升性能测试效率:JMeter中的用户自定义变量!

前言 在测试过程中&#xff0c;我们经常会碰到测试服务地址有改动的情况&#xff0c;为了方便&#xff0c;我们会把访问地址参数化&#xff0c;当访问地址变化了&#xff0c;我们只需要把参数对应的值改动一下就可以了。 一&#xff1a;添加配置元件-用户定义的变量&#xff…

python命令行 引导用户填写ssh登录信息

字多不看&#xff0c;直接体验&#xff1a; 待补充 演示代码 # -*- coding:UTF-8 -*- """ author: dyy contact: douyaoyuan126.com time: 2023/11/23 9:20 file: 引导用户填写ssh接口信息.py desc: xxxxxx """# region 引入必要的依赖 impor…

腾讯云 小程序 SDK对象存储 COS使用记录,原生小程序写法。

最近做了一个项目&#xff0c;需求是上传文档&#xff0c;文档类型多种&#xff0c;图片&#xff0c;视频&#xff0c;文件&#xff0c;doc,xls,zip,txt 等等,而且文档类型可能是大文件&#xff0c;可能得上百兆&#xff0c;甚至超过1G。 腾讯云文档地址&#xff1a;https://c…

AI如何帮助IT领导者优化成本和降低风险

围绕AI的兴奋和好奇心-以及随之而来的可能性-让整个行业沸沸扬扬&#xff0c;结果不言而喻&#xff0c;32%的IT领导者表示&#xff0c;集成AI是2023年的首要任务&#xff0c;其次是降低安全风险(31%)和降低IT成本(29%)。 虽然在可预见的未来&#xff0c;AI可能是IT领导者的首要…