数据结构深入理解--栈-阿里云开发者社区

数据结构深入理解--栈

2024-05-27 33

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 数据结构深入理解--栈

一、栈的定义

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

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

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

栈可以这样理解：相信大家都对枪械有一定粗略的了解，咱们就用压子弹来帮助大家进行理解。

压栈，大家可以想象为压子弹，子弹是一发一发往下压，那压栈就是在容量之内一个数据一个数据往下压。

出栈，大家可以理解为子弹射出的过程，即：最后压入的子弹先出。数据最后的先出。

这就是压栈与出栈的过程，当然也可以压一个出一个，压多个出一个都可以，大家完全就可以把栈当作压子弹和子弹射出。

好了，基础知识我们已经掌握，那么，我们该用什么结构来实现栈呢？

通过单链表，双链表还是什么？大家可以在此处进行思考，稍后公布答案。

二、栈的实现

上文说到，我们要选择一个结构来实现栈。我们来一一分析一下：

双链表全称为：带头双向循环链表，用它来实现可以吗？还用说吗？太过于完美当然可以，但是要用两个指针，同学们，一个指针已经困扰大家已久，那两个指针想必是大家不想经历的大恐怖。所以，这个时候咱们把它先列为备胎（实在没办法在想它（在特殊情况下能渣则渣）🐶）。

单链表全称为：不带头单向不循环链表，大家想单链表找到尾元素麻烦吗？找一遍时间复杂度为O（N）。虽然我们可以反转一下，但是你愿意用吗？要是放两个指针还不如用双链表。

这个时候怎么办？难道我们要使用双链表？不，绝对不行。这时，数组意外路过，对啊，我们可以用数组。

数组每次使用前像顺序表一样判断是否开辟空间，在用一个变量size来记录尾，这样不就完美符合要求了。那说干就干吧。打开我们心爱的VS。

2.1 栈的结构

栈的结构，可以借鉴一下顺序表，要有数组、容量和栈定元素。结构如下：

1. // 支持动态增长的栈
2. typedef int STDataType;
3. typedef struct Stack
4. {
5.  STDataType* a;
6.  int top;    // 栈顶
7.  int capacity;  // 容量 
8. }Stack;

2.2 栈的初始化

要进行初始化，大家想一想top赋值为多大合适，如果为0，那么0是不是为栈的第一个元素？是不是？答案是：是的。那么，有没有办法不叫top指向数组第一个元素？有，使top的值为-1即可。在后续代码中，我会将top初始化为0（别问，问就是top此时可以当顺序表中的size使用）。代码如下：

1. // 初始化栈
2. void StackInit(Stack* ps)
3. {
4.  assert(ps);
5.  ps->a = NULL;
6.  ps->capacity = ps->top = 0;
7. }

2.3 栈的销毁

在我们今后写代码一定要记住：只要你malloc，realloc一定要free，你创建了就一定要销毁。

那我们创建了一个栈，那么我们一定要销毁。代码如下：

1. // 销毁栈 
2. void StackDestroy(Stack* ps)
3. {
4.  assert(ps);
5.  free(ps->a);//此处记得释放ps指向的数组，不要写成ps！！！
6.  ps->a = NULL;
7.  ps->capacity = ps->top = 0;
8. }

注意事项写在代码里了，一定要记住！！！

2.3 栈元素的插入

1. void StackPush(Stack* ps, STDataType data)
2. {
3.  assert(ps);
4.  if (ps->capacity == ps->top)
5.  {
6.    int newcapacity = ps->capacity == 0 ? 4 : 2 * sizeof(ps->capacity);
7.    STDataType* newnode = (STDataType*)realloc(ps->a,newcapacity*sizeof(STDataType));
8.    if (newnode == NULL)
9.    {
10.       perror("realloc fail");
11.       return;
12.     }
13.     ps->capacity = newcapacity;
14.     ps->a = newnode;
15.   }
16.   //这里之所以没有封装成一个接口，是因为这里只用一次，其余的都不使用
17.   ps->a[ps->top] = data;
18.   ps->top++;
19.   //这里也可以合二为一
20.   //ps->a[ps->top++] = data;
21. }

此处要点与顺序表类似，就不过多强调。

2.4 栈元素的删除

1. // 出栈 
2. void StackPop(Stack* ps)
3. {
4.  assert(ps);
5.  assert(ps->top > 0);
6.  ps->top--;
7. }

此处代码过于简单，那么能不能不把这个封装了，直接写。其实你要是想这么干，你可以试一试，不过提醒一下：可能会出乱子。还是那句话：专业的事专业的人做。

2.5 栈顶元素获取

1. // 获取栈顶元素 
2. STDataType StackTop(Stack* ps)
3. {
4.  assert(ps);
5.  assert(ps->top > 0);
6.  return ps->a[ps->top - 1];
7. }

对于此代码最后的返回值可能会有人有疑问，我简单解释一下：

2.6 栈元素有效个数获取

1. // 获取栈中有效元素个数 
2. int StackSize(Stack* ps)
3. {
4.  assert(ps);
5.  return ps->top;
6. }

上文说过top初始化为0时可当size来使用，代码简单，不过多解释。

2.7 栈是否为空判断

1. // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
2. bool StackEmpty(Stack* ps)
3. {
4.  assert(ps);
5.  return ps->top == 0;
6. }

注意点：必须包含头文件：stdbool.h。

三、代码总览

Stack.h

1. #pragma once
2. #include<stdio.h>
3. #include<stdlib.h>
4. #include<assert.h>
5. #include<stdbool.h>
6. 
7. // 支持动态增长的栈
8. typedef int STDataType;
9. typedef struct Stack
10. {
11.   STDataType* a;
12.   int top;    // 栈顶
13.   int capacity;  // 容量 
14. }Stack;
15. 
16. // 初始化栈 
17. void StackInit(Stack* ps);
18. // 入栈 
19. void StackPush(Stack* ps, STDataType data);
20. // 出栈 
21. void StackPop(Stack* ps);
22. // 获取栈顶元素 
23. STDataType StackTop(Stack* ps);
24. // 获取栈中有效元素个数 
25. int StackSize(Stack* ps);
26. // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
27. bool StackEmpty(Stack* ps);
28. // 销毁栈 
29. void StackDestroy(Stack* ps);

Stack.c

1. #include"Stack.h"
2. 
3. // 初始化栈
4. void StackInit(Stack* ps)
5. {
6.  assert(ps);
7.  ps->a = NULL;
8.  ps->capacity = ps->top = 0;
9. }
10. // 入栈 
11. void StackPush(Stack* ps, STDataType data)
12. {
13.   assert(ps);
14.   if (ps->capacity == ps->top)
15.   {
16.     int newcapacity = ps->capacity == 0 ? 4 : 2 * sizeof(ps->capacity);
17.     STDataType* newnode = (STDataType*)realloc(ps->a,newcapacity*sizeof(STDataType));
18.     if (newnode == NULL)
19.     {
20.       perror("realloc fail");
21.       return;
22.     }
23.     ps->capacity = newcapacity;
24.     ps->a = newnode;
25.   }
26.   //这里之所以没有封装成一个接口，是因为这里只用一次，其余的都不使用
27.   ps->a[ps->top] = data;
28.   ps->top++;
29.   //这里也可以合二为一
30.   //ps->a[ps->top++] = data;
31. }
32. // 出栈 
33. void StackPop(Stack* ps)
34. {
35.   assert(ps);
36.   assert(ps->top > 0);
37.   ps->top--;
38. }
39. // 获取栈顶元素 
40. STDataType StackTop(Stack* ps)
41. {
42.   assert(ps);
43.   assert(ps->top > 0);
44.   return ps->a[ps->top - 1];
45. }
46. // 获取栈中有效元素个数 
47. int StackSize(Stack* ps)
48. {
49.   assert(ps);
50.   return ps->top;
51. }
52. // 检测栈是否为空，如果为空返回非零结果，如果不为空返回0 
53. bool StackEmpty(Stack* ps)
54. {
55.   assert(ps);
56.   return ps->top == 0;
57. }
58. // 销毁栈 
59. void StackDestroy(Stack* ps)
60. {
61.   assert(ps);
62.   free(ps->a);//此处记得释放ps指向的数组，不要写成ps！！！
63.   ps->a = NULL;
64.   ps->capacity = ps->top = 0;
65. }

测试代码:test.c

1. #include"Stack.h"
2. 
3. int main()
4. {
5.  Stack p;
6.  StackInit(&p);
7.  StackPush(&p, 1);
8.  StackPush(&p, 2);
9.  StackPush(&p, 3);
10.   StackPush(&p, 4);
11.   while (!StackEmpty(&p))
12.   {
13.     printf("%d ", StackTop(&p));
14.     StackPop(&p);
15.   }
16.   StackDestroy(&p);
17.   return 0;
18. }

四、例题

既然明白了，那么来几道题巩固一下吧！

例一：

设栈S和队列 Q的初始状态均为空，元素 abcdepg 依次进入栈S。若每个元素出栈后立即进入队列 Q，且7个元素出队的顺序是 bdcfeag，则栈S的容量至少是：

例二：

若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行，但不允许连续3次进行退栈操作，不可能得到的出栈序列是（）。

A. dcebfa B. cbdaef C.bcaefd D.afedcb

例三：

元素 a,b,c,d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是

好了，我们的学习到现在就结束了，如有疑惑可私信，也可在评论区留言。

完！

文章标签：

C++

关键词：

数据结构栈