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

一、栈的应用

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;
    }
}