<数据结构> 栈Stack

一.栈stack:先进后出 FILO

1.栈的主要功能是进行数据的存储和计算 栈是一种容器 是具有特殊限制的链表或数组

2.栈的存储方式:

①顺序存储:数组

空间固定 所以需要预先知道所需要开辟的空间有多大 数组难以进行扩容 所以导致可用空间是有限的

②链式存储:链表

栈可以理解为链表的头插头删 这种存储方式便于查找 又快又方便

3.栈的操作端为栈顶pTop 栈是没有栈底的概念的

4.栈的基本操作:

①栈的初始化init ②入栈压栈push ③出栈pop ④清空栈clear

⑤栈的销毁destroy ⑥获得栈顶元素 ⑦栈内总个数 ⑧栈是否为空

具体实现的时候 定义两个结构体 这样有利于栈的销毁的实现 具体代码如下:

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 
 4 typedef struct node
 5 {
 6     int num;
 7     struct node * pNext;
 8 }MyStack;
 9 
10 typedef struct node2
11 {
12     int count;
13     MyStack* pTop;
14 }Stack;
15 
16 void s_Init(Stack** ppStack)
17 {
18     (*ppStack) = (Stack*)malloc(sizeof(Stack));
19     (*ppStack) -> count = 0;
20     (*ppStack) -> pTop = NULL;
21 }
22 
23 void s_Push(Stack* pStack,int n)
24 {
25     if(pStack == NULL) return ;
26 
27     MyStack* pMyStack = (MyStack*)malloc(sizeof(MyStack));
28     pMyStack -> num = n;
29     pMyStack -> pNext = pStack -> pTop;
30     pStack -> pTop = pMyStack;
31 
32     pStack -> count ++;
33 }
34 
35 int s_Pop(Stack* pStack)
36 {
37     if(pStack == NULL || pStack -> count == 0) return -1;
38 
39     MyStack* pDel = pStack -> pTop;
40     int n = pDel -> num;
41     pStack -> pTop = pStack -> pTop -> pNext;
42     free(pDel);
43     pDel = NULL;
44 
45     pStack -> count --;
46     return n;
47 }
48 
49 void s_Clear(Stack* pStack)
50 {
51     while(pStack -> count != 0)
52     {
53         s_Pop(pStack);
54     }
55 }
56 
57 void s_Destroy(Stack** pStack)
58 {
59     s_Clear(*pStack);
60     free(*pStack);
61     *pStack = NULL;
62 }
63 
64 MyStack* s_GetTop(Stack* pStack)
65 {
66     return pStack -> pTop;
67 }
68 
69 int s_GetCount(Stack* pStack)
70 {
71     return pStack -> count;
72 }
73 
74 int s_IsEmpty(Stack* pStack)
75 {
76     return pStack -> count == 0? 1:0;
77 }
78 
79 int main()
80 {
81     Stack* pStack = NULL;
82     s_Init(&pStack);
83 
84     s_Push(pStack,10);
85     s_Push(pStack,11);
86     s_Push(pStack,12);
87     printf("Pop:%d\n",s_Pop(pStack));
88     printf("Pop:%d\n",s_Pop(pStack));
89     printf("Pop:%d\n",s_Pop(pStack));
90     printf("Count:%d",s_GetCount(pStack));
91 
92     return 0;
93 }

二.栈的应用

1.括号匹配问题:给一串如 ((())((()))) 这样的字符串 让我们判断括号数目是否匹配 就可以利用一个栈来解决这样的问题

解决:每当遇到“(”就入栈 遇到“)”就把栈中的一个“(”出栈

当栈中没有“(”可以出栈 或是 栈中最后剩余“(”没有括号与之进行匹配的时候 就说明这一串字符串括号是不匹配的 否则 括号匹配

2.递归就是一个入栈出栈的过程

PS:递归的适用场合:当处理大规模数据和处理小规模数据的方法一致时 可以使用递归

①著名的递归问题:斐波那契数列Fibonacci

F(1)=F(2)=1

F(n)=F(n-1)+F(n-2)

 1 #include<stdio.h>
 2 
 3 int Fib(int n)
 4 {
 5     if(n == 1 || n == 2) return 1;
 6     else
 7     {
 8         return Fib(n-1) + Fib(n-2);
 9     }
10 }
11 
12 int main()
13 {
14     printf("%d\n",Fib(10));
15     return 0;
16 }

当递归调用的次数较少时 输出结果还可以正常的输出 但是当n为40 50甚至更大的时候 程序的运行就速度会没有那么快 可能会卡一段时间

所以不妨利用循环的方式来解决递归问题

利用循环来解决Fibonacci问题

当n大于等于3的时候 可以把F(n)理解为c 把F(n-1)理解为b 那么F(n-2)即为a

利用循环 从3开始 不断的去更新a b和c这三个变量的值 去计算F(n)的值

实现代码如下:

 1 #include<stdio.h>
 2 
 3 int Fib(int n)
 4 {
 5     if(n == 1 || n == 2) return 1;
 6     else if(n >= 3)
 7     {
 8         int a = 1;
 9         int b = 1;
10         int c = 0;
11         int i = 3;
12         for(i;i<=n;i++)
13         {
14             c = a + b;
15             a = b;
16             b = c;
17         }
18         return c;
19     }
20 }
21 
22 int main()
23 {
24     printf("%d\n",Fib(10));
25     return 0;
26 }

递归和循环的比较

递归:利用递归来解决实际问题 会很慢

因为递归就是函数调用的过程 函数调用就是一个压栈出栈的问题 所以无论是时间还是空间都消耗巨大

但是递归的优点就是代码量少 实现起来只要逻辑理解了 就很简单

循环:循环相比递归利用的时间和空间就会小一些 但是劣势也很明显 就是代码量比较多

其实 利用栈和循环是可以替代递归的 数组也可以 只不过数组的话 需要提前预知开辟空间大小

④解决一个问题的最好方法 可能永远是数学问题吧 斐波那契数列的解决方法也有数学方法 这里就不说了 我自己理解起来都费劲

3.逆波兰表示法:四则运算

这里主要是 中缀表达式和后缀表达式之间的相互转换 先介绍一下规则

中缀转后缀规则:借助辅助栈

遇到数字或者字符直接打印

遇到符号 将符号与栈顶元素进行优先级比较:如果当前元素优先级高 则直接入栈 如果当前元素优先级低 则将栈内元素依次出栈

直到比当前元素优先级低为止 将当前元素入栈

如果遇到“(” 无条件入栈 如果遇到“)” 将栈内元素依次出栈 直到找到“(”为止

后缀转中缀规则:借助辅助栈

遇到数字或字符直接入栈

遇到符号 将栈顶元素的下一个和栈顶元素构成表达式

中缀转后缀的简便做法:

把所有的表达式括起来 然后把符号拿到所在的括号的外面并且去掉所有括号 即为后缀表达式

例如:(6+4)*9-8/2 → (((6+4)*9)-(8/2)) → 64+9*82/-