线性结构常见应用之栈[基于郝斌课程]

栈的定义：
  一种可以实现“先进后出”的存储结构
  栈类似于箱子，先放进去的最后取出来，最后放入的先取出来
栈的分类：
  静态栈的内核是数组
  动态栈的内核是链表
栈的算法：
  出栈
  压栈
栈的应用：
  函数调用
  中断
  表达式求值
  内存分配
  缓冲处理
  迷宫

1. /*
2. @file      main.c
3. @brief     线性结构常见应用之栈
4. @author    EricsT (EricsT@163.com)
5. @version   v1.0.0
6. @date      2025-09-23
7. @history   2025-09-23 EricsT - 新建文件
8. */
10. #include <stdio.h>
11. #include <malloc.h>
12. #include <stdlib.h>
14. typedef struct NODE
15. {
16.         int data;
17.         NODE* ptrNext;
18. }* PtrNode, Note;
20. typedef struct STACK
21. {
22.         PtrNode ptrTop;
23.         PtrNode ptrBottom;
24. }* PtrStack, Stack;
26. void InitStack(PtrStack ptrStack);//初始化
27. void PushStack(PtrStack ptrStack, int pushValue);//压栈
28. bool PopStack(PtrStack ptrStack);//出栈
29. void TraverseStack(const PtrStack ptrStack);//遍历
30. bool IsEmptyStack(const PtrStack ptrStack);//判断是否为NULL
31. void ClearStack(PtrStack ptrStack);//清空栈
33. int main(void)
34. {
35.         Stack stack;
37.         InitStack(&stack);
39.         int pushValue;
40.         printf("请输入插入数值");
41.         scanf("%d", &pushValue);
42.         PushStack(&stack, pushValue);
44.         printf("请输入插入数值");
45.         scanf("%d", &pushValue);
46.         PushStack(&stack, pushValue);
48.         printf("请输入插入数值");
49.         scanf("%d", &pushValue);
50.         PushStack(&stack, pushValue);
52.         printf("请输入插入数值");
53.         scanf("%d", &pushValue);
54.         PushStack(&stack, pushValue);
56.         printf("请输入插入数值");
57.         scanf("%d", &pushValue);
58.         PushStack(&stack, pushValue);
60.         TraverseStack(&stack);
62.         PopStack(&stack);
64.         TraverseStack(&stack);
66.         ClearStack(&stack);
68.         TraverseStack(&stack);
70.         return 0;
71. }
73. void InitStack(PtrStack ptrStack)
74. {//顶栈和底栈都指向空节点
76.         ptrStack->ptrBottom = (PtrNode)malloc(sizeof(NODE));
77.         ptrStack->ptrBottom->ptrNext = NULL;
79.         ptrStack->ptrTop = ptrStack->ptrBottom;
80. }
82. void PushStack(PtrStack ptrStack, int pushValue)
83. {
84.         PtrNode ptrPushNode = (PtrNode)malloc(sizeof(NODE));
86.         ptrPushNode->data = pushValue;
87.         ptrPushNode->ptrNext = ptrStack->ptrTop;
89.         ptrStack->ptrTop = ptrPushNode;
90. }
92. void TraverseStack(const PtrStack ptrStack)
93. {
94.         PtrNode ptrNodeCur = ptrStack->ptrTop;
96.         //while (NULL != ptrNodeCur->ptrNext)
97.         //{
98.         //        printf("%d ", ptrNodeCur->data);
99.         //        ptrNodeCur = ptrNodeCur->ptrNext;
100.         //}
102.         while (ptrStack->ptrBottom != ptrNodeCur)
103.         {
104.                 printf("%d ", ptrNodeCur->data);
105.                 ptrNodeCur = ptrNodeCur->ptrNext;
106.         }
108.         printf("\n");
109. }
111. bool PopStack(PtrStack ptrStack)
112. {
113.         if (IsEmptyStack(ptrStack))//空栈时无法出栈
114.                 return false;
116.         PtrNode ptrNode = ptrStack->ptrTop;
117.         ptrStack->ptrTop = ptrNode->ptrNext;
118.         free(ptrNode);
119.         //ptrStack->ptrTop = ptrStack->ptrTop->ptrNext;这种写法无法释放原来顶栈的内存
120.         return true;
121. }
123. bool IsEmptyStack(const PtrStack ptrStack)
124. {
125.         if (ptrStack->ptrBottom == ptrStack->ptrTop)
126.                 return true;
128.         return false;
129. }
131. void ClearStack(PtrStack ptrStack)
132. {
133.         if (IsEmptyStack(ptrStack))
134.                 return;
136.         PtrNode ptrNoteCur = ptrStack->ptrTop;
137.         PtrNode ptrNoteNext = NULL;
139.         while (ptrStack->ptrBottom != ptrNoteCur)
140.         {
141.                 ptrNoteNext = ptrNoteCur->ptrNext;
142.                 free(ptrNoteCur);//释放内存
143.                 ptrNoteCur = ptrNoteNext;
144.         }
146.         ptrStack->ptrTop = ptrStack->ptrBottom;
147. }

复制代码

 

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！