【数据结构】栈-C语言版-阿里云开发者社区

【数据结构】栈-C语言版

2023-02-07 78

版权

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

简介： 【数据结构】栈-C语言版

栈的概念

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

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

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

栈的实现一般可以使用数组或者链表实现，相对而言数组的结构实现更优一些。因为数组在尾上插入数据的代价比较小。

栈的实现

头文件 039-Stack.h

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #pragma once
3. #include<stdbool.h>
4. #include<stdio.h>
5. #include<assert.h>
6. #include<stdlib.h>
7. 
8. typedef int STDataType;
9. 
10. struct Stack
11. {
12.   STDataType* a;
13.   int top;//栈顶，top指向最后一个数据的下一个位置
14.   int capacity;//容量，方便增容
15. };
16. 
17. typedef struct Stack Stack;
18. 
19. //初始化
20. void StackInit(Stack* pst);
21. 
22. //销毁
23. void StackDestroy(Stack* pst);
24. 
25. //栈顶插入元素
26. void StackPush(Stack* pst, STDataType x);
27. 
28. //栈顶删除元素
29. void StackPop(Stack* pst);
30. 
31. //取栈顶元素
32. STDataType StackTop(Stack* pst);
33. 
34. //判断栈空
35. bool StackEmpty(Stack* pst);
36. 
37. //求栈元素个数
38. int StackSize(Stack* pst);

源文件 039-Stack.c

1. #include "039-Stack.h"
2. 
3. //初始化
4. void StackInit(Stack* pst)
5. {
6.  assert(pst);
7.  pst->a = (STDataType*)malloc(sizeof(STDataType) * 4);
8.  pst->top = 0;
9.  pst->capacity = 4;
10. }
11. 
12. //销毁
13. void StackDestroy(Stack* pst)
14. {
15.   assert(pst);
16.   free(pst->a);
17.   pst->a = NULL;
18.   pst->capacity = pst->top = 0;
19. }
20. 
21. //插入元素
22. void StackPush(Stack* pst, STDataType x)
23. {
24.   assert(pst);
25.   if (pst->top == pst->capacity)
26.   {
27.     STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * pst->capacity * 2);
28.     if (tmp == NULL)
29.     {
30.       printf("realloc fail\n");
31.       exit(-1);
32.     }
33.     pst->a = tmp;
34.     pst->capacity *= 2;
35.   }
36. 
37.   pst->a[pst->top] = x;
38.   pst->top++;
39. }
40. 
41. //删除元素
42. void StackPop(Stack* pst)
43. {
44.   assert(pst);
45.   assert(!StackEmpty(pst));
46.   pst->top--;
47. }
48. 
49. //返回栈顶元素
50. STDataType StackTop(Stack* pst)
51. {
52.   assert(pst);
53.   assert(!StackEmpty(pst));
54.   return pst->a[pst->top - 1];
55. }
56. 
57. //判断栈是否已满，空返回1，非空返回0
58. bool StackEmpty(Stack* pst)
59. {
60.   assert(pst);
61.   return pst->top == 0;
62. }
63. 
64. //求栈中元素个数
65. int StackSize(Stack* pst)
66. {
67.   assert(pst);
68.   return pst->top;
69. }

测试文件 039-test.c

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #include "039-Stack.h"
3. 
4. void TestStack()
5. {
6.  Stack st;
7.  StackInit(&st);
8.  StackPush(&st, 1);
9.  StackPush(&st, 2);
10.   StackPush(&st, 3);
11. 
12.   while (!StackEmpty(&st))
13.   {
14.     printf("%d ", StackTop(&st));
15.     StackPop(&st);
16.   }
17. 
18.   StackDestroy(&st);
19. 
20. }
21. int main()
22. {
23.   TestStack();
24.   return 0;
25. }

栈的应用

1.有效的括号 OJ链接

分析：

（1）将栈的实现可以直接copy进去（返回栈顶元素需要做小小的改动：如果栈为空，不能直接assert断言终止，而要返回'\0'），后面只需要实现括号的匹配即可。

（2）如何实现括号匹配？如果是左括号，那么入栈，如果是右括号就判断栈顶元素该右括号是否能够匹配，如果可以就从栈里弹出一个左括号，如果不匹配就直接返回false。

1. #define  _CRT_SECURE_NO_WARNINGS  1
2. #pragma once
3. #include<stdbool.h>
4. #include<stdio.h>
5. #include<assert.h>
6. #include<stdlib.h>
7. 
8. typedef int STDataType;
9. struct Stack
10. {
11.   STDataType* a;
12.   int top;//栈顶，top指向最后一个数据的下一个位置
13.   int capacity;//容量，方便增容
14. };
15. 
16. typedef struct Stack Stack;
17. 
18. //初始化
19. void StackInit(Stack* pst);
20. 
21. //销毁
22. void StackDestroy(Stack* pst);
23. 
24. //栈顶插入元素
25. void StackPush(Stack* pst, STDataType x);
26. 
27. //栈顶删除元素
28. void StackPop(Stack* pst);
29. 
30. //取栈顶元素
31. STDataType StackTop(Stack* pst);
32. 
33. //判断栈空
34. bool StackEmpty(Stack* pst);
35. 
36. //求栈元素个数
37. int StackSize(Stack* pst);
38. 
39. //初始化
40. void StackInit(Stack* pst)
41. {
42.   assert(pst);
43.   pst->a = (STDataType*)malloc(sizeof(STDataType) * 4);
44.   pst->top = 0;
45.   pst->capacity = 4;
46. }
47. 
48. //销毁
49. void StackDestroy(Stack* pst)
50. {
51.   assert(pst);
52.   free(pst->a);
53.   pst->a = NULL;
54.   pst->capacity = pst->top = 0;
55. }
56. 
57. //插入元素
58. void StackPush(Stack* pst, STDataType x)
59. {
60.   assert(pst);
61.   if (pst->top == pst->capacity)
62.   {
63.     STDataType* tmp = (STDataType*)realloc(pst->a, sizeof(STDataType) * pst->capacity * 2);
64.     if (tmp == NULL)
65.     {
66.       printf("realloc fail\n");
67.       exit(-1);
68.     }
69.     pst->a = tmp;
70.     pst->capacity *= 2;
71.   }
72. 
73.   pst->a[pst->top] = x;
74.   pst->top++;
75. }
76. 
77. //删除元素
78. void StackPop(Stack* pst)
79. {
80.   assert(pst);
81.   assert(!StackEmpty(pst));
82.   pst->top--;
83. }
84. 
85. //返回栈顶元素
86. STDataType StackTop(Stack* pst)
87. {
88.   assert(pst);
89.     if(StackEmpty(pst))
90.     {
91.         return '\0';
92.     }
93.   //assert(!StackEmpty(pst));
94.   return pst->a[pst->top - 1];
95. }
96. 
97. //判断栈是否已满，空返回1，非空返回0
98. bool StackEmpty(Stack* pst)
99. {
100.  assert(pst);
101.  return pst->top == 0;
102. }
103. 
104. //求栈中元素个数
105. int StackSize(Stack* pst)
106. {
107.  assert(pst);
108.  return pst->top;
109. }
110. 
111. 
112. bool isValid(char * s) {
113.  Stack st;
114.  StackInit(&st);
115.  while (*s)
116.  {
117.    //左括号入栈
118.    if (*s == '(' || *s == '[' || *s == '{')
119.    {
120.      StackPush(&st, *s);
121.      s++;//迭代
122.    }
123.    else
124.    {
125.      if (StackEmpty(&st))
126.      {
127.        return false;
128.      }
129.      //右括号找最近的左括号匹配
130.      char top  = StackTop(&st);
131.      if (top == '(' && *s != ')'
132.        || top == '[' && *s != ']'
133.        || top == '{' && *s != '}')
134.      {
135.        StackDestroy(&st);
136.        return false;
137.      }
138.      else
139.      {
140.        //匹配就弹出左括号
141.        StackPop(&st);
142.        s++;//迭代  
143.      }
144.    }
145.  }
146. 
147.  bool ret = StackEmpty(&st);
148.  StackDestroy(&st);
149.  return ret;
150. }
151. 
152. 
153. 
154.

【数据结构】栈-C语言版

栈的概念

栈的实现

栈的应用

热门文章

最新文章

相关课程

相关电子书