程序员经验分享-hwhale

数据结构——栈（九）

2023-05-16

数据结构

文章目录

  • 数据结构
  • 前言
  • 一、栈的介绍
  • 二、栈的实现
    • 1.栈的结构
    • 2.栈的初始化
    • 3.进栈
    • 4.出栈
    • 5.栈的判断
    • 6.取栈顶元素
    • 7.栈的清空
    • 8.栈的销毁
  • 总结

前言

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

一、栈的介绍

1、栈的英文为(stack)

2、栈是一个先进后出(FILO-First In Last Out)的有序列表。

3、栈(stack)是限制线性表中元素的插入和删除只能在线性表的同一端进行的一种特殊线性表。允许插入和删除的一端，为变化的一端，称为栈顶(Top)，另一端为固定的一端，称为栈底(Bottom)。

4、根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。

图解方式说明出栈(pop)和入栈(push)的顺序
在这里插入图片描述

二、栈的实现

栈有顺序栈和链栈两种，所以栈的实现可以使用数组实现，也可以使用链表。
但是相对而言数组的结构实现更优一些。

1.栈的结构

由于栈的访问都是在尾上，所以用一个top来标记尾。

// 支持动态增长的栈
typedef int STDataType;
typedef struct Stack
{
	STDataType *a;//存储数据的数组
	int top; //栈顶的位置
	int capacity; //栈能存储的最大容量
}stack;
//静态栈
typedef int STDataType;
#define N 10
typedef struct Stack
{
	STDataType a[N];
	int top; // 栈顶
}Stack;

2.栈的初始化

//栈的初始化
int StackInit(stack *st)
{
	assert(st);   
	//这里给栈的初始大小为4个整型变量的大小
	st->a = (STDataType*)malloc(sizeof(stack)* 4);
	st->top = -1;//给栈顶一个初始值也可设置为其他值
	st->capacity = 4;//给一个初始大小，也可设置为其他值
	return 1;
}

在这里插入图片描述

3.进栈

//进栈 
int StackPush(stack *st, STDataType x)
{
	assert(st);
	
	if (st->top == st->capacity)//如果栈满则扩容
	{
		STDataType* tmp = (STDataType*)realloc(st->a, sizeof(stack)* st->capacity * 2);

		if (tmp == NULL)
		{
			exit(-1);//结束整个程序
		}
		st->capacity *= 2;
		st->a = tmp;
	}

	//在top位置插入数据后，top++表示栈顶向后移一个位置
	st->a[st->top++] = x;
	printf("%d进栈成功\n",x); 
}

在这里插入图片描述

4.出栈

//出栈 
void StackPop(stack* st)
{
	assert(st);
	//assert(!StackEmpty(st));//判断栈非空，若空则不进行删除操作
	st->top--;//top--即可，下一次数据入栈会直接覆盖top位置的值
}

在这里插入图片描述
出栈两次之后只剩下两个栈

5.栈的判断

//判断栈是否为空
void StackEmpty(stack* st)
{
	assert(st);
	if (st->top == -1)//若top为-1，说明栈中没有元素，为空
	{
		printf("栈为空\n"); 
	}
	else
	printf("栈不为空\n"); 
}

//得到栈的数据个数
void StackSize(stack *st)
{
	assert(st);
	printf("有%d个栈\n",(st->top)+1);  //从-1开始所以要初始化为0 
}

在这里插入图片描述

6.取栈顶元素

//取栈顶元素 
void StackTop(stack* st)
{
	assert(st);
//	assert(!StackEmpty(st));

	printf( "栈顶为%d\n",st->a[st->top - 1]);
}

7.栈的清空

void Stackclear(stack* st)
{
	assert(st);
	//assert(!StackEmpty(st));//判断栈非空，若空则不进行删除操作
	st->top=-1;//top--即可，下一次数据入栈会直接覆盖top位置的值
	printf("栈清空成功\n");
}

在这里插入图片描述

8.栈的销毁

//栈的销毁
void StackDestroy(stack* st)
{
		
	assert(st);
	free(st->a);
	st->a = NULL;
	st->capacity = 0;
	st->top = 0;
	free(st);
	printf("栈销毁成功\n"); 
}

总结

在这里插入图片描述

附上完整代码

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
// 支持动态增长的栈，本文以动态增长的栈为例
typedef int STDataType;
typedef struct Stack
{
	STDataType *a;//存储数据的数组
	int top; //栈顶的位置
	int capacity; //栈能存储的最大容量
}stack;

//栈的初始化
int StackInit(stack *st)
{
	assert(st);   
	//这里给栈的初始大小为4个整型变量的大小
	st->a = (STDataType*)malloc(sizeof(stack)* 4);
	st->top = -1;//给栈顶一个初始值也可设置为其他值
	st->capacity = 4;//给一个初始大小，也可设置为其他值
	return 1;
}

//进栈 
int StackPush(stack *st, STDataType x)
{
	assert(st);
	
	if (st->top == st->capacity)//如果栈满则扩容
	{
		STDataType* tmp = (STDataType*)realloc(st->a, sizeof(stack)* st->capacity * 2);

		if (tmp == NULL)
		{
			exit(-1);//结束整个程序
		}
		st->capacity *= 2;
		st->a = tmp;
	}
	//在top位置插入数据后，top++表示栈顶向后移一个位置
	st->a[st->top++] = x;
	printf("%d进栈成功\n",x); 
//	if(st->top>3)
//	printf("%d进栈失败\n",x); 
}
//判断栈是否为空
void StackEmpty(stack* st)
{
	assert(st);
	if (st->top == -1)//若top为-1，说明栈中没有元素，为空
	{
		printf("栈为空\n"); 
	}
	else
	printf("栈不为空\n"); 
}

//得到栈的数据个数
void StackSize(stack *st)
{
	assert(st);
	printf("有%d个栈\n",(st->top)+1);  //从-1开始所以要初始化为0 
}
//出栈 
void StackPop(stack* st)
{
	assert(st);
	//assert(!StackEmpty(st));//判断栈非空，若空则不进行删除操作
	st->top--;//top--即可，下一次数据入栈会直接覆盖top位置的值
}
//取栈顶元素 
void StackTop(stack* st)
{
	assert(st);
//	assert(!StackEmpty(st));

	printf( "栈顶为%d\n",st->a[st->top - 1]);
}
//栈的销毁
void StackDestroy(stack* st)
{	
	assert(st);
	free(st->a);
	st->a = NULL;
	st->capacity = 0;
	st->top = 0;
	free(st);
	printf("栈销毁成功\n"); 
}
void Stackclear(stack* st)
{
	assert(st);
	//assert(!StackEmpty(st));//判断栈非空，若空则不进行删除操作
	st->top=-1;//top--即可，下一次数据入栈会直接覆盖top位置的值
	printf("栈清空成功\n");
}
int main()
{
	stack st;
	int ret=StackInit(&st);
	if(ret==1)
	printf("栈初始化成功\n"); 
    StackPush(&st,1);
    StackPush(&st,3);
    StackPush(&st,5);
    StackPush(&st,7);
    StackEmpty(&st);
    StackSize(&st);
    StackPop(&st); 
    StackSize(&st);
    StackPop(&st); 
    StackSize(&st);
    StackTop(&st);
    Stackclear(&st);
    StackSize(&st);
 }
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

数据结构——栈（九） 的相关文章

随机推荐

  • 汇编语言--实验七

    实验名称 xff1a 寻址方式在结构化数据访问中的应用 一 xff1a 实验目的 学会寻址方式在结构化数据访问中的应用 xff1b 利用前面所学知识熟悉编程技巧 二 xff1a 实验内容及步骤 内容 xff1a xff08 1 xff09

  • 汇编语言--实验九

    实验名称 xff1a 根据材料编程 目录 实验名称 xff1a 根据材料编程 一 xff1a 实验目的 二 xff1a 实验内容及步骤 内容 xff08 1 xff09 步骤 xff08 1 xff09 结果 xff08 1 xff09 三

  • Visual Studio 2022 C++开发 (Win)配置教程

    前言 本文将讲解如何在Window系统下配置Visual Studio 2022版本的C 43 43 开发环境 步骤 下载并且安装Visual Studio Tools xff08 1 xff09 下载 Visual Studio Tool

  • template ＜ class T＞ ，map和vector用法——恶补c++

    部分目录 template lt class T gt 是什么找到各素数因子map数组下用法map遍历map元素的默认值 vector 用法 template lt class T gt 是什么 template lt class T gt

  • 停车场寻车系统（识别车牌，手机app查询相关信息）

    停车场寻车系统 文章目录 停车场寻车系统前言一 手机app二 车牌识别三 数据查询总结 停车场寻车系统 前言 上个星期用了一周左右做了一个停车场寻车系统的项目 xff0c 可以识别车牌 xff0c 通过手机app查询车辆信息 一 手机app

  • K210+MLX90614红外测温

    红外测温 文章目录 红外测温前言一 MLX90614二 使用步骤总结 前言 K210随便找一个都行 一 MLX90614 这个模块之前的博客有介绍 xff0c 他是用IIC通信的 模块就不过多介绍了 xff0c 之间看代码吧 import

  • PHP mysql_connect()连接-已淘汰

    1 首先在mysql命令控制台新建数据库 mysql gt create database test Query OK 1 row affected 0 04 sec mysql gt use test Database changed m

  • STM32使用红外测温

    红外测温 文章目录 红外测温前言一 原理二 STM32代码1 MLX90614 c2 MLX90614 h 总结 前言 一 原理 红外测温的原理可以直接去看卖家的手册 xff0c 手册多余的话太多了 xff0c 知道他是IIC通信的就行了

  • Arduino——PAJ7620手势识别模块

    手势识别模块 文章目录 手势识别模块前言一 安装PAJ7620库二 代码 前言 在用arduino驱动这些模块得时候 xff0c 方法很简单 xff0c 先去管理库中找这个库 xff0c 如果有这个库 xff0c 然后下载这个库 xff0c

  • Arduino——正点原子sim800c模块

    sim800c 文章目录 sim800c前言一 arduino代码 前言 最近要做一个项目需要用到sim800c xff0c 就用arduino驱动一下吧 xff0c 用的是正点原子的sim800c 使用的时候最好使用12v1A供电 xff

  • Arduino——野火GPS模块

    GPS模块 文章目录 GPS模块前言一 Arduino代码 前言 手上还有一个GPS xff0c 用arduino做模块很方便 xff0c 打算和短信模块结合 xff0c 短信模块上次已经使用完成了 xff0c 这次学习一下GPS模块 看模

  • Arduino——GY39大气压、温湿度、光照模块

    GY39模块 文章目录 GY39模块前言一 模块介绍二 arduino代码 前言 前几天买东西的时候买了一个GY39 xff0c 这个模块集成了温湿度 xff0c 大气压 xff0c 海拔 xff0c 光照一体 xff0c 使用起来很方面

  • Arduino通过NRF24L01实现双机无线通信

    双机无线通信 文章目录 双机无线通信前言一 接线二 Arduino代码1 主机2 从机 总结 前言 无线通信对于做各种项目来说都很加分 xff0c 今天使用这个nrf模块进行无线通信 我原本是想用两个蓝牙的 xff0c 但是蓝牙有个缺点 x

  • STM32+ESP8266+机智云+DHT11数据上传

    机智云 文章目录 机智云前言一 工程的修改二 数据的上传1 标识符2 数据处理3 数据上传 三 app控制 前言 今天搞了一下机智云 xff0c 就想把温湿度发到app上去 xff0c 然后能够控制灯的开关 之前从来没有用过这个玩意 xff

  • 数据结构——线性结构（二）

    数据结构 文章目录 数据结构前言一 线性结构1 线性表2 线性表的特点 二 线性结构的存储形式1 顺序结构2 链式结构 前言 很早之前提到了数据结构 xff0c 上一篇博客简单介绍了什么是线性结构 xff0c 这篇博客简单做一个补充 常见的

  • 数据结构——顺序表（三）

    数据结构 文章目录 数据结构一 什么是顺序表二 顺序表的创建1 静态顺序表2 动态数据表 三 顺序表的初始化 销毁四 顺序表的插入1 尾插2 头插3 任意插入 总结 一 什么是顺序表 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线

  • PHP new mysqli()连接

    1 首先在mysql命令控制台新建数据库 mysql gt create database test Query OK 1 row affected 0 04 sec mysql gt use test Database changed m

  • 数据结构——链表（五）

    数据结构 96 文章目录 数据结构前言一 什么是链表二 实现单链表1 单链表的结构2 单链表的初始化3 单链表的插入4 遍历链表5 链表长度 总结 前言 接下来学习一下链表 xff0c 链表比数组用的更多 一 什么是链表 概念 xff1a

  • 数据结构——双向循环链表（八）

    数据结构 文章目录 数据结构前言一 双向循环链表初始化二 双向循环链表的插入遍历 三 双向链表的删除总结 前言 双向循环链表用的次数是最多的 xff0c 下面我们看一下双向循环链表的增删改查 一 双向循环链表初始化 双向循环链表不能出现NU

  • 数据结构——栈（九）

    数据结构 文章目录 数据结构前言一 栈的介绍二 栈的实现1 栈的结构2 栈的初始化3 进栈4 出栈5 栈的判断6 取栈顶元素7 栈的清空8 栈的销毁 总结 前言 栈是一种特殊的线性表 xff0c 只允许在固定的一端进行插入和删除元素的操作

热门标签