栈：数据结构与算法系列深度解析

发表时间: 2019-03-10 10:01

什么是栈

栈是一种运算受限制的线性表，只允许在表的一端进行插入和删除操作。这一端被称为栈顶，另一端被称为栈底。向一个栈中插入新数据叫做进栈、入栈或者压栈，是把新元素放到栈顶上边，使其成为新的栈顶元素；删除数据叫做出栈或者退栈，就是把栈顶的元素删掉，使其下边的元素称为新的栈顶元素。

举一个容易理解的例子，就是有一摞盘子，我们用的时候从上往下一个一个取，放的时候都是从下往上一个一个放，一般不从中间取或者放。这种先进后出，后进先出的数据结构就是栈。

这种操作受限的数据结构在什么情况下用呢，我们为什么不能用操作更为方便的数组或者链表呢。当某个数据只涉及在一端的插入和删除数据，并满足先进后出，后进先出的特点，我们就可以用栈这种数据结构，而数组和链表因为操作的灵活性，有时候会使一些数据不可控，更容易出现错误。

栈的实现

从功能上，我们是可以用数组和链表来实现栈，只要实现栈的入栈和出栈的操作，即从栈顶插入新的数据，从栈顶删除数据。用数组实现的栈叫做顺序栈，用链表实现的栈叫做链表栈。下边我们分别看一下用数组和链表实现栈的代码。这里用Java代码实现。

数组实现

//基于数组实现的栈public class ArrayStack{ //数组 private String[] items; //栈的大小 private int length; //栈中元素的个数 private int count; public ArrayStack(int len){ items = new String[len]; length = len; count = 0; } //入栈 public boolean Push(String x){ //数组空间不足 if(count == length){ return false; } items[count] = x; count++; return true; } //出栈 public String Pop(){ //栈为空 if(count == 0){ return null; } String tem = items[count-1]; count--; return tem; }}

链表实现

//基于链表实现的栈public class ListNodeStack { private ListNode top; //进栈 public void Push(int val) { ListNode node = new ListNode(val, null); if (top == null) { top = node; } else { node.next = top; top = node; } } //出栈 public int Pop() { if (top == null) { return -1; } int val = top.val; top = top.next; return val; } //链表的结点 class ListNode { private int val; private ListNode next; public ListNode(int x, ListNode next) { val = x; this.next = next; } public int GetValue() { return val; } }}

上边代码用数组实现的栈是一个固定大小的栈，当栈满了之后就没法办插入新的数据了，那么我们能不能用数组实现一个动态扩容的栈呢？前边我们将数组的时候说过，实现一个动态扩容的数组，是在数组满了的时候，我们重新创建一个大小为原来两倍的数组，然后把原来数组的数据拷贝到新的数组中，所以我们也可以用这个方法来实现一个动态扩容的栈。我们看一下代码实现。

//基于数组实现的栈public class ArrayStack { //数组 private String[] items; //栈的大小 private int length; //栈中元素的个数 private int count; public ArrayStack(int len) { items = new String[len]; length = len; count = 0; } //入栈 public void Push(String x) { //数组空间不足 if (count == length) { DilatationArray(); } items[count] = x; count++; } //出栈 public String Pop() { //栈为空 if (count == 0) { return null; } String tem = items[count - 1]; count--; return tem; } //数组扩容 private void DilatationArray() { String[] newArray = new String[length * 2]; for (int i = 0; i < length; i++) { newArray[i] = items[I]; } items = newArray; }}

栈的实际应用

在函数调用中的应用

在Java的虚拟机中有一个内存区域被称为虚拟机栈。每个方法在执行的时候都会创建一个“栈帧”。用来存储局部变量表（包括参数）、操作栈、动态链接、方法出口等信息。每个方法从调用到结束就会有栈帧在虚拟机栈中入栈和出栈。

举一个简单的例子。

public class AddClass{ public int Main(){ int a = 0; int b = 5; int c = 0; a = Add(2, 3); c = a + b; return c; } public int Add(int x, int y){ int sum = 0; sum = x + y; return sum; }}

从代码中我们看到 Main 方法中首先声明了几个变量，然后调用了 Add 方法，然后经过一些运算，最后返回一个值。我们画图来更直观的看一下这个过程。

image.png

在表达式求值中的应用

编辑器的表达式求值的过程，就是用栈来实现的。我们举一个简单的四则运算的表达式的求值过程来看一下。例如：1+2*3-4/2。编辑器是怎么计算来得到最后的值呢。

这个求值过程，编辑器是用两个栈来实现的，一个保存数字的栈，一个保存运算符号的栈。我们从左向右遍历表达式，当遇到数字的时候把它压入数字栈，当遇到运算符号的时候，就与运算符栈的栈顶的运算符比较，如果比栈顶的运算符优先级高，就直接压入运算符栈，如果比栈顶的运算符优先级低或者相同，那么就从运算符栈取出栈顶运算符号，从数字栈中取出两个数字进行计算，然后把结果压入数字栈，然后继续比较，依次类推，知道最后。

我们为了更形象的理解，也用画图的方式来展示一下这个过程。