力扣刷题笔记232

力扣刷题笔记232 题号：232. 用栈实现队列 简介：

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有 *** 作（push、pop、peek、empty）：

实现 MyQueue 类：

void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

你只能使用标准的栈 *** 作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty *** 作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈 *** 作即可。

进阶：

你能否实现每个 *** 作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个 *** 作的总时间复杂度为 O(n) ，即使其中一个 *** 作可能花费较长时间。

示例：

输入：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

题解：

首先我们要了解队列的特点 ：先进先出
然后根据栈先进后出的特点，我们可以借助两个栈来实现一个队列
首先准备两个栈

进行入队 *** 作时，即输入栈入栈即可,多入几个效果明显一些

执行出队 *** 作，我们需要先将输入栈中的内容转到输出栈中，然后输出栈输出

这样就借助两个栈实现了入队出队 *** 作

代码：

class MyQueue {
    public Stack stack;
    public Stack stack1;
    public MyQueue() {
        // 负责进栈
        stack = new Stack();
        // 负责出栈
        stack1 = new Stack();
    }
    
    public void push(int x) {
        stack.push(x);
    }
    
    public int pop() {
    // 只有当输出栈空时，才能将输入栈中的内容转出
        if (stack1.isEmpty()) {
            zhuanhuan();
        }
       return stack1.pop();
    }
    
    public int peek() {
        if (stack1.isEmpty()){
        zhuanhuan();
        }
        return stack1.peek();
    }
    
    public boolean empty() {
        return stack.isEmpty()&&stack1.isEmpty();
    }

    public void zhuanhuan(){
        while (!stack.isEmpty()) {
            stack1.push(stack.pop());
        }
    }
}