简介
什么是栈？栈是一种只运行从一端插入和删除数据的线性表。一种形象的表示就像我们往一个大小受限的箩筐里放砖头，我们只能从从口放进去也只能从口取出来，而且是顺序的后进先出，不能从中间挑一个拿出来。栈主要有两个操作，一个入栈一个出栈。栈的实现方式可以用链表也可以用数组，我们将用数组来实现的栈叫做顺序栈，用链表实现的栈叫做链式栈。
实现
基于链表的链式栈java代码实现：
#Node.java
public class Node {
private int data;
public Node next;
public Node(int data){
this.data=data;
}
}
#linkStack.java
public class LinkStack {
Node top=null;
public boolean isEmpty(){
return top==null;
}
//入栈
public void push(int data){
Node newNode=new Node(data);
newNode.next=top;
top=newNode;
}
//出栈并移除栈顶
public Node pop(){
if (isEmpty()){
return null;
}
Node d=top;
top=top.next;
return d;
}
//进返回栈顶，不移除
public Node peek(){
if (isEmpty()){
return null;
}
return top;
}
}
对于数组方式的实现基本差别不大，这里就不写了。接下来探讨下栈操作的算法复杂度是多少。由于入栈和出栈操作都只有一个操作，所以时间复杂度为O（1）;那么对于空间复杂度呢？一个存储了n个数据的栈，空间复杂度是不是O（n）呢？其实不是，因为栈的两个操作入栈和出栈，运行时都只需一个到两个临时变量来做存储，我们在分析算法空间复杂度的时候是不需要将存储数据本来就需要的那些空间算进了的，所以空间复杂度也为O（1）。
动态扩容
上面提到的两种实现方法的栈有什么不一样呢？其实数组是一种固定大小的数据结构，正是由于这个特性，使得数组实现的链表所容纳的数据是受限的，当栈满了之后我们就无法继续添加数据了，而链表就不受这个限制，那么是不是就是说链表实现的栈比数组更好，我们应该不使用数组实现栈呢？其实不是的，链表实现的栈由于需要存储一个next指针，所以它每个节点都会比数组多消耗更多的内存空间。当然我们前面有些关于数组的文章，里面有提到数组的动态扩容是怎么实现，那么既然数组可以实现动态扩容，那么用数组实现的栈同样也可以做到动态扩容，这样就不会再有空间受限的问题了。当然扩容也同样会带来新的问题，就是在扩容时复杂度提高到O（n）。
动态扩容算法复杂度分析：
对于出栈操作，由于不会涉及到数据的搬移，所以复杂度无论何时都为O（1），那么入栈操作，当空间足够多时，也不需要数据搬移，所以复杂度也为O（1），但是当空间不足，需要扩容时，由于数组扩容需要将原有的数据搬移到新创建的数组中，这时复杂度就变为了O（n），所以对于入栈操作，最好情况时间复杂度为O（1），最坏为O（n），那么平静是多少呢？前面的文章有介绍过平均时间复杂度如何求。我们会用到摊还分析法。我们这里约定每次扩容都为原数组大小的2倍，当前满栈为k个数据，并且不涉及出栈操作，所以达到扩容条件时进行了k此O（1）的入栈操作，而后会进行k个数据的数组内存搬移操作，将k个搬移操作均摊到每次入栈操作，就能得到均摊时间复杂度为O（1）。
栈的应用
我们写代码时函数的调用就是用类似栈的数据结构来存储调用的函数的，这里我们来分析一个用栈来实现表达式求值的一个例子。用计算机的思维来求解：1+2*3-4这个表达式，
实际上计算机是通过两个栈来实现这些运算操作的，其中一个栈用来保存操作的数，另一个用来保存运算符。它先从左到右遍历表达式，当遇到数字就直接压入操作数栈，当遇到云算符，就与云算符栈顶元素进行比较，如果当前运算符比栈顶运算符的优先级高，就将当前运算符压入运算符栈栈顶，如果当前运算符比栈顶运算符优先级低或者相等，就从数字栈取出两个操作数来进行运算，运算结果压入数字栈顶，然后继续与运算符栈栈顶进行比较，进行跟前面一样的操作，知道整个表达式运算完成。
栈应用示意图.png
关于栈的学习就先到这里了。
网友评论