电子工程师技术服务社区
公告
登录
|
注册
首页
技术问答
厂商活动
正点原子
板卡试用
资源库
下载
文章
社区首页
文章
面试官问我什么是「栈」,我随手画了10张图来解释
分 享
扫描二维码分享
面试官问我什么是「栈」,我随手画了10张图来解释
数据结构
李肖遥
关注
发布时间: 2020-09-09
丨
阅读: 803
## 栈的概念 栈(stack)是限定仅在表的一端进行操作的数据结构,且栈是一种先进后出的数据结构,允许操作的一端称为**栈顶**,不允许操作的称为**栈底**,如下图所示: ![](https://cf01.ickimg.com/bbsimages/202008/9bac6b80bf9f909a98c78b38385ed2d2.png) 之前我们讲到了链表,我们只能够对其链表的表尾结点进行操作,并且只能进行插入一个新的结点与删除最末尾的这个结点两个操作,而这样**强限制性的‘链表’**,就是我们所说的**栈**。 就像是一个死胡同一样,只有一个出口,如图所示,有个概念: ![](https://cf01.ickimg.com/bbsimages/202008/d496ba6e6d3a533a70a0b88974f4dc1b.png) ## 栈的结点设计 栈分为**数组栈**和**链表栈**,其区别如下: - `数组栈`使用数组进行功能的模拟,实现较为快速和便利; - `链表栈`使用链表的思路去设计,实现相比较说较为麻烦,但是其稳定,且不易出错; 在链表栈中又分为**静态链表栈和动态链表栈**,其区别如下: - `静态链表栈`给定栈的空间大小,不允许超过存储超过给定数据大小的元素; - `动态栈`使用的是自动创建空间的方法进行创建,只要符合机器的硬件要求以及编译器的控制,其理论上是极大的。 ### 数组栈 其实际就是用一段连续的存储空间来存储栈中的数据元素,有以下特点: 1. 元素所占的存储空间必须连续,这里的连续是指的逻辑连续,而不是物理连续。 2. 元素在存储空间的位置是按逻辑顺序存放的 我们来举例说明,鉴于C语言数组下标都是0开始,并且栈的使用需要的空间大小难以估计,所以初始化空栈的时候,不应该设定栈的最大容量。 我们先为栈设定一个基本容量,在应用过STACK_程当中,当栈的空间不够用时,再逐渐扩大。 设定2个常量,`STACK_INIT_SIZE`(存储空间初始化分配量)和`STACK_INCREMENT`(存储空间分配增量),宏定义如下 ``` #define STACK_INIT_SIZE 1000 //数值可以根据实际情况确定 #define STACK_INCREMENT 10 //数值可以根据实际情况确定 ``` 栈的定义如下 ``` typedef struct { void *base; void *top; int stackSize; } SqSTACK; ``` - base 表示栈底指针 - top 表示栈顶指针 - stackSize 表示栈当前可以使用的最大容量 若base的值是NULL,表示栈结构不存在;top初始值指向栈底,即`top = base;` 每当插入新的元素时,指针top就增1,反之删除就减1,**非空栈中的栈顶指针**始终在**栈顶元素的下一个指针**上面。 数据元素和栈顶指针的关系如下图所示: ![](https://cf01.ickimg.com/bbsimages/202008/bff46c6d5658c70860001dcf578acb5b.png) ### 链表栈 我们以链表栈的动态链表栈为例子,进行栈的设计。 首先是栈的结点,设计出两个结构体,一个结构体Node表示结点,其中包含有一个`data`域和`next`指针,如图所示: ![Node](https://cf01.ickimg.com/bbsimages/202008/c420c1fb23150d098d1ba246cfe808b5.png) 其中data表示数据,next指针表示下一个的指针,其指向下一个结点,通过next指针将各个结点链接。 接下来是我们设计的重点,为这个进行限制性的设计,我们需要额外添加一个结构体,其包括了一个**永远指向栈头的指针top**和**一个计数器count**记录元素个数。 **其主要功效**就是设定**允许操作元素的指针**以及**确定栈何时为空**,如图所示: ![Stack](https://cf01.ickimg.com/bbsimages/202008/3e93fbf04998d8ce37a792679dd2b875.png) 这里我采用的是**top和count组合的方法**。其代码可以表示为: ```cpp //栈的结点设计 //单个结点设计,数据和下一个指针 typedef struct node { int data; struct node *next; } Node; ``` 利用上面的结点创建栈,分为指向头结点的top指针和计数用的count ``` typedef struct stack { Node *top; int count; } Link_Stack; ``` ## 栈的基本操作—入栈(压栈) 入栈的基本顺序可以用以下图所示: ![](https://cf01.ickimg.com/bbsimages/202008/f770d29fa8d423ec07acc0dcf22f16d0.png) 入栈(push)操作时,我们只需要找到top所指向的空间,创建一个新的结点,将**新的结点的next指针**指向**top指针指向的空间**,再将top指针转移,并且指向新的结点,这就是是**入栈操作**。 其代码可以表示为: ```cpp //入栈 push Link_Stack *Push_stack(Link_Stack *p, int elem) { if (p == NULL) return NULL; Node *temp; temp=(Node*)malloc(sizeof(Node)); //temp = new Node; temp->data = elem; temp->next = p->top; p->top = temp; p->count++; return p; } ``` ## 栈的基本操作—出栈 ![](https://cf01.ickimg.com/bbsimages/202008/2c25182e108d3a1a6e04b0d29fff932f.png) 出栈(pop)操作,是在栈不为空的情况下,重复说一次,**一定要进行判空操作**,将栈顶的元素删除,同时top指针,next向下进行移动即可的操作。 其代码可以表示为: ```cpp //出栈 pop Link_Stack *Pop_stack(Link_Stack *p) { Node *temp; temp = p->top; if (p->top == NULL) { printf("错误:栈为空"); return p; } else { p->top = p->top->next; free(temp); //delete temp; p->count--; return p; } } ``` ## 栈的基本操作—遍历 这个就很常见了,也是我们调试必须的手段。 栈的遍历相对而言比较复杂,由于栈的特殊性质,其只允许在一端进行操作,所以**遍历操作操作永远都是逆序的**。 简单一点描述,其过程为,在栈不为空的情况下,一次从栈顶元素向下访问,直到指针指向空(即到栈尾)为结束。 其代码可以表示为: ```cpp //遍历栈:输出栈中所有元素 int show_stack(Link_Stack *p) { Node *temp; temp = p->top; if (p->top == NULL) { printf(""); printf("错误:栈为空"); return 0; } while (temp != NULL) { printf("%d\t", temp->data); temp = temp->next; } printf("\n"); return 0; } ``` ## 栈数组与栈链表的代码实现 最后呢,我们使用代码来帮助我们了解一下: ### 栈数组 数组栈是一种更为快速的模拟实现栈的方法,这里我们不多说。 模拟,就是不采用真实的链表设计,转而采用数组的方式进行**模拟操作**。 也就是说这是一种仿真类型的操作,其可以快速的帮助我们构建代码,分析过程,相应的实现起来也更加的便捷。 其代码如下: ```cpp #include
#include
#include
#define maxn 10000 //结点设计 typedef struct stack{ int data[maxn]; int top; }stack; //创建 stack *init(){ stack *s=(stack *)malloc(sizeof(stack)); if(s==NULL){ printf("分配内存空间失败"); exit(0); } memset(s->data,0,sizeof(s->data)); //memset操作来自于库文件string.h,其表示将整个空间进行初始化 //不理解可以查阅百度百科https://baike.baidu.com/item/memset/4747579?fr=aladdin s->top=0; //栈的top和bottom均为0(表示为空) return s; } //入栈push void push(stack *s,int data){ s->data[s->top]=data; s->top++; } //出栈pop void pop(stack *s){ if(s->top!=0){ s->data[s->top]=0; //让其回归0模拟表示未初始化即可 s->top--; } } //模拟打印栈中元素 void print_stack(stack *s){ for(int n=s->top-1;n>=0;n--){ printf("%d\t",s->data[n]); } printf("\n"); //习惯性换行 } int main(){ stack *s=init(); int input[5]={11,22,33,44,55}; //模拟五个输入数据 for(int i=0;i<5;i++){ push(s,input[i]); } print_stack(s); ///////////// pop(s); print_stack(s); return 0; } ``` 其编译结果如下: ![](https://cf01.ickimg.com/bbsimages/202008/2d9f7f0aee4816d344ccb601c00784ef.png) ## 关于栈的总结 栈-它是一种运算受限的线性表,在数制转换,括号匹配的检验,表达式求值等方面都可以使用,并且较为简便的解决问题。 今天栈基础就讲到这里,下一期,我们再见!
原创作品,未经权利人授权禁止转载。详情见
转载须知
。
举报文章
点赞
(
0
)
李肖遥
关注
评论
(0)
登录后可评论,请
登录
或
注册
相关文章推荐
MK-米客方德推出工业级存储卡
Beetle ESP32 C3 蓝牙数据收发
Beetle ESP32 C3 wifi联网获取实时天气信息
开箱测评Beetle ESP32-C3 (RISC-V芯片)模块
正点原子数控电源DP100测评
DP100试用评测-----开箱+初体验
Beetle ESP32 C3环境搭建
【花雕体验】16 使用Beetle ESP32 C3控制8X32位WS2812硬屏之二
X
你的打赏是对原创作者最大的认可
请选择打赏IC币的数量,一经提交无法退回 !
100IC币
500IC币
1000IC币
自定义
IC币
确定
X
提交成功 ! 谢谢您的支持
返回
我要举报该内容理由
×
广告及垃圾信息
抄袭或未经授权
其它举报理由
请输入您举报的理由(50字以内)
取消
提交