栈

栈的结构

栈是一种“后进先出，先进后出”的结构，如果你的数据具备这种特点，就可以用栈这种东西。

栈既可以用数组实现，也可以用链表实现，用数组实现的叫顺序栈，用链表实现的叫链式栈。

顺序栈还是链式栈，因为只有栈顶可以插入和删除，所以它们的插入和删除的时间复杂度都为o(1)。

栈的应用举例

1.存储函数里的临时变量

image

存储临时变量

2.求值表达式( 3+5*8-6)

通过两个栈，一个栈存数字，一个栈存运算符。遇到数字就存入栈，遇到运算符就与栈顶的首个运算符比较优先级，如果高于就直接入栈，如果等于或小于就取出两个数字与当前的栈顶运算符进行计算。

image

编译器求值表达式

3.匹配括号({[{}]})

拿出一个栈，如果与栈顶的括号不匹配就入栈，如果匹配就把栈顶的括号删除。

4.浏览器页面的前进后退

用两个栈，一个栈用来存储一直向前点的页面，一个栈用来存储后退的页面。如果用户点击后退就从后退栈里取出栈顶页面压入前进栈，如果用户点击向前则从前进栈中的栈顶页面压入后退栈。参考代码

数组实现栈

大致思路是，先确定一个数组的大小，设置一个int的变量，使这个变量每次增加数据就+1，放在数据的上一格。如果要出栈，就把变量的下一个数组元素弄出来，变量也跟随-1到这个数组元素的小标(其实数组元素并未删除)。入栈和出栈需要先判断栈内的条件。

image

数组实现栈

链表实现栈

大致思路是，用一个结点来代替刚才的int变量，入栈时，就新创建一个结点，然后把这个结点的next往回设为top，然后把top结点变成最新的结点。出栈的时候，就是先取出top的值，然后把top往回设置为top.next。注意出入栈的判断条件。

image

链表实现栈