【数据结构】栈详解

目录

  • 1. 前言
  • 2. 栈
    • 2.1 栈的概念及结构
    • 2.2 如何实现栈
    • 2.3 数组栈实现
      • 2.3.1 top怎么确定
      • 2.3.2 栈顶插入
        • 2.3.2.1 栈顶插入分析
        • 2.3.2.2 栈顶插入代码实现
      • 2.3.3 栈顶删除
      • 2.3.4 判空
        • 2.3.4.1 分析
        • 2.3.4.2 代码实现
      • 2.3.5 栈的元素个数
      • 2.3.6 栈销毁
      • 2.3.7 栈访问数据
  • 3. 源代码
    • 3.1 Stack.h
    • 3.2 Stack.c
    • 3.3 test.c

1. 前言

在前面我们一起了解的数据结构有顺序表和链表，这次来介绍栈。
与顺序表和链表相同的是，栈也是常见的数据结构。而与前面两种不同的是，它在农村种的存储，接下来让我们一起来学习一下。

2. 栈

2.1 栈的概念及结构

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

压栈：栈的插入操作叫做进栈/压栈/入栈，入数据在栈顶。

出栈：栈的删除操作叫做出栈。出数据也在栈顶。
在这里插入图片描述

2.2 如何实现栈

在这里插入图片描述
那该如何实现栈呢？
第一种使用数组栈
第二种使用链式栈

链表实现又分为双向链表，和单链表。
双向链表实现，栈顶可以是尾，也可以是头。
单链表实现，栈顶只能是头。
在这里插入图片描述
如果只选择一种来实现，那必然是数组，虽然有扩容，但不是频繁扩容。还有另外一个优势，它访问数据，CPU高速缓存命中率比较高，访问第一个，后面都在缓存了。

2.3 数组栈实现

2.3.1 top怎么确定

我们需要考虑top怎么确定？
如果top给0，那么表示的是栈顶还是栈顶位置的下一个？
在这里插入图片描述

如果空的时候top给的是0，那么插入一个数据之后top也是0，因为top指向栈顶。
此时就出现了歧义。top==0是一个元素还是空？区分不开。

那该怎么区分呢？
第一种如果top指向栈顶元素，那么top初始时给-1。

在这里插入图片描述
这种插入数据时：
要先加加top，再在这个位置赋值。
在这里插入图片描述

第二种指向栈顶元素的下一个。
此时top初始时就为0。
在这里插入图片描述
这种插入数据时：
要先在这个位置赋值，再加加top。
在这里插入图片描述

这里插入就取决于怎么初始化栈。

选择第二种来实现代码，这种更简单。

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

	pst->a = NULL;
	pst->capacity = 0;
	pst->top = 0;//第二种
}

2.3.2 栈顶插入

2.3.2.1 栈顶插入分析

插入的代码非常简单：

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

但是在插入之前，要先判断一下栈有没有满，满的化要进行扩容。

if (pst->top == pst->capacity)

但我们要初始时候有没有给空间，如果有直接扩两倍，没有就给初始值4。
使用一个三目表达式

int newcapacity = pst->capacity == 0 ? 4 : pst->capacity * 2;

如果没有开空间，就直接返回或者结束程序。

if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
2.3.2.2 栈顶插入代码实现
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->a, sizeof(STDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}

		pst->a = tmp;
		pst->capacity = newcapacity;
	}

	pst->a[pst->top] = x;
	pst->top++;
}

2.3.3 栈顶删除

删除很简单，直接top–，就行，但减减之前判断一下top是不是0，加一个断言就行。
代码实现：

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

2.3.4 判空

2.3.4.1 分析

判空这里得看刚开始时：初始时top为0，就要判断top==0。初始为-1，那么就要判断top==-1。
可以用if来判断：

if (pst->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}

但是有个更简单的：bool类型返回就是真假，利用返回值当结果就行，直接返回pst->top == 0。

2.3.4.2 代码实现

代码实现：

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

	/*if (pst->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}*/

	return pst->top == 0;
}

2.3.5 栈的元素个数

如果top是指向栈顶元素的下一个，那么元素个数就是top。
如果top就是指向栈顶，那么元素个数就是top+1。
在这里插入图片描述

代码实现：

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

	return pst->top;
}

2.3.6 栈销毁

直接将元素都free掉，再把它们都置为空。把栈顶和栈空间都置为0。

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

	free(pst->a);
	pst->a = NULL;
	pst->top = pst->capacity = 0;
}

2.3.7 栈访问数据

因为栈是后进先出，所以栈不能随便打印。
那怎么打印呢？
判断栈是否为空，然后从栈顶开始访问。
访问了栈顶元素，要想访问下一个就要先将栈顶元素弹出，直到栈为空，就结束。

代码实现：

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

3. 源代码

3.1 Stack.h

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


typedef int STDataType;

typedef struct Stack
{
	int* 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);

3.2 Stack.c

#include"Stack.h"

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

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

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

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

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

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

		pst->a = tmp;
		pst->capacity = newcapacity;
	}

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

	/*if (pst->top == 0)
	{
		return true;
	}
	else
	{
		return false;
	}*/

	return pst->top == 0;
}

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

	return pst->top;
}

3.3 test.c

#include"Stack.h"


int main()
{
	ST s;
	STInit(&s);
	STPush(&s, 1);
	STPush(&s, 2);
	STPush(&s, 3);
	printf("%d ", STTop(&s));
	STPop(&s);
	printf("%d ", STTop(&s));
	STPop(&s);

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

	//    一     对     多
	// 入栈顺序  --  出栈顺序
	while (!STEmpty(&s))
	{
		printf("%d ", STTop(&s));
		STPop(&s);
	}
	printf("\n");

	return 0;
}

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

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

相关文章

苍穹外卖—解决前端时间属性显示问题

苍穹外卖—解决前端时间属性显示问题

项目场景&#xff1a; 点击员工管理 出现显示时间属性问题 输入员工姓名为zhangsan 现实的时间属性是数组类型 问题描述 提示&#xff1a;这里描述项目中遇到的问题&#xff1a; 例如&#xff1a;数据传输过程中数据不时出现丢失的情况&#xff0c;偶尔会丢失一部分数据 APP …
阅读更多...
手把手带你在AutoDL上部署InternLM-Chat-7B Transformers

手把手带你在AutoDL上部署InternLM-Chat-7B Transformers

手把手带你在AutoDL上部署InternLM-Chat-7B Transformers 调用 项目地址&#xff1a;https://github.com/KMnO4-zx/self_llm.git 如果大家有其他模型想要部署教程&#xff0c;可以来仓库提交issue哦~ 也可以自己提交PR&#xff01; InternLM-Chat-7B Transformers 部署调用 环…
阅读更多...
【代数学习题4.2】从零理解范数与迹 —— 求数域元素的范数与迹

【代数学习题4.2】从零理解范数与迹 —— 求数域元素的范数与迹

从零理解范数与迹 —— 求数域元素的范数与迹 写在最前面题目解答 2. 范数 N N N思路求解过程python求解 3. 数域 K K K 的范数 N K N_K NK​思路求解过程Python求解分析解题步骤 4. 迹 T T T求解过程共轭元素计算迹 python求解分析解题步骤 5. 数域 K K K 的迹 T K T_K …
阅读更多...
利用 React 和 Bootstrap 进行强大的前端开发

利用 React 和 Bootstrap 进行强大的前端开发

文章目录 介绍React 和 Bootstrap设置环境使用 Bootstrap 创建 React 组件React-Bootstrap 组件结论 介绍 创建响应式、交互式和外观引人入胜的 Web 界面是现代前端开发人员的基本技能。幸运的是&#xff0c;借助 React 和 Bootstrap 等工具的出现&#xff0c;制作这些 UI 变得…
阅读更多...
算法设计与分析复习--回溯法（二）

算法设计与分析复习--回溯法（二）

文章目录 上一篇0-1背包问题图着色问题n皇后问题下一篇 上一篇 算法设计与分析复习–回溯&#xff08;一&#xff09; 0-1背包问题 问题描述&#xff1a;给定n中物品和一个背包。物品 i i i 的重量是 w i w_i wi​ &#xff0c;其价格为 v i v_i vi​ , 背包容量为 c c …
阅读更多...
speech studio-神经网络定制自己的声音

speech studio-神经网络定制自己的声音

Speech Studio - 神经网络定制声音 - 概述 (microsoft.com)
阅读更多...
Java，数据结构与集合源码，数据结构概述

Java，数据结构与集合源码，数据结构概述

目录 数据结构概念&#xff1a; 数据结构的研究对象&#xff1a; 研究对象一&#xff0c;数据间逻辑关系&#xff1a; 研究对象二&#xff0c;数据的存储结构&#xff08;或物理结构&#xff09;&#xff1a; 研究对象三&#xff1a;运算结构 数据结构的相关介绍&#xff…
阅读更多...
C++初阶--类型模板

C++初阶--类型模板

文章目录 泛型编程函数模板使用通用加法函数多模板参数必须用实例化 函数模板的原理类模板使用 注意事项 泛型编程 先看一个例子&#xff1a; 这是一些对于Swap重载的函数&#xff0c;区别是类型不同&#xff1b; 虽然能够重载使用&#xff0c;但代码复用率比较低&#xff0c…
阅读更多...
C++11新特性 变参模板、完美转发和emplace

C++11新特性 变参模板、完美转发和emplace

#include <iostream> #include <vector> #include <deque> #include <list> #include <algorithm> using namespace std;class student { public:student() {cout << "无参构造函数被调用!" << endl;}student(int age, st…
阅读更多...
C++静态链接库的生成以及使用

C++静态链接库的生成以及使用

目录 一.前言二.生成静态链接库三.使用静态链接库四.其他 一.前言 这篇文章简单讨论一下VS如何生成和使用C静态链接库&#xff0c;示例使用VS2022环境。 二.生成静态链接库 先创建C项目-静态库 然后将默认生成的.h和.cpp文件清理干净&#xff0c;当然你也可以选择保留。 然…
阅读更多...
Spring：IoC，AOP的简单理解与使用

Spring：IoC，AOP的简单理解与使用

IoC容器 IoC &#xff0c;Spring全家桶各个功能模块的基础&#xff0c;是创建对象的容器。 IoC概念 控制反转&#xff0c;将对象的创建进行反转&#xff0c;常规情况下对象由开发者手动创建&#xff0c;而使用IoC不再需要创建对象&#xff0c;由IoC容器根据需求自动创建项目…
阅读更多...
2023年【上海市安全员C3证】考试内容及上海市安全员C3证复审考试

2023年【上海市安全员C3证】考试内容及上海市安全员C3证复审考试

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 上海市安全员C3证考试内容是安全生产模拟考试一点通总题库中生成的一套上海市安全员C3证复审考试&#xff0c;安全生产模拟考试一点通上上海市安全员C3证作业手机同步练习。2023年【上海市安全员C3证】考试内容及上海…
阅读更多...
MyCAT2的主从配置

MyCAT2的主从配置

http://t.csdnimg.cn/KzwDy&#xff08;mysql主从搭建&#xff09; 前提&#xff0c;先搭建好MySQL的主从配置&#xff0c;登录MyCAT 2在MyCAT2里面操作&#xff0c;也就是连接8066这个端口。 一、创建数据源 ​​​​​​​1.创建数据源 添加读写的数据源 /* mycat:createD…
阅读更多...
U4_1：图论之DFS/BFS/TS/Scc

U4_1：图论之DFS/BFS/TS/Scc

文章目录 一、图的基本概念二、广度优先搜索&#xff08;BFS&#xff09;记录伪代码时间复杂度流程应用 三、深度优先搜索&#xff08;DFS&#xff09;记录伪代码时间复杂度流程时间戳结构BFS和DFS比较 四、拓扑排序一些概念有向图作用拓扑排序 分析伪代码时间复杂度彩蛋 五、强…
阅读更多...
阿里云oss存储文件上传功能实现（保姆级教程）

阿里云oss存储文件上传功能实现（保姆级教程）

先登录&#xff1a; 点击进入控制台 点击左上角导航栏按钮 搜索oss&#xff0c;点击进入 进入之后点击立即开通oss按钮&#xff0c;开通之后点击下图立即创建&#xff0c;弹出创建Bucket 填上Bucket名称&#xff0c;读写权限改为公共读。其他不变点击确定创建&#xff0c;完成…
阅读更多...
uniapp、微信小程序返回上页面刷新数据

uniapp、微信小程序返回上页面刷新数据

目录 前言&#xff1a; 方法1&#xff1a; 方法2&#xff1a; 方法3&#xff1a; 前言&#xff1a; 返回上页面刷新数据这个功能主要用于在当前页面点击跳转到另一个页面之后&#xff0c;在另一个页面对数据进行了操作&#xff0c;比如&#xff1a;阅读量&#xff0c;然后返…
阅读更多...
计算机组成原理-主存储器与CPU的连接

计算机组成原理-主存储器与CPU的连接

文章目录 知识总览单块存储芯片与CPU的连接位扩展&#xff08;存储字的位数&#xff09;字扩展&#xff08;存储字数&#xff09;关于线选法和片选法字位同时扩展总结补充&#xff1a;译码器 知识总览 单块存储芯片与CPU的连接 数据总线&#xff0c;地址总线&#xff0c;片选线…
阅读更多...
Web 自动化神器 TestCafe—页面基本操作篇

Web 自动化神器 TestCafe—页面基本操作篇

前 言 Testcafe是基于node.js的框架&#xff0c;以操作简洁著称&#xff0c;是web自动化的神器 今天主要给大家介绍一下testcafe这个框架和页面元素交互的方法。 一、互动要求 使用 TestCafe 与元素进行交互操作&#xff0c;元素需满足以下条件&#xff1a;☟ 元素在 body 页…
阅读更多...
迅为RK3568开发板学习之Linux驱动篇第十三期输入子系统

迅为RK3568开发板学习之Linux驱动篇第十三期输入子系统

驱动视频全新升级&#xff0c;并持续更新~更全&#xff0c;思路更科学&#xff0c;入门更简单。 迅为基于iTOP-RK3568开发板进行讲解&#xff0c;本次更新内容为第十三期&#xff0c;主要讲解输入子系统&#xff0c;共计24 讲。 关注B站&#xff1a;北京迅为电子&#xff0c;在…
阅读更多...
Parallel Diffusion Models of Operator and Image for Blind Inverse Problems

Parallel Diffusion Models of Operator and Image for Blind Inverse Problems

盲逆问题算子和图像的并行扩散模型 论文链接&#xff1a;https://arxiv.org/abs/2211.10656 项目链接&#xff1a;https://github.com/BlindDPS/blind-dps Abstract 在正向算子已知的情况下(即非盲)&#xff0c;基于扩散模型的逆问题求解器已经展示了最先进的性能。然而&…
阅读更多...
最新文章

Copyright @ 2022~2023