摘要
一文掌握栈的四大经典应用场景：括号配对，表达式求值，浏览器前进后退，函数调用；手把手实现一个简易版本的计算器。
什么是栈
我们来看一下百度百科中对栈的定义：栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。
向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。
栈的实现
栈和数组，链表一样，也是一种线性的数据结构。在有些编程语言中并没有栈这种数据结构，但是要实现一个栈却也简单，通过数组或者链表都可以来实现一个栈。
通过数组实现
在 Java 中，栈（Stack 类）就是通过数组来实现的，下面我们就自己利用数组来实现一个简单的栈：
package com.lonely.wolf.note.stack;
import java.util.Arrays;
/**
* 基于数组来实现自定义栈
*/
public class MyStackByArray<E> {
public static void main(String[] args) {
MyStackByArray stack = new MyStackByArray();
stack.push(1);
System.out.println("stack有效元素个数：" + stack.size);//输出 1
System.out.println("查看栈顶元素：" + stack.peek());//输出 1
System.out.println("栈是否为空：" + stack.isEmpty());//输出 false
System.out.println("弹出栈顶元素：" + stack.pop());// 输出 1
System.out.println("栈是否为空：" + stack.isEmpty());//输出 true
stack.push(2);
stack.push(3);
stack.push(4);
System.out.println("stack有效元素个数：" + stack.size);//输出 3
System.out.println("弹出栈顶元素：" + stack.pop()); //输出 4
}
private Object[] element;//存储元素的数组
private int size;//栈内有效元素
private int DEFAULT_SIZE = 2;//默认数组大小
public MyStackByArray() {
element = new Object[DEFAULT_SIZE];
}
/**
* 判断是否为空，注意不能直接用数组的长度
* @return
*/
public boolean isEmpty(){
return size == 0;
}
/**
* 查看栈顶元素
* @return
*/
public synchronized E peek() {
if (size == 0){
return null;
}
return (E)element[size-1];
}
/**
* 查看并弹出栈顶元素
* @return
*/
public E pop() {
if (size == 0){
return null;
}
E obj = peek();
size--;//利用 size 属性省略元素的移除
return obj;
}
/**
* 压栈
* @param item
* @return
*/
public E push(E item) {
ensureCapacityAndGrow();
element[size++] = item;
return item;
}
/**
* 扩容
*/
private void ensureCapacityAndGrow() {
int len = element.length;
if (size + 1 > len){//扩容
element = Arrays.copyOf(element,len * 2);
}
}
}
复制代码通过队列实现
除了通过数组，其实通过链表等其他数据结构也能实现，实现栈最关键就是要注意栈的后进先出特性。
在 leetcode 中的第 225 是利用两个队列来实现一个栈，具体要求是这样的：
请你仅使⽤两个队列实现⼀个后⼊先出（LIFO）的栈，并⽀持普通栈的全部四种操作（push、top、pop 和 empty），你只能使用队列的基本操作（也就是 push to back、peek/pop from front、size 和 is empty 这些操作）。
在解决这个问题之前，我们先要明白队列的特性，队列最主要的一个特性就是先进先出，所以我们不管先把元素放到哪个队列，最后出来的元素依然是先进先出，似乎实现不了栈的后进先出特性。
实现思路
为了满足栈的特性，我们就必须要让先入队的元素最后出队，所以我们可以这么做：
使用一个队列作为主队列，每次出栈都从主队列（mainQqueue）获取元素，另外一个队列作为辅助队列（secondQueue），仅仅用来存储元素，每次存储元素的时候先存入 secondQueue，然后将 mainQueue 内的元素依次放入 secondQueue，最后再将两个队列互换，这样每次出队的时候只需要从 mainQueue 依次获取元素即可。
下面我们一起来画一个流程图帮助理解这个过程：
- 放入元素
1。
先将元素放入 secondQqueue，这时候 mainQueue 为空，所以不需要移动元素，直接交换两个队列即可，所以最终得到的依然是 mainQueue 内有一个元素 1，而 secondQueue 中没有元素：
- 继续放入元素
2。
这时候元素 2 依然先放入 secondQqueue，然后此时发现 mainQueue 里面有元素，一次取出来，入队 secondQueue，然后继续将两个队列交换：
- 继续放入元素
3。
继续放入元素 3 也是一样的道理，依然先放入 secondQqueue，然后将 mainQueue 中的两个元素一次放回到 secondQueue，最后再将两个队列进行交换：
大部分算法都是这样，关键是理清思路，思路理清了剩下的就是代码翻译的过程，这个过程只要做好好边界控制及其他注意事项，相对来说就比较容易实现了：
package com.lonely.wolf.note.stack;
import java.util.LinkedList;
import java.util.Queue;
public class MyStackByTwoQueue {
public static void main(String[] args) {
MyStackByTwoQueue queue = new MyStackByTwoQueue();
queue.push(1);
queue.push(2);
System.out.println(queue.pop());
}
private Queue<Integer> mainQueue = new LinkedList<>();
private Queue<Integer> secondQueue = new LinkedList<>();
public void push(int e){
secondQueue.add(e);
if (!mainQueue.isEmpty()){
secondQueue.add(mainQueue.poll());
}
//交换连个 queue，此时新加入的元素 e 即为 mainQueue 的头部元素
Queue temp = mainQueue;
mainQueue = secondQueue;
secondQueue = temp;
}
public int top(){
return mainQueue.peek();
}
public int pop(){
return mainQueue.poll();
}
public boolean empty() {
return mainQueue.isEmpty();
}
}
复制代码栈的经典应用场景
因为栈是一种操作受限的数据结构，所以其使用场景也比较有限，下面我们列举几个比较经典的应用场景。
浏览器前进后退
浏览器的前进后退就是典型的先进后出，因为有前进后退，所以我们需要定义两个栈：forwardStack 和 backStack。当我们从页面 1 访问到页面 4，那么我们就把访问过的页面依次压入 backStack：
后退的时候直接从 backStack 出栈就可以了，当 backStack 为空就说明不能继续后退了；而且当从 backStack 出栈的同时又将页面压入 forwardStack，这样前进的时候就可以从 forwardStack 依次出栈：
括号配对
利用栈来验证一个字符串中的括号是否完全配对会非常简单，因为右括号一定是和最靠近自己的一个左括号配对的，这就满足了后进先出的特性。所以我们可以直接遍历字符串，遇到左括号就入栈，遇到右括号就看看是否和当前栈顶的括号匹配，如果不匹配则不合法，如果匹配则将栈顶元素出栈，并继续循环，直到循环完整个字符串之后，如果栈为空就说明括号恰好全部配对，当前字符串是有效的。
leetcode 20 题
在 leetcode 中的第 20 题就是一道括号配对的题，题目是这样的：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合；左括号必须以正确的顺序闭合。
知道了上面的解题思路，代码实现起来还是比较简单的：
public static boolean isValid(String s){
if (null == s || s.length() == 0){
return false;
}
Stack<Character> stack = new Stack<>();
Map<Character,Character> map = new HashMap<>();
map.put(')','(');
map.put(']','[');
map.put('}','{');
for (int i=0;i<s.length();i++){
char c = s.charAt(i);
if (c == '(' || c == '[' || c == '{'){
stack.push(c);//左括号入栈
}else{
if (stack.isEmpty() || map.get(c) != stack.peek()){
return false;
}
stack.pop();//配对成功则出栈
}
}
return stack.isEmpty();
}
复制代码表达式求值
算法表达式也是栈的一个经典应用场景，为了方便讲解，我们假设表达式中只有 +、-、*、/ 四种符号，然后我们要对表示式 18-12/3+5*4 进行求解应该如何做呢？
其实这道题也可以利用两个栈来实现，其中一个用来保存操作数，称之为操作数栈，另一个栈用来保存运算符，称之为运算符栈。具体思路如下：
- 遍历表达式，当遇到操作数，将其压入操作数栈。
- 遇到运算符时，如果运算符栈为空，则直接将其压入运算符栈。
- 如果运算符栈不为空，那就与运算符栈顶元素进行比较：如果当前运算符优先级比栈顶运算符高，则继续将其压入运算符栈，如果当前运算符优先级比栈顶运算符低或者相等，则从操作数符栈顶取两个元素，从栈顶取出运算符进行运算，并将运算结果压入操作数栈。
- 继续将当前运算符与运算符栈顶元素比较。
- 继续按照以上步骤进行遍历，当遍历结束之后，则将当前两个栈内元素取出来进行运算即可得到最终结果。
leetcode 227 题
题目：给你一个有效的字符串表达式 s，请你实现一个基本计算器来计算并返回它的值，整数除法仅保留整数部分，s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开。
这道题目可以利用我们上面讲述的思路进行解决，不过除此之外，在审题时我们应该还需要考虑两个点：
- 表达式中有空格，我们需要将空格处理掉
- 操作数可能有多位，也就是说我们需要将操作数先计算出来。
使用两个栈求解
这道题如果我们按照上面的思路，使用两个栈来做的话，虽然代码有点繁琐，但是思路还是清晰的，具体代码如下：
public static int calculateByTwoStack(String s){
if (null == s || s.length() == 0){
return 0;
}
Stack<Integer> numStack = new Stack<>();//操作数栈
Stack<Character> operatorStack = new Stack<>();//运算符栈
int num = 0;
for (int i = 0;i<s.length();i++){
char c = s.charAt(i);
if (Character.isDigit(c)){//数字
num = num * 10 + (c - '0');
if (i == s.length() - 1 || s.charAt(i+1) == ' '){//如果是最后一位或者下一位是空格，需要将数字入栈
numStack.push(num);
num = 0;
}
continue;
}
if (c == '+' || c == '-' || c == '*' || c == '/'){
if (s.charAt(i-1) != ' '){//如果前一位不是空格，那需要将整数入栈
numStack.push(num);
num = 0;
}
if (c == '*' || c == '/'){//如果是乘除法，那么需要将当前运算法栈内的乘除法先计算出来
while (!operatorStack.isEmpty() && (operatorStack.peek() == '*' || operatorStack.peek() == '/')){
numStack.push(sum(numStack,operatorStack.pop()));//将计算出的结果再次入栈
}
} else {//如果是加减法，优先级已经是最低，那么当前运算符栈内所有数据都需要被计算掉
while (!operatorStack.isEmpty()){
numStack.push(sum(numStack,operatorStack.pop()));
}
}
operatorStack.push(c);
}
}
//最后开始遍历：两个操作数，一个运算符进行计算
while (!numStack.isEmpty() && !operatorStack.isEmpty()){
numStack.push(sum(numStack,operatorStack.pop()));//计算结果再次入栈
}
return numStack.pop();//最后一定剩余一个结果入栈了
}
private static int sum(Stack<Integer> numStack,char operator){
int num1 = numStack.pop();
int num2 = numStack.pop();
int result = 0;
switch (operator){
case '+':
result = num2 + num1;
break;
case '-':
result = num2 - num1;
break;
case '*':
result = num2 * num1;
break;
case '/':
result = num2 / num1;
break;
default:
}
return result;
}
复制代码上面题目中我们也可以先使用正则把表达式中所有空格去除，这样的话也可以省去空格的判断
使用一个栈求解
其实这道题因为只有加减乘除法，所以我们其实可以取巧，只利用一个栈也可以实现。
因为乘除法一定优先于加减法，所以可以先把乘除法计算出来后将得到的结果放回表达式中，最后得到的整个表达式就是加减法运算，具体做法为：
遍历字符串 s，并用变量 preOperator 记录每个数字之前的运算符，对于表达式中的第一个数字，我们可以默认其前一个运算符为加号。每次遍历到数字末尾时（即：读到一个运算符，或者读到一个空格，或者遍历到字符串末尾），根据 preOperator 来决定计算方式：
- 加号：将数字直接压入栈内。
- 减号：将对应的负数压入栈内。
- 乘/除号：计算数字与栈顶元素，并将栈顶元素替换为计算结果。
这样最终只需要将栈内的所有数据相加就可以得到结果，具体代码示例如下：
public static int calculateOneStack(String s){
if (null == s || s.length() == 0){
return 0;
}
Stack<Integer> stack = new Stack<>();
char preOperator = '+';//默认前一个操作符是加号
int num = 0;
for (int i = 0;i<s.length();i++){
char c = s.charAt(i);
if (Character.isDigit(c)){
num = num * 10 + (c - '0');
}
if ((!Character.isDigit(c) && c != ' ') || i == s.length()-1){//判断数字处理是否已经结束，如果结束需要将数字入栈或者计算结果入栈
switch (preOperator){
case '+':
stack.push(num);//加法则直接将数字入栈
break;
case '-':
stack.push(-num);//减法则将负数入栈
break;
case '*':
stack.push(stack.pop() * num);//乘法则需要计算结果入栈
break;
case '/':
stack.push(stack.pop() / num);//除法则需要计算结果入栈
break;
default:
}
preOperator = c;
num = 0;
}
}
int result = 0;
while (!stack.isEmpty()){//最后将栈内所有数据相加即可得到结果
result+=stack.pop();
}
return result;
}
复制代码函数调用
除了上面的三个经典场景，其实我们平常的方法调用也是用的栈来实现的，我们每次调用一个新的方法就会定义一个临时变量，并将其作为一个栈帧进行入栈，当方法执行完毕之后，就会将当前方法对应的栈帧进行出栈。
总结
本文主要讲述了栈这种操作受限的数据结构，并通过数组实现了一个简易版的栈，同时讲述了如何通过两个队列实现一个栈。最后我们列举了栈的四大经典应用场景：括号配对，表达式求值，浏览器前进后退，函数调用等，而其中括号配对和表达式求值这两种场景又会衍生出不同的算法题
原文链接：https://juejin.cn/post/7051435936134987784
如果你觉的本文对你有帮助，麻烦点赞关注支持一下
京公网安备 11010502036488号