【数据结构】深入了解栈

在这里插入图片描述
🔥博客主页： 小羊失眠啦.
🎥系列专栏：《C语言》 《数据结构》 《Linux》《Cpolar》
❤️感谢大家点赞👍收藏⭐评论✍️

在这里插入图片描述

文章目录

  • 一、栈的基本概念
  • 二、栈实现方法的分析与选择
    • 2.1 引入
    • 2.2 顺序表实现
    • 2.3 链表实现
      • 2.3.1 单链表实现（尾为栈顶）
      • 2.3.2 单链表实现（头为栈顶）
      • 2.3.3 双向链表实现
      • 2.3.4 总结
    • 2.4 选择
  • 三、栈接口的实现
      • 📖3.1 栈的初始化
      • 📖3.2 栈的销毁
      • 📖3.3 入栈
      • 📖3.4 出栈
      • 📖3.5 读取栈顶元素
      • 📖3.6 判断栈空
      • 📖3.7 栈元素个数
      • 📖3.8 思考
  • 四、栈的完整代码及效果展示

一、栈的基本概念

栈是一种特殊的线性表。其只允许在固定的一端进行插入和删除元素的操作，进行数据的插入和删除的一端称作栈顶，另外一端称作栈底。栈不支持随机访问，栈的数据元素遵循先进后出的原则，即LIFO（Late In First Out）。

也许有人曾经听说过压栈和入栈的术语，以下是它们的定义：

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

我们结合动图来理解栈的后进先出：

img

二、栈实现方法的分析与选择

2.1 引入

我们可以使用顺序存储结构或者链式存储结构来实现栈。换句话来说，我们可以使用之前学习过的顺序表或者链表来实现栈，它们各自有自己的优缺点，下面我们就来分析分析。

2.2 顺序表实现

以下是动态顺序表实现栈的结构体声明和图示：

typedef int STDataType;
typedef struct stack
{
	STDataType* a;//指向动态开辟的空间
	int top;//栈顶所在下标，相当于元素个数
	int capacity;//顺序表容量
}ST;

在这里插入图片描述

优点：由于栈的插入和删除数据符合先进后出的原则，我们 把顺序表末端当作栈顶，则插入数据和删除数据就是尾插和尾删 。而前面我们知道 顺序表的尾插和尾删效率非常高 ，时间复杂度为O（1）。

缺点： 存在容量限制，当容量不足是需要扩容，扩容需要成本。

2.3 链表实现

2.3.1 单链表实现（尾为栈顶）

typedef struct StackNode
{
    STDataType x;//数据域
    StackNode* nest;//指针域，指向下一结点
}ST;
struct Stack
{
    ST* phead;//指向第一个结点
    ST* tail;//指向尾结点
}

在这里插入图片描述

假如我们使用链表尾当作栈顶，则对应的插入删除就是尾插和尾删。我们知道单链表的尾插和尾删要先找到链表尾，时间复杂度是O(N)。可能有人会想，那我定义一个尾指针来记录链表尾部，想法很好，但是这样虽然解决了尾插效率低的问题，但是尾删除了要找到最后一个结点，还要找到其前面的结点，由于链表单向，最终还是要遍历链表，没有什么意义。

2.3.2 单链表实现（头为栈顶）

我们知道，和顺序表相反，单链表头插和头删效率较高，时间复杂度为O（1）。我们就可以将链表头当作栈顶，这样插入就相当于头插，删除就相当于头删，如下：

img

2.3.3 双向链表实现

如果一定要使用链表以及把链表尾当作栈顶，为了解决删除需要找到尾结点的前驱结点时间效率低的问题，我们可以用双向链表来实现栈。双向链表除了后继指针还增加了前驱指针来指向上一个结点，利用这个结构可以直接得到上一个结点，无需再遍历链表，时间复杂度为O（1）。

typedef struct StackNode
{
    STDataType x;//数据域
    StackNode* nest;//后继指针域，指向下一结点
    StackNode* prev;//前驱指针域，指向上一结点
}ST;
struct Stack
{
    ST* phead;//指向第一个结点
    ST* tail;//指向尾结点
}

在这里插入图片描述

2.3.4 总结

如果 没有要求栈顶的位置，则我们还是使用单链表来实现，将头作为栈顶。这是因为双向链表比单链表的结点多占用了一个前驱指针的空间，虽然现代计算机空间已然构不成太大问题，但是能省则省。
如果题目要求栈顶在链表尾的话，那还是老老实实用双向链表实现吧。
使用链表的缺点就是每次插入都要malloc新结点，会消耗一定的时间成本。

2.4 选择

我们推荐采用顺序表来实现对栈的操作，原因如下：

  1. 栈的特性完美利用了顺序表尾插尾删效率高的特性，虽然需要扩容，但是链表创建结点也同样需要成本，而 顺序表扩容频率不像链表一样如此频繁。
  2. 我们知道CPU与主存速度上存在巨大差距，为了提高效率，CPU和主存之间还存在着cache高速缓存。 CPU访问cache的速度是快于主存的。每次CPU取数据时会访问cache看看存不存在所需的数据，如果不存在才会访问主存，然后将数据所在的内存块加载到cache中。由于顺序表空间是连续的，根据cache的空间局部性原理，采用顺序表 cache的命中率会高于链表，效率高。

三、栈接口的实现

📖3.1 栈的初始化

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

📖3.2 栈的销毁

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

📖3.3 入栈

由于栈只允许在固定的一端插入，我们又将末端当作栈顶，因此入栈就是尾插。而顺序表的尾插我们已经很清楚了，往栈顶所在下标放入数据，然后栈顶下标加1即可。效果和代码如下：

img

void STPush(ST* ps, STDataType x)
{
	assert(ps);
	if (ps->capacity == ps->top)
	{
		int newcapacity = ps->capacity == 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.4 出栈

和入栈一样，出栈也只在固定的一端进行。入栈是尾插，则出栈就是尾删。而我们用顺序表来实现栈，因此尾删只需要将栈顶退后一位即可。

这里有人可能会将栈顶的元素置0然后再将栈顶位置后退一位。实际上这种方法并不可取，有以下两种原因：

  1. 如果栈顶的元素本身就是0，那我们的行为就失去了意义。
  2. 栈的元素类型不一定是整形，如果是浮点型或者结构体，我们赋值为0显然是不妥的。

img

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

📖3.5 读取栈顶元素

直接根据栈顶所在的下标得到栈顶元素，如下：

在这里插入图片描述

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

📖3.6 判断栈空

在我们设计的栈结构中，top实际上就等价于元素个数，通过判断top是否为0就可以知道栈是否为空。我们使用了C语言stdbool.h头文件中的bool类型，其只能用来存放true(1)和false(0)两个值，分别代表真和假。代码如下：

bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}

📖3.7 栈元素个数

根据我们构造的栈结构体，栈顶top的值就是栈的元素个数，直接返回即可：

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

📖3.8 思考

会不会有人会有以下思考：

  1. 求栈顶元素，判空，求元素个数都是用一行直接返回，这些接口会不会有些许多余，直接访问结构体相应成员不就好了？
  2. 为什么没有实现查找，打印，修改等接口?

下面我们来分析一下：

  • 我们要知道，数据结构的实现方式多种多样，在本文我们将栈元素个数作为栈顶的下标，那可不可以将最后一个元素的下标作为栈顶下标呢？实际上完全可以。那么就会出现一个问题，如果我们使用别人已经封装好的栈，我们要怎么知道栈顶元素下标是top还是top-1呢？我们要怎么知道是top=0为空还是top=-1为空呢？我们要怎么知道元素个数是top还是top+1呢？我们完全不知道，只有设计者才知道，因此设计者往往会将这些功能再封装成函数，供我们直接调用。

  • 这是因为栈是一种限制型数据结构，其不支持随机访问，只允许在固定的一端(栈顶)进行插入和删除操作，不允许在其他的位置进行任何操作。因此，栈不存在查找，打印，修改等对除栈顶之外的位置进行操作的接口，否则会破坏栈的特性。为了遵循栈的特性，我们就不实现这些接口。

四、栈的完整代码及效果展示

按照以往惯例，我们采用多文件编写的形式，将上述接口的定义实现放在Stack.c文件中，然后将接口的声明和结构体的定义放于Stack.h头文件中，以达到封装的效果。这样我们如果需要使用栈，就只需要在文件中包含对应的头文件Stack.h就可以使用我们上面定义的各种接口。以下为本文实现的栈完整代码以及效果展示：
Stack.h

#pragma once

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

//#define N 10
//struct Stack
//{
//	int a[N];
//	int top;
//};

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

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->capacity == ps->top)
	{
		int newcapacity = ps->capacity == 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

#define _CRT_SECURE_NO_WARNINGS 1
//test.c文件，用于测试
#include"Stack.h"

void test1()
{
    ST st;
    //初始化
    STInit(&st);
    //求元素个数
    printf("入栈前栈的元素个数为:%d\n", STSize(&st));
    //入栈
    STPush(&st, 1);
    STPush(&st, 2);
    STPush(&st, 3);
    STPush(&st, 4);
    printf("入栈后栈的元素个数为:%d\n", STSize(&st));
    //由于无法遍历打印，我们就交替使用 求栈顶元素-出栈 来显示栈中元素
    printf("栈中元素:> ");
    while (!STEmpty(&st))//栈不为空则继续
    {
        //求栈顶元素
        printf("%d ", STTop(&st));
        //出栈
        STPop(&st);
    }
    //全部出栈
    printf("\n全部出栈后栈的元素个数为:%d\n", STSize(&st));
    //销毁
    STDestroy(&st);
}

int main()
{
    test1();
    return 0;
}

最终效果：
在这里插入图片描述

本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言，小羊一定认真修改，写出更好的文章~~

在这里插入图片描述

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

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

相关文章

全国犯罪人数大数据可视化平台【可视化项目案例-08】

全国犯罪人数大数据可视化平台【可视化项目案例-08】

🎉🎊🎉 你的技术旅程将在这里启航！ 🚀🚀 本文选自专栏：可视化技术专栏100例 可视化技术专栏100例，包括但不限于大屏可视化、图表可视化等等。订阅专栏用户在文章底部可下载对应案例源码以供大家深入的学习研究。 🎓 每一个案例都会提供完整代码和详细的讲解，不…
阅读更多...
将铜互连扩展到2nm的研究

将铜互连扩展到2nm的研究

晶体管尺寸在3nm时达到临界点&#xff0c;纳米片FET可能会取代finFET来满足性能、功耗、面积和成本目标。同样&#xff0c;正在评估2nm铜互连的重大架构变化&#xff0c;此举将重新配置向晶体管传输电力的方式。 芯片制造商也可能会在2nm节点开始用钌或钼在一定程度上取代铜。…
阅读更多...
网上第一批购买大王卡的用户都怎么样了？

网上第一批购买大王卡的用户都怎么样了？

近日&#xff0c;小编看到有网友在网上发帖询问&#xff0c;网上第一批购买大王卡的用户都怎么样了&#xff1f;一时间得到纷纷得到回应。 小编也汇总了一些回复&#xff0c;大家可以看一看&#xff1a; 因为大王卡是一张定向流量卡&#xff0c;所以在使用时很多软件都是需要额…
阅读更多...
列出目录内最大十个文件并排序

列出目录内最大十个文件并排序

在Linux中&#xff0c;可以使用以下命令列出目录内最大的十个文件并排序&#xff1a; find ./ -type f -print0 | xargs -0 du -h | sort -rh | head -n 10 find ./ -type f -print0: find命令用于在指定目录下查找文件。这里&#xff0c;我们在当前目录下查找所有的文件&…
阅读更多...
在AI时代提升个人晋升力的策略

在AI时代提升个人晋升力的策略

✍️作者简介&#xff1a;沫小北/码农小北&#xff08;专注于Android、Web、TCP/IP等技术方向&#xff09; &#x1f433;博客主页&#xff1a;沫小北/码农小北 开源中国、稀土掘金、51cto博客、博客园、知乎、简书、慕课网、CSDN &#x1f514;如果文章对您有一定的帮助请&…
阅读更多...
Java map 详解 - 用法、遍历、排序、常用API等

Java map 详解 - 用法、遍历、排序、常用API等

概要&#xff1a; java.util 中的集合类包含 Java 中某些最常用的类。最常用的集合类是 List 和 Map。 Map 提供了一个更通用的元素存储方法。Map 集合类用于存储元素对&#xff08;称作“键”和“值”&#xff09;&#xff0c;其中每个键映射到一个值。 本文主要介绍java m…
阅读更多...
cesium 自定义顶点属性

cesium 自定义顶点属性

// 创建平面const planeGeometry new Cesium.PlaneGeometry({vertexFormat: Cesium.VertexFormat.POSITION_AND_ST, // 位置和UV});const geometry Cesium.PlaneGeometry.createGeometry(planeGeometry);// [3]-----[2]// | |// [0]-----[1]geometry.attributes.color…
阅读更多...
Echart 极坐标 方位距离图 图标符号旋转以及大小 颜色渐变

Echart 极坐标 方位距离图 图标符号旋转以及大小 颜色渐变

背景&#xff1a; 参与一个交互式图表项目&#xff0c;客户有一个极坐标对比需求&#xff0c;展示不同方位不同距离的不同类型的指标数据。具体到属性字段则是&#xff1a; 来源、距离、方位、ID、旋转角度、大小 先看效果图&#xff1a; 技术点&#xff1a; 图例说明&#…
阅读更多...
二、服务拆分及远程调用

二、服务拆分及远程调用

目录 一、注意事项&#xff1a; 1.单一职责: 2.数据独立: 3.面向服务&#xff1a; 二、服务拆分例子&#xff1a; 三、远程调用例子&#xff1a; 微服务调用方式&#xff1a; 四、提供者与消费者 服务调用关系&#xff1a; 一、注意事项&#xff1a; 1.单一职责: 不同…
阅读更多...
新用户可一次性买3年的优惠云服务器，看到价格泪奔了！

新用户可一次性买3年的优惠云服务器，看到价格泪奔了！

本文将综合介绍腾讯云主推的4款云服务器配置及其价格&#xff0c;并重点强调其特点和优势。其中两款3年的优惠云服务器&#xff0c;非常值得新用户选择&#xff01; 一、入门级配置&#xff1a;2核4G 5M带宽&#xff0c;一年166元 这款入门级配置适合初学者或者对资源需求不高…
阅读更多...
淘宝API接口开发系列，获取商品详情，按关键词搜索商品，拍立淘，商品评论销量商品类目，买家卖家订单接口等演示案例

淘宝API接口开发系列，获取商品详情，按关键词搜索商品，拍立淘，商品评论销量商品类目，买家卖家订单接口等演示案例

关键词推荐API接口通过提供相关的关键词推荐&#xff0c;能够帮助用户更快捷地搜索、改善用户体验&#xff0c;同时也对于SEO优化、广告投放、内容创作和个性化推荐等方面有着重要的作用。 item_search-按关键字搜索淘宝商品 公共参数 名称类型必须描述keyString是调用key&am…
阅读更多...
一文简单聊聊protobuf

一文简单聊聊protobuf

目录 基本介绍 原理 同类对比 为什么要使用protobuf? 基本介绍 protobuf的全称是Protocol Buffer&#xff0c;是Google提供的一种数据序列化协议。Protocol Buffers 是一种轻便高效的结构化数据存储格式&#xff0c;可以用于结构化数据序列化&#xff0c;很适合做数据存储…
阅读更多...
Vue 3.0 + vite + axios+PHP跨域问题的解决办法

Vue 3.0 + vite + axios+PHP跨域问题的解决办法

最后一个Web项目&#xff0c;采用前后端分离。 前端&#xff1a;Vue 3.0 viteelement plus 后端&#xff1a;PHP 运行时前端和后端是两个程序&#xff0c;前端需要时才向后端请求数据。由于是两个程序&#xff0c;这就会出现跨域问题。 比如前端某个地方需要请求的接口如下…
阅读更多...
2023年度实用Figma插件大放送！

2023年度实用Figma插件大放送！

根据统计&#xff0c;自2018年以来&#xff0c;Sketch的使用率已经从42%下降到31%&#xff0c;而Figma的使用率已经从12%上升到26%。为什么Figma如此受欢迎&#xff1f;为什么有越来越多的设计师倾向于使用Figma做设计&#xff1f;其实Figma现在除了给用户带来的丝滑的操作体验…
阅读更多...
KT148A语音芯片的下载用的是串口，测试可以直接串口发指令控制吗

KT148A语音芯片的下载用的是串口，测试可以直接串口发指令控制吗

一、问题简介 KT148A语音芯片的下载用的是串口&#xff0c;那我实际测试是不是可以直接串口发指令测试控制&#xff1f;就不用单独写程序去模拟一线串口的时序了 详细描述 首先看一下KT148A芯片的参考设计原理图&#xff1a;其中芯片的2脚和3脚就是串口&#xff0c;注意下载语…
阅读更多...
跨国企业在数据跨境传输中应该知道的五大要点

跨国企业在数据跨境传输中应该知道的五大要点

随着全球化的加速和数字化经济的蓬勃发展&#xff0c;数据跨境传输已经成为跨国企业日常业务运营中的重要环节。然而&#xff0c;在数据跨境传输过程中&#xff0c;企业需要关注一系列问题&#xff0c;以确保遵守法律法规、保障数据安全、提高传输效率并降低风险。本文将探讨数…
阅读更多...
Office LTSC 2021 v16.80

Office LTSC 2021 v16.80

Office 2021 for Mac是一款针对Mac用户推出的办公软件套装&#xff0c;包括了Word、Excel、PowerPoint、Outlook等常用的办公软件。相比于之前的版本&#xff0c;Office 2021 for Mac也进行了一些更新和改进&#xff0c;以提高用户的使用体验和效率。 以下是Office 2021 for M…
阅读更多...
Python使用Mechanize库完成自动化爬虫程序

Python使用Mechanize库完成自动化爬虫程序

Mechanize是一个Python第三方库&#xff0c;它可以模拟浏览器的行为&#xff0c;实现自动化的网页访问、表单填写、提交等操作。下面是一个使用Mechanize库编写的爬虫的例子&#xff0c;它可以爬取百度搜索结果页面的标题和链接&#xff1a; import mechanize from bs4 import …
阅读更多...
宝马所有发动机号码的位置以及型号说明

宝马所有发动机号码的位置以及型号说明

每个汽车制造商都会为自己生产的汽车底盘和发动机分配一个内部代码&#xff0c;以标识研发和生产项目&#xff0c;而宝马对这些底盘代码和发动机代码更是规划的井井有条&#xff0c;比如发动机有M、N、B、S、P或W等代码标识&#xff0c;而底盘和车身则有E、F、G或i等代码标识。…
阅读更多...
Nginx 版本信息泄露解决方案

Nginx 版本信息泄露解决方案

Nginx 【CVE-2021-23017;CVE-2022-41742】 【影响】 攻击者可能使用泄露的版本信息来确定该版本服务器有哪些安全漏洞&#xff0c;据此展开进一步的攻击。以下是百度的请求示例&#xff0c;也是有版本泄露&#xff1a; 【解决方案】 在Server节点增加以下配置&#xff1a; #…
阅读更多...
最新文章

Copyright @ 2022~2023