Leetcode 分类刷题 —— 栈（Stack）

1、题目描述：

Leetcode 232. Implement Queue using Stacks

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty).
Implement the MyQueue class:
void push(int x) Pushes element x to the back of the queue.
int pop() Removes the element from the front of the queue and returns it.
int peek() Returns the element at the front of the queue.
boolean empty() Returns true if the queue is empty, false otherwise.

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

2、解题思路：

队列的特性是 FIFO （先入先出），而栈的特性是 FILO （先入后出）。
知道两者特性之后，我们便能用两个栈来模拟队列的特性，一个栈为入队栈，一个栈为出对栈。

3、代码

class MyQueue {
    private Stack<Integer> inputStack; // 输入栈
    private Stack<Integer> outputStack; // 输出栈

    /** Initialize your data structure here. */
    public MyQueue() {
        inputStack = new Stack<>();
        outputStack = new Stack<>();
    }
    
    /** Push element x to the back of queue. */
    public void push(int x) {
        inputStack.push(x); // 将元素入输入栈
    }
    
    /** Removes the element from in front of queue and returns that element. */
    public int pop() {
        peek(); // 先调用 peek() 方法
        return outputStack.pop(); // 将输出栈顶元素出栈并返回
    }
    
    /** Get the front element. */
    public int peek() {
        if (outputStack.isEmpty()) {
            // 如果输出栈为空，则将输入栈的元素全部弹出并压入输出栈
            while (!inputStack.isEmpty()) {
                outputStack.push(inputStack.pop());
            }
        }
        return outputStack.peek(); // 返回输出栈顶元素
    }
    
    /** Returns whether the queue is empty. */
    public boolean empty() {
        return inputStack.isEmpty() && outputStack.isEmpty(); // 只有当输入栈和输出栈都为空时，队列才为空
    }
}