【40讲系列2】栈、队列

一、栈和队列的特点，使用场景

　　栈（Stack）是限定仅在表尾进行插入和删除操作的线性表，后进先出。

　　队列（Queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表，先进先出。

二、代码实现

对于队列，LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。

　　Queue<Integer> queue = new LinkedList<>(); // 队列在使用时，尽量用offer()和poll()，优点是通过返回的布尔值可以判断成功与否，add()和remove()方法在失败的时候会抛出异常。

对于栈，一般可以使用 Stack<Integer> stack = new Stack<>();

　　但是，由于历史问题，Java官方的Stack类已经不建议使用，建议使用 Deque<Integer> stack = new ArrayDeque<>(); 注意只使用这个类中关于栈的接口。

　　入栈：addLast(), 不建议使用add()，因为 add() 依然是调用addLast()，使用addLast()语义更清晰

　　出栈：removeLast() 或者 pollLast()， removeLast() 依然是调用pollLast()。注意不要使用poll()，因为poll()调用pollFirst()，不符合栈的语义。

三、基本应用

栈：使用栈模拟系统栈，写出非递归的程序。

队列：广度优先遍历

　　- 树 -> 层序遍历；图 -> 无权图的最短路径

四、典型例题

①：判断括号字符串是否有效

LeetCode20-括号的匹配

②：用栈实现队列（LC232、剑指05.用两个栈实现队列）

③：用队列实现栈（LC225）

class MyStack {

    Queue<Integer> queue;
    /** Initialize your data structure here. */
    public MyStack() {
        queue = new LinkedList<>();
    }
    
    /** Push element x onto stack. */
    public void push(int x) {
        queue.offer(x);
        for (int i = 0; i < queue.size() - 1; i++) {
            queue.offer(queue.poll());
        }
    }
    
    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        return queue.poll();
    }
    
    /** Get the top element. */
    public int top() {
        return queue.peek();
    }
    
    /** Returns whether the stack is empty. */
    public boolean empty() {
        return queue.isEmpty();
    }
}

五、扩展例题——栈

第一组（栈的基础应用）：LeetCode20. 有效的括号、LeetCode150. 逆波兰表达式求值、LeetCode71. 简化路径

第二组（栈模拟递归）：LeetCode144. 二叉树的前序遍历、LeetCode94. 二叉树的中序遍历、LeetCode145. 二叉树的后序遍历、LeetCode341. 扁平化嵌套列表迭代器

六、扩展例题——队列

第一组（二叉树的BFS）：LeetCode102. 二叉树的层序遍历、LeetCode107. 二叉树的层次遍历 II、LeetCode103. 二叉树的锯齿形层次遍历、LeetCode199. 二叉树的右视图

第二组（BFS和图的最短路径）：LeetCode279. 完全平方数、LeetCode127. 单词接龙、LeetCode126. 单词接龙 II