数据结构之栈和队列的应用

一、栈的应用

1. 括号匹配

2. 计算后缀表达式

方法一（栈）

方法二（数组模拟栈）

二、队列应用

1. 二叉树层序遍历

方法一（队列）

三、总结

一、栈的应用

1. 括号匹配

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

class Solution {public boolean isValid(String s) {// 判断括号数是否匹配if (s.length() %2 == 1) {return false;}Stack<Character> S = new Stack();for (int i = 0; i < s.length(); ++i) {char ele = s.charAt(i);// 左括号if (containLeft(ele)) {S.push(ele);} else {if (S.empty()) {return false;}// 右括号if (CompareTo(S.peek(), ele)) {// 将栈顶元素弹出S.pop();} else {return false;}}}return S.empty() ? true : false;}// 包含左括号
public static boolean containLeft(char ch) {if (ch == '{') return true;if (ch == '(') return true;if (ch == '[') return true;return false;
}//  检验括号是否匹配public static boolean CompareTo(char forth, char latter) {if ((forth == '{' && latter == '}') || (forth == '(' && latter == ')') || (forth == '[' && latter == ']')) {return true;}return false;}
}

2. 计算后缀表达式

根据逆波兰表示法，求该后缀表达式的计算结果。

有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

后缀表达式按照从左到右的运算规则，计算表达式需要一个栈存放操作数；假设表达式成立，依次获取每一个字符串，如果字符串是操作数，则直接入栈，如果字符串是操作符，出栈两次，首先出栈的是右操作数，后出栈的是左操作数，将运算得到的新操作数入栈。

方法一（栈）

class Solution {public int evalRPN(String[] tokens) {Stack<Integer> S = new Stack<>();int i = 0;while (i < tokens.length) {String token = tokens[i++];if (isNumber(token)) {S.push(Integer.parseInt(token));} else {int num2 = S.pop();int num1 = S.pop();switch(token) {case "+":S.push(num1 + num2);break;case "-":S.push(num1 - num2);break;case "*":S.push(num1 * num2);break;case "/":S.push(num1 / num2);break;default:}}}return S.pop();}public boolean isNumber(String token) {return !("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token));}
}

方法二（数组模拟栈）

class Solution {public int evalRPN(String[] tokens) {int n = tokens.length;int[] stack = new int[(n + 1) / 2];int index = -1;for (int i = 0; i < n; i++) {String token = tokens[i];switch(token) {case "+":index--;stack[index] += stack[index + 1];break;case "-":index--;stack[index] -= stack[index + 1];break;case "*":index--;stack[index] *= stack[index + 1];break;case "/":index--;stack[index] /= stack[index + 1];break;default:index++;stack[index] = Integer.parseInt(token);}}return stack[index];}
}

二、队列应用

1. 二叉树层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

 /** public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
public List<Integer> levelOrder(TreeNode node) {// 定义res存储结点的值List<Integer> res = new LinkedList<>();Queue<TreeNode> queue = new LinkedList<>();if (node != null) {queue.offer(node);}while (!queue.isEmpty()) {TreeNode ele = queue.poll();res.add(ele.val);// 判断结点是否有左右孩子if (ele.left != null) {queue.offer(ele.left);}if (ele.right != null) {queue.offer(ele.right);}}return res;
}

不同于题目的是，返回一个一维列表，但如果需要返回二维列表，我们不仅要实现层序遍历，还需要将同一层的结点放到一起。显然，上述的算法无法解决这个问题。

既然一个一个迭代无法满足要求，那么我们就可以考虑一层一层迭代。

我们定义一个队列，队列中存放同一层的结点。那么我们需要考虑如何迭代一层结点？

假设队列中存放了根节点root，此时队列的长度为1，那么我们迭代一次就可以让第一层所有结点出队。出队的同时，会将root的子节点存放到队列中。

此时队列的长度为2，我们迭代两次可以让第二层所有的结点出队，出队同时会让出队元素的子结点入队，且队列满足FIFO特点，因而可以保证从左至右遍历。

归纳总结可知，迭代的次数等于前一层的入队元素个数，因为出队同时要进队，因而前一层全部出队后，队列中的一定是当前层的元素，而且队列的长度一定等于当前层的结点个数，按照这个过程迭代，直至遍历完所有结点。

方法一（队列）

 /** public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList();if (root == null) {return res;}Queue<TreeNode> queue = new LinkedList<TreeNode>();queue.offer(root);while (! queue.isEmpty()) {List<Integer> level = new ArrayList<>();int currentLevelSize = queue.size();for (int i = 0; i < currentLevelSize; ++i) {TreeNode node = queue.poll();level.add(node);if (node.left != null) {queue.offer(node.left);}if (node.right != null) {queue.offer(node.right);}}res.add(level);}return res;}
}