【3.5】LeetCode每日一题· 用栈实现队列

2021年03月05日 10时55分

标签： LeetCode 栈

## 题目描述
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作（`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

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

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/implement-queue-using-stacks/ "题目链接")

## 解题思路
使用两个栈实现，一个为输入栈，一个为输出栈。当执行**push**操作时，往输入栈中压入数字。当执行**pop**或**peek**操作时，访问输出栈的栈顶元素。如果输出栈为空，就将输入栈中的所有数字压入输出栈中。由于输入栈是**先进后出的**，因此输出栈是**先进先出**的，满足队列的要求。判断队列为空，只需判断是否两个栈均为空即可。

对于所有元素，其出栈时最多被访问过两次（一次输入栈移入输出栈，一次输出栈弹出），因此总时间复杂度为$$O(N)$$，因此每个**pop/peek**操作的均摊时间复杂度为$$O(1)$$。**push**操作的时间复杂度为$$O(1)$$，**empty**操作的时间复杂度也为$$O(1)$$，因此每个操作的均摊时间复杂度为$$O(1)$$。

## 代码
	class MyQueue {
	public:
		stack<int> inputs;
		stack<int> outputs;

/** Initialize your data structure here. */
		MyQueue() {

}

/** Push element x to the back of queue. */
		void push(int x) {
			inputs.push(x);
		}

/** Removes the element from in front of queue and returns that element. */
		int pop() {
			if(outputs.empty()){
				while(inputs.size()){
					outputs.push(inputs.top()); inputs.pop();
				}
			}
			int ans = outputs.top(); outputs.pop();
			return ans;
		}

/** Get the front element. */
		int peek() {
			if(outputs.empty()){
				while(inputs.size()){
					outputs.push(inputs.top()); inputs.pop();
				}
			}
			return outputs.top();
		}

/** Returns whether the queue is empty. */
		bool empty() {
			return inputs.empty() && outputs.empty();
		}
	};

/**
	 * 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();
	 * bool param_4 = obj->empty();
	 */

#### 用时和内存
> 执行用时：0 ms，在所有 C\++提交中击败了100.00%的用户
> 内存消耗：6.8 MB，在所有 C\++提交中击败了66.02%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【3.5】LeetCode每日一题· 用栈实现队列

所有评论

暂无评论

新增评论