宜昌网站推广优化技巧_著名办公室装修公司_seo网络搜索引擎优化_电商运营方案

一、题目描述

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

输入：
["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

提示：

1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的（例如，一个空的队列不会调用 pop 或者 peek 操作）

二、解题思路

我们可以使用两个栈来实现队列的功能。一个栈用于入队操作（我们称之为 inStack），另一个栈用于出队操作（我们称之为 outStack）。以下是具体的操作步骤：

push(int x)：将元素 x 压入 inStack。
pop()：如果 outStack 为空，则将 inStack 中的所有元素依次弹出并压入 outStack，然后从 outStack 弹出栈顶元素。如果 outStack 不为空，直接从 outStack 弹出栈顶元素。
peek()：如果 outStack 为空，则将 inStack 中的所有元素依次弹出并压入 outStack，然后返回 outStack 的栈顶元素。如果 outStack 不为空，直接返回 outStack 的栈顶元素。
empty()：如果 inStack 和 outStack 都为空，则返回 true，否则返回 false。

三、具体代码

import java.util.Stack;class MyQueue {private Stack<Integer> inStack;private Stack<Integer> outStack;public MyQueue() {inStack = new Stack<>();outStack = new Stack<>();}public void push(int x) {inStack.push(x);}public int pop() {if (outStack.isEmpty()) {while (!inStack.isEmpty()) {outStack.push(inStack.pop());}}return outStack.pop();}public int peek() {if (outStack.isEmpty()) {while (!inStack.isEmpty()) {outStack.push(inStack.pop());}}return outStack.peek();}public boolean empty() {return inStack.isEmpty() && outStack.isEmpty();}
}/*** Your MyQueue object will be instantiated and called as such:* MyQueue obj = new MyQueue();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.peek();* boolean param_4 = obj.empty();*/

四、时间复杂度和空间复杂度

1. 时间复杂度

push(int x)：
- 这个方法直接将元素压入 inStack 栈中，时间复杂度为 O(1)。
pop()：
- 如果 outStack 为空，需要将 inStack 中的所有元素依次弹出并压入 outStack。在最坏的情况下，如果 inStack 包含所有元素，那么这个操作的时间复杂度为 O(n)，其中 n 是队列中元素的数量。
- 如果 outStack 不为空，直接从 outStack 弹出栈顶元素，时间复杂度为 O(1)。
- 由于每个元素最多只会从 inStack 移动到 outStack 一次，所以在均摊意义下，pop() 操作的时间复杂度为 O(1)。
peek()：
- 时间复杂度的分析同 pop() 方法。在最坏的情况下，时间复杂度为 O(n)，但均摊下来是 O(1)。
empty()：
- 检查两个栈是否为空，时间复杂度为 O(1)。

2. 空间复杂度

push(int x)：
- 每次调用 push 都会将一个新元素放入栈中，所以空间复杂度为 O(1)。
pop()：
- 这个方法不会增加额外的空间，空间复杂度为 O(1)。
peek()：
- 这个方法不会增加额外的空间，空间复杂度为 O(1)。
empty()：
- 这个方法不会增加额外的空间，空间复杂度为 O(1)。

总体空间复杂度：

在最坏的情况下，所有元素可能同时存在于两个栈中（例如，push 操作之后立即进行 pop 或 peek 操作之前），因此总的空间复杂度为 O(n)，其中 n 是队列中元素的数量。

五、总结知识点

类定义：
- 使用 class 关键字定义了一个名为 MyQueue 的类。
成员变量：
- 类中定义了两个 Stack<Integer> 类型的成员变量 inStack 和 outStack，用于模拟队列的行为。
构造方法：
- 定义了一个无参的构造方法 MyQueue()，用于初始化两个栈 inStack 和 outStack。
栈操作：
- 使用 push() 方法将元素压入栈中。
- 使用 pop() 方法从栈中移除并返回栈顶元素。
- 使用 peek() 方法返回栈顶元素但不从栈中移除它。
- 使用 isEmpty() 方法检查栈是否为空。
方法重载：
- 在 MyQueue 类中定义了四个方法：push(int x)、pop()、peek() 和 empty()，这些方法重载了 Stack 类中的一些方法，但具有不同的行为和用途。
逻辑控制：
- 在 pop() 和 peek() 方法中使用了 if 语句来检查 outStack 是否为空，如果为空，则将 inStack 中的所有元素转移到 outStack 中，这是实现队列功能的关键步骤。
循环结构：
- 使用了 while 循环在 pop() 和 peek() 方法中，当 outStack 为空时，将 inStack 中的所有元素移动到 outStack 中。
返回类型：
- pop() 和 peek() 方法返回 int 类型，表示队列中的元素。
- empty() 方法返回 boolean 类型，表示队列是否为空。
注释：
- 使用了多行注释 /** ... */ 来提供类的描述和使用示例。
接口与实现：
- MyQueue 类定义了一个接口，该接口可以被实例化并调用 push、pop、peek 和 empty 方法。
类型参数化：
- 使用了泛型 Stack<Integer> 来确保栈中只包含整数类型的元素。

以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。