目录

引言

1.栈的概念和结构

栈的核心概念

栈的结构

2.栈的实现

2.1栈的实现方式

2.2栈的功能

2.3栈的声明

1.顺序栈

2。链式栈

2.4栈的功能实现

1.栈的初始化

2.判断栈是否为空

3.返回栈顶元素

4.返回栈的大小

5.元素入栈

6.元素出栈

7.打印栈的元素

8.销毁栈

3.顺序栈和链式栈的对比

 适用场景

总结

4.完整代码

1.顺序表

2.链式表

结束语


引言

在学习完链表之后,我们接下来学习数据结构——栈。

学习目标:

  • 1.栈的概念和结构
  • 2.栈的实现
  • 3.顺序栈和链式栈的对比

1.栈的概念和结构

栈(Stack)是一种线性数据结构,其核心特点是 “后进先出”(Last In, First Out,LIFO)—— 即最后入栈的元素会最先被弹出。这种特性类似于日常生活中的 “叠盘子”:最后叠上去的盘子,会被最先拿走。

栈的核心概念

  1. 入栈(Push):向栈顶添加元素。
  2. 出栈(Pop):从栈顶移除并返回元素(栈为空时无法出栈)。
  3. 栈顶(Top):栈中最上方的元素(最后入栈的元素)。
  4. 栈底(Bottom):栈中最下方的元素(最先入栈的元素)。
  5. 栈空(Empty):栈中没有任何元素的状态。
  6. 栈的大小(Size):栈中元素的数量。

栈的结构

栈的结构可以抽象为一个 “容器”,元素只能从一端(栈顶)进行插入和删除操作,另一端(栈底)是固定的。

“后进先出”(Last In, First Out,LIFO):

栈顶(Top):栈顶是栈中最后添加(push)元素的位置,也是最先被移除(pop)或查看(peek/top)的元素所在的位置。在栈的所有操作中,无论是添加、删除还是查看元素,都是针对栈顶进行的。因此,栈顶是栈中最活跃、最频繁被访问的位置。

栈底(Bottom):栈底是栈中最早被添加进去的元素所在的位置,也是栈中唯一一个固定不变的位置(除非整个栈被清空)。在栈的常规操作中,栈底元素不会被直接访问,除非是将整个栈的内容倒序输出或者栈被完全清空。因此,栈底在栈的操作中扮演的是一个相对静态的角色。

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

出栈:栈的删除操作叫做出栈,出数据也在栈顶。

  • 在计算机领域,栈有着广泛应用。例如,在编程语言中,函数调用时会使用栈来管理局部变量和返回地址。当一个函数被调用时,其相关的信息(如参数、局部变量等)会被压入栈中,函数执行完毕后,这些信息会从栈中弹出。此外,表达式求值、括号匹配等问题也常借助栈来解决。

2.栈的实现

2.1栈的实现方式

栈可以通过两种常见的数据结构实现:

  1. 数组实现(顺序栈)

    • 用数组存储元素,栈顶对应数组的最后一个索引。
    • 入栈:在数组尾部添加元素(时间复杂度 O (1))。
    • 出栈:删除数组尾部元素(时间复杂度 O (1))。
    • 缺点:数组大小固定,可能出现溢出(需动态扩容)。
  2. 链表实现(链式栈)

    • 用链表的头节点作为栈顶,每次操作头节点。
    • 入栈:在链表头部插入新节点(时间复杂度 O (1))。
    • 出栈:删除链表头部节点(时间复杂度 O (1))。
    • 优点:大小灵活,无需考虑扩容。

相对而言数组的结构实现更优,因为数组在尾上插入数据的代价比较小。

2.2栈的功能

栈的数据结构要实现如下功能:

1.栈的初始化。
2.判断栈是否为空。
3.返回队头元素。
4.返回栈的大小。
5.元素入栈。

6.元素出栈。
7.打印栈的元素。
8.销毁栈。

2.3栈的声明

1.顺序栈

顺序栈的声明需要一个指向一块空间的指针a,指向栈顶元素的top,以及标志栈空间大小的capacity。

typedef int STDataType;typedef struct STDataType
{STDataType* a;int top;int capacity;
}ST;
2.链式栈

链式栈的声明只需要一个top指针,以及栈的容量capacity。

当然这里需要链表的声明。

typedef int STDataType;typedef struct SListNode
{STDataType data;struct SListNode* next;
}SLTNode;typedef struct Stack
{// 指向栈顶节点的指针SLTNode* top;int size;
}ST;

2.4栈的功能实现

1.栈的初始化

顺序栈和链式栈都可以先初始为NULL。

(1)顺序栈

顺序栈可以将top设置为-1,capacity设置为0。

代码如下:

//栈的初始化
void STInit(ST* st)
{assert(st);st->a = NULL;st->top = -1;st->capacity = 0;
}
(2)链式栈

链式栈将size设置为0,top设置为NULL。

//栈的初始化
void STInit(ST* st)
{assert(st);st->size = 0;st->top = NULL;
}
2.判断栈是否为空

判断栈是否为空只需要判断top的指向。

(1)顺序栈

当top=-1则为空。

代码如下:

//判空
bool STEmpty(ST* st)
{assert(st);return st->top == -1;
}
(2)链式栈

判断top是否指向NULL。

//判空
bool STEmpty(ST* st)
{return (st->top == NULL);
}
3.返回栈顶元素
(1)顺序栈
//取出栈顶数据
STDataType STTop(ST* st)
{assert(st);// 断言确保栈不为空(即栈顶索引不小于0)assert(st->top >= 0);return st->a[st->top];
}
(2)链式栈
//取出栈顶数据
STDataType STTop(ST* st)
{assert(st);assert(!STEmpty(st));return st->top->data;
}
4.返回栈的大小
(1)顺序栈

由于在一开始将top设置为-1,需要top+1才能符合需要。

代码如下:

//获取数据个数
STDataType STSize(ST* st)
{assert(st);return st->top + 1;
}
(2)链式栈
//获取数据个数
STDataType STSize(ST* st)
{return st->size;
}
5.元素入栈

注意:入栈需要检查空间是否足够。

(1)顺序栈

由于top设置的是-1,因此需要先腾出空间然后再将新元素x放在栈顶。

代码如下:

//入栈
void STPush(ST* st, STDataType x)
{assert(st);// 注意:由于top初始化为-1,所以满的条件是top == capacity - 1if (st->top == st->capacity - 1){// 如果栈已满,则扩展栈的容量int newcapacity = st->capacity == 0 ? 4 : st->capacity * 2;STDataType* tmp = (STDataType*)realloc(st->a, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail:");return;}st->a = tmp;st->capacity = newcapacity;}// 增加栈顶索引,为新元素腾出空间st->top++;// 将新元素x存储在栈顶位置st->a[st->top] = x;
}
(2)链式栈
//入栈
void STPush(ST* st, STDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail:");return;}// 新节点的next指向原来的栈顶newnode->next = st->top;// 设置新节点的数据newnode->data = x;// 更新栈顶为新节点st->top = newnode;st->size++;
}
6.元素出栈

(1)顺序栈
//出栈
void STPop(ST* st)
{assert(st);assert(st->top >= 0);st->top--;
}

(2)链式栈

//出栈
void STPop(ST* st)
{assert(st);assert(!STEmpty(st));// 获取栈顶节点的下一个节点SLTNode* next = st->top->next;free(st->top);// 更新栈顶指针,使其指向新的栈顶节点st->top = next;st->size--;
}
7.打印栈的元素
(1)顺序栈
//栈的打印
void STPrint(ST* st)
{assert(st);assert(!STEmpty(st));// 从栈顶开始打印,直到栈底(但不包括索引-1)for (int i = st->top; i >= 0; i--){printf("%d ", st->a[i]);}
}
(2)链式栈
//栈的打印
void STPrint(ST* st)
{assert(st);assert(!STEmpty(st));for (SLTNode* top = st->top; top != NULL; top = top->next){printf("%d ", top->data);}
}
8.销毁栈
(1)顺序栈
//栈的销毁
void STDestory(ST* st)
{assert(st);free(st->a);st->a = NULL;st->capacity = 0;st->top = -1;
}
(2)链式栈
//栈的销毁
void STDestory(ST* st) 
{assert(st);SLTNode* top = st->top;while (top != NULL){SLTNode* next = top->next;free(top);top = next;}st->size = 0;
}

3.顺序栈和链式栈的对比

顺序栈链式栈
数据结构使用动态数组实现,元素在物理内存中连续存储使用链表实现,元素通过节点和指针连接,内存空间不连续
内存管理栈空间不足时可动态扩容,释放整个栈时一次性释放内存节点内存单独分配和释放,需要遍历链表以释放所有节点内存
时间效率可以通过数组下标直接访问栈内任意位置的元素,但是这不符合栈的定义由于每次都需要扩容操作,所以效率略比顺序栈低
空间效率顺序栈的扩容较大可能会造成空间的浪费内存使用相对灵活,但每个节点需要额外存储指针

优缺点对比

顺序栈链式栈
优点1. 内存连续,缓存利用率高(局部性原理);
2. 实现简单,操作高效(无指针操作)。
1. 无需预分配空间,大小动态调整;
2. 不会出现栈溢出(除非内存耗尽)。
缺点1. 初始化时需确定容量,可能溢出或浪费空间;
2. 动态扩容时有性能开销。
1. 每个节点需额外存储指针,空间开销略大;
2. 内存不连续,缓存利用率较低。

 适用场景

  • 顺序栈
    适用于元素数量已知或变化不大的场景,例如:

    • 表达式求值(元素数量有限);
    • 函数调用栈(深度可控)。
  • 链式栈
    适用于元素数量不确定或变化剧烈的场景,例如:

    • 处理动态数据(如日志记录,长度未知);
    • 需频繁扩容的场景(避免顺序栈的复制开销)。

总结

  • 顺序栈注重效率和空间连续性,适合场景固定、数据量可预测的情况;
  • 链式栈注重灵活性,适合数据量动态变化、难以预估的情况。

4.完整代码

1.顺序表

Stack.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int STDataType;typedef struct STDataType
{STDataType* a;int top;int capacity;
}ST;//栈的初始化
void STInit(ST* st);//栈的销毁
void STDestory(ST* st);//入栈
void STPush(ST* st, STDataType x);
//出栈
void STPop(ST* st);//取出栈顶数据
STDataType STTop(ST* st);//判空
bool STEmpty(ST* st);//获取数据个数
STDataType STSize(ST* st);//栈的打印
void STPrint(ST* st);

Stack.c

#include"Stack.h"//栈的初始化
void STInit(ST* st)
{assert(st);st->a = NULL;st->top = -1;st->capacity = 0;
}//栈的销毁
void STDestory(ST* st)
{assert(st);free(st->a);st->a = NULL;st->capacity = 0;st->top = -1;
}//入栈
void STPush(ST* st, STDataType x)
{assert(st);// 注意:由于top初始化为-1,所以满的条件是top == capacity - 1if (st->top == st->capacity - 1){// 如果栈已满,则扩展栈的容量int newcapacity = st->capacity == 0 ? 4 : st->capacity * 2;STDataType* tmp = (STDataType*)realloc(st->a, newcapacity * sizeof(STDataType));if (tmp == NULL){perror("realloc fail");return;}st->a = tmp;st->capacity = newcapacity;}// 增加栈顶索引,为新元素腾出空间st->top++;// 将新元素x存储在栈顶位置st->a[st->top] = x;
}//出栈
void STPop(ST* st)
{assert(st);assert(st->top >= 0);st->top--;
}//取出栈顶数据
STDataType STTop(ST* st)
{assert(st);assert(st->top >= 0);return st->a[st->top];
}//判空
bool STEmpty(ST* st)
{assert(st);return st->top == -1;
}//获取数据个数
STDataType STSize(ST* st)
{assert(st);return st->top + 1;
}//栈的打印
void STPrint(ST* st)
{assert(st);assert(!STEmpty(st));// 从栈顶开始打印,直到栈底(但不包括索引-1)for (int i = st->top; i >= 0; i--){printf("%d ", st->a[i]);}
}
2.链式表

Stack.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int STDataType;typedef struct SListNode
{STDataType data;struct SListNode* next;
}SLTNode;typedef struct Stack
{// 指向栈顶节点的指针SLTNode* top;int size;
}ST;//栈的初始化
void STInit(ST* st);//栈的销毁
void STDestory(ST* st);//入栈
void STPush(ST* st, STDataType x);//出栈
void STPop(ST* st);//取出栈顶数据
STDataType STTop(ST* st);//判空
bool STEmpty(ST* st);//获取数据个数
STDataType STSize(ST* st);//栈的打印
void STPrint(ST* st);

Stack.c

#include"Stack.h"//栈的初始化
void STInit(ST* st)
{assert(st);st->size = 0;st->top = NULL;
}//栈的销毁
void STDestory(ST* st) 
{assert(st);SLTNode* top = st->top;while (top != NULL){SLTNode* next = top->next;free(top);top = next;}st->size = 0;
}//入栈
void STPush(ST* st, STDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail:");return;}// 新节点的next指向原来的栈顶newnode->next = st->top;// 设置新节点的数据newnode->data = x;// 更新栈顶为新节点st->top = newnode;st->size++;
}//出栈
void STPop(ST* st)
{assert(st);assert(!STEmpty(st));// 获取栈顶节点的下一个节点SLTNode* next = st->top->next;free(st->top);// 更新栈顶指针,使其指向新的栈顶节点st->top = next;st->size--;
}//取出栈顶数据
STDataType STTop(ST* st)
{assert(st);assert(!STEmpty(st));return st->top->data;
}//判空
bool STEmpty(ST* st)
{return (st->top == NULL);
}//获取数据个数
STDataType STSize(ST* st)
{return st->size;
}//栈的打印
void STPrint(ST* st)
{assert(st);assert(!STEmpty(st));for (SLTNode* top = st->top; top != NULL; top = top->next){printf("%d ", top->data);}
}

结束语

本篇我们主要介绍了一下栈,接下来我们将接着学习与栈类似的另一个数据结构——队列。

感谢您的三连支持!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/diannao/98938.shtml
繁体地址,请注明出处:http://hk.pswp.cn/diannao/98938.shtml
英文地址,请注明出处:http://en.pswp.cn/diannao/98938.shtml

如若内容造成侵权/违法违规/事实不符,请联系英文站点网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

华为HICE云计算的含金量高吗?

在数字时代的今天&#xff0c;云计算技术证飞速的发展成为企业数字化转型的重要支撑。而华为作为领先的通信和信息技术公司&#xff0c;推出的HCIE云计算认证备受关注。接下来就来说说华为HCIE云计算认证的含金量到底有多高。HCIE认证被认为是华为认证中的最高等级&#xff0c;…

OSPF协议原理讲解和实际配置(华为/思科)

OSPF&#xff08;open shorest path first&#xff0c;开放最短路径优先&#xff09;是一种动态的&#xff0c;基于链路状态的动态路由协议&#xff0c;广泛的应用在企业网络中&#xff0c;通过维护网络拓扑信息&#xff0c;利用 Dijkstra 算法实现最短路径&#xff0c;实现高效…

【开题答辩全过程】以 《黄帝内经》问答系统为例,包含答辩的问题和答案

个人简介一名14年经验的资深毕设内行人&#xff0c;语言擅长Java、php、微信小程序、Python、Golang、安卓Android等开发项目包括大数据、深度学习、网站、小程序、安卓、算法。平常会做一些项目定制化开发、代码讲解、答辩教学、文档编写、也懂一些降重方面的技巧。感谢大家的…

npm : 无法加载文件 C:\Program Files\nodejs\npm.ps1,因为在此系统上禁止运行脚

这个错误是由于 PowerShell 的执行策略限制&#xff0c;导致无法运行脚本。你可以通过以下步骤解决这个问题&#xff1a; 1. 查看当前的执行策略 打开 PowerShell&#xff0c;以管理员身份运行&#xff0c;输入以下命令查看当前的执行策略&#xff1a; Get-ExecutionPolicy如果…

macOS苹果电脑运行向日葵远程控制软件闪退

文章目录问题原因分析修复附录向日葵字太小按Ctrl键会弹出开始菜单的问题问题 向日葵是一款远程控制的应用&#xff0c;在macOS下也能运行&#xff0c; 本来用的好好的&#xff0c;有一天升级后突然就运行不起来了&#xff0c;一点开能显示几秒首界面&#xff0c;立马就自动退…

Linux dma-buf 框架原理、实现与应用详解

1. 背景与意义 1.1 异构系统与缓冲区共享的挑战 在现代 SoC、嵌入式、图形和多媒体系统中&#xff0c;CPU、GPU、VPU、ISP、DMA 控制器等多个硬件单元需要高效地共享和传递大块数据&#xff08;如图像帧、视频流、AI 张量等&#xff09;。如果每个设备都维护独立的缓冲区&…

Scikit-learn Python机器学习 - 分类算法 - 朴素贝叶斯

锋哥原创的Scikit-learn Python机器学习视频教程&#xff1a; https://www.bilibili.com/video/BV11reUzEEPH 课程介绍 ​ 本课程主要讲解基于Scikit-learn的Python机器学习知识&#xff0c;包括机器学习概述&#xff0c;特征工程(数据集&#xff0c;特征抽取&#xff0c;特…

如何免费股票数据API(第13期):沪深A股《最新分时交易》数据获取大全:附Python、Java等多语言实战教程与接口文档说明

在金融科技迅猛发展的今天&#xff0c;股票量化分析以其严谨的科学性和强大的系统性&#xff0c;正日益成为投资领域的主流方法论。任何卓越的量化模型的诞生&#xff0c;都离不开全面、精准、及时的数据支撑。无论是跃动着的实时交易数据、沉淀了历史规律的K线走势&#xff0c…

国标GB28181视频EasyGBS视频监控平台:一网联全城,交通道路可视化、视频巡检、应急指挥“三合一”。

一、方案背景​人车暴涨&#xff0c;路口告急&#xff1a;高峰堵、事故慢、取证难&#xff0c;老办法已拖不动城市交通。破局之道&#xff0c;先看摄像头——EasyGBS 严格遵循 GB28181 国标&#xff0c;一站式完成直播、存储、检索、转码&#xff0c;把万千路口秒级搬上云端&am…

单元测试(白盒测试方法)

一、单元测试1.单元测试是对软件的基本组成单元进行的测试&#xff0c;如函数、类或类的方法。单元测试是对软件的最小可测试单元&#xff08;即可独立编译或汇编的程序模块&#xff09;进行的测试活动&#xff0c;也称为模块测试二、白盒测试方法实例代码public static int te…

2010-2022 同等学力申硕国考:软件工程简答题真题汇总

2010年简答题 给出数据流图的定义&#xff0c;并举例说明数据流图的四个基本构成成份。 数据流图&#xff08;Data Flow Diagram, DFD&#xff09;是一种用于描述系统中数据流动和处理过程的图形工具。它通过直观的方式展示了系统的输入数据如何经过一系列处理变换为输出数据&a…

海外盲盒APP开发:如何用技术重构“惊喜经济”

当盲盒的神秘感遇上技术的确定性&#xff0c;一场关于消费体验的革命正在海外市场悄然发生。从概率算法的公平性到AR虚拟开箱的沉浸感&#xff0c;从跨境物流的实时追踪到多语言支持的无缝切换&#xff0c;海外盲盒APP的开发是一场技术、设计与商业逻辑的深度融合。概率算法&am…

Aosp13 手机sim卡信号格显示修改

工作中&#xff0c;客户要求对信号格显示偏弱不够友好为由&#xff0c;提出修改&#xff0c;要求使其显示信号强一些。在此记录 一问题&#xff1a;修改系统sim卡显示的信号格&#xff0c;在设备其他配置不变的情况下&#xff0c;使其信号格显示比原有的要优秀二 …

硬件开发2-汇编2(ARMv7-A)- 裸机开发

一、指令1、b&#xff08;Branch&#xff09;原型&#xff1a;B<c> <label>作用&#xff1a;实现无条件跳转&#xff0c;常用于不返回的跳转场景特点&#xff1a;仅跳转到目标地址&#xff0c;不保存返回地址示例&#xff1a;b reset ;跳转到reset标号处执…

清源 SCA 社区版更新(V4.2.0)|漏洞前置感知、精准修复、合规清晰,筑牢软件供应链安全防线!

随着数字化进程加速&#xff0c;软件供应链安全威胁日益复杂&#xff0c;公开漏洞响应滞后、0day 攻击防不胜防、组件升级编译失败、安全与合规风险混杂......这些痛点让企业安全团队、运维人员及研发团队疲于应对。自 2025 年 7 月 1 日安势清源 SCA 社区版首次正式发布以及在…

氚燃料增殖里程碑:MIT新型BABY包层技术实验验证

● 导语 5月20日&#xff0c;麻省理工学院&#xff08;MIT&#xff09;发文称&#xff0c;BABY实验首次获取了氚在装置内增殖的实测数据&#xff0c;验证了核心模型&#xff0c;并为未来核聚变电厂的燃料自循环奠定了重要基础。 原文&#x1f447;&#x1f3fb; https://m…

python+springboot+uniapp微信小程序题库系统 在线答题 题目分类 错题本管理 学习记录查询系统

目录技术栈介绍具体实现截图系统设计研究方法&#xff1a;设计步骤设计流程核心代码部分展示研究方法详细视频演示试验方案论文大纲源码获取/详细视频演示技术栈介绍 Django-SpringBoot-php-Node.js-flask 本课题的研究方法和研究步骤基本合理&#xff0c;难度适中&#xff0…

Office转PDF转换器v1.0.py

软件介绍 这是批量将word、Excel、PPT转换为PDF格式的软件&#xff0c;不过PPT转换为PDF需要电脑安装了office&#xff0c;目前这个我还没有解决没有office也可以安装的方法。 软件使用 软件使用是比较简单的&#xff0c;导入文件/文件夹&#xff0c;在自定义输出路径 点击这…

62_基于深度学习的海洋垃圾检测识别系统(yolo11、yolov8、yolov5+UI界面+Python项目源码+模型+标注好的数据集)

目录 项目介绍&#x1f3af; 功能展示&#x1f31f; 一、环境安装&#x1f386; 环境配置说明&#x1f4d8; 安装指南说明&#x1f3a5; 环境安装教学视频 &#x1f31f; 二、数据集介绍&#x1f31f; 三、系统环境&#xff08;框架/依赖库&#xff09;说明&#x1f9f1; 系统环…

深入浅出 全面剖析消息队列(Kafka,RabbitMQ,RocketMQ 等)

消息队列 一、概念 消息队列&#xff08;MQ&#xff09;&#xff1a;一种异步通信机制&#xff0c;通过“消息”的形式让不同系统或模块解耦核心思想&#xff1a;发送方&#xff08;生产者Producer&#xff09;只负责发送消息&#xff0c;接收方&#xff08;消费者Consumer&…