栈知识总结

Julia999

线性结构的两种常见的应用之一：栈定义：一种可以实现“先进后出”的存储结构（类似于箱子）


分类：
静态栈
动态栈：


算法：
出栈
压栈


直接上代码好理解：

1. #include<stdio.h>
   
2. #include<mallloc.h>
   
3. #include<stdlib.h>
   
4. 
   
5. typedef struct Node
   
6. {
   
7.         int data;
   
8.         struct Node *pNext;
   
9. }NODE,*PNODE;
   
10. 
    
11. typedef struct Stack
    
12. {
    
13.         //pTop永远指向顶部，pBottom永远指向底部
    
14.         PNODE pTop;
    
15.         PNODE pBottom;
    
16. }STACK,*PSTACK;
    
17. 
    
18. void initStack(PSTACK pS)
    
19. {
    
20.         //造出一个节点，并且让pTopS指向这个节点
    
21.         pS->pTop=(PDONE)malloc(sizeof(NODE));
    
22.         if(NULL=pS->pTop)
    
23.         {
    
24.                 printf("动态内存分配失败！");
    
25.                 exit(-1);
    
26.         }
    
27.         else
    
28.         {
    
29.                 pS->pButtom=pS->pTop;
    
30.                 //让指向的这个节点的指针域指向NULL
    
31.                 pS->pTop->pNext-NULL;
    
32.         }
    
33.        
    
34. }
    
35. 
    
36. void push(PSTACK pS,int val)
    
37. {
    
38.         //先造出一个节点来保存val的值
    
39.         PNODE pNew=(PNODE)malloc(sizeof(NDOE));
    
40.         //将新的节点的数据域变成val
    
41.         pNew->data=val;
    
42.         //将新的节点的指针域指向下一个节点（每次压入都是压入栈顶的上方
    
43.         pNew->pNext=pS->pTop;
    
44.         //将pTop指向新的节点
    
45.         pS->pTop=pNew;
    
46. 
    
47. }
    
48. 
    
49. void traverse(PSTACK pS)
    
50. {
    
51.         //先定义一个p永远指向栈顶元素
    
52.         PNODE p=pS->pTop;
    
53.         while(p!=pS->pBottom)
    
54.         {
    
55.                 printf("%d ",p->data);
    
56.                 p=p->pNext;
    
57.         }
    
58.         printf("\n");
    
59.         return;
    
60. }
    
61. 
    
62. bool is_empty(PSTACK pS)
    
63. {
    
64.         if(pS->pTop==pS->pBottom)
    
65.                 return true;
    
66.         else
    
67.                 return false
    
68. }
    
69. 
    
70. //把pS所指向的栈出栈一次，并把出栈的元素存入pVal所指向的变量中，如果出栈失败，返回false
    
71. bool pop(PSTACK pS,int *pVal)
    
72. {
    
73.         if(is_empty(pS))  //pS本身存放的就是S的地址
    
74.                 return false;
    
75.         else
    
76.         {       
    
77.                 PNODE r=pS->pTop;
    
78.                 *pVal=r->data;
    
79.                 pS->pTop=r->pNext;
    
80.                 free(r);
    
81.                 r=NULL;
    
82.                 return true;
    
83.         }
    
84. 
    
85. }
    
86. 
    
87. void clear(PSTACK pS)  //清空
    
88. {
    
89.         if(is_empty(pS))
    
90.         {
    
91.                 return;
    
92.         }
    
93.         else
    
94.         {
    
95.                 PNODE p=pS->pTop;
    
96.                 PNODE q=NULL;
    
97.                 while(p!=pS->pBottom)
    
98.                 {
    
99.                         q=p->pNext;
    
100.                         free(p);
     
101.                         p=q;
     
102.                 }
     
103.                 pS->pTop=pS->pBottom;
     
104.         }
     
105. 
     
106. }
     
107. 
     
108. 
     
109. int main()
     
110. {
     
111.         int val;
     
112.         //相当于我们的S内存中有pTop pBottom两个变量，但是变量里面还没有存放有效的信息
     
113.         STACK S;  //STACK等价于struct Stack
     
114.         init(&S);  //目的是造出一个空栈
     
115.         push(&S,1);   //压栈
     
116.         push(&S,2);
     
117.         traverse(&S);  //遍历输出
     
118. 
     
119.         if(pop(&S,&val))
     
120.         {
     
121.                 printf("出栈成功，出栈的元素是:%d \n",val);
     
122.         }
     
123.         else
     
124.                 printf("出栈失败！");
     
125. 
     
126.         traverse(&S);  //遍历输出
     
127. 
     
128.         clear(&S);
     
129.         traverse(&S);  //遍历输出
     
130. 
     
131.         return 0;
     
132. }
     
133. 
     

复制代码

应用：
函数调用
中断
表达式求值
内存分配
缓冲处理
迷宫


线性结构的两种常见的应用之二：队列（先进先出）