232. 用栈实现队列

🟢 🔖 栈 设计 队列 🔗 力扣open in new window LeetCodeopen in new window

题目

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.

Notes:

You must use only standard operations of a stack, which means only push to top, peek/pop from top, size, and is empty operations are valid.
Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack's standard operations.

Example 1:

Input
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output
[null, null, null, 1, 1, false]
Explanation
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

Constraints:

1 <= x <= 9
At most 100 calls will be made to push, pop, peek, and empty.
All the calls to pop and peek are valid.

Follow-up: Can you implement the queue such that each operation is amortizedopen in new window O(1) time complexity? In other words, performing n operations will take overall O(n) time even if one of those operations may take longer.

题目大意

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

解题思路

使用两个栈，将一个栈当作输入栈，用于压入 push 传入的数据；另一个栈当作输出栈，用于 pop 和 peek 操作。

每次 pop 或 peek 时，若输出栈为空则将输入栈的全部数据依次弹出并压入输出栈，这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

代码

class MyQueue {
	constructor() {
		this.pushList = [];
		this.popList = [];
	}

	// @param {number} x
	// @return {void}
	push(x) {
		this.pushList.push(x);
	}

	// @return {number}
	pop() {
		if (this.popList.length === 0) {
			while (this.pushList.length > 0) {
				this.popList.push(this.pushList.pop());
			}
		}
		return this.popList.pop();
	}

	// @return {number}
	peek() {
		if (this.popList.length === 0) {
			while (this.pushList.length > 0) {
				this.popList.push(this.pushList.pop());
			}
		}
		return this.popList[this.popList.length - 1];
	}

	// @return {boolean}
	empty() {
		let len = this.pushList.length + this.popList.length;
		return len === 0;
	}
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * var obj = new MyQueue()
 * obj.push(x)
 * var param_2 = obj.pop()
 * var param_3 = obj.peek()
 * var param_4 = obj.empty()
 */

232. 用栈实现队列

# 232. 用栈实现队列

# 题目

# 题目大意

# 解题思路

# 代码

# 相关题目

232. 用栈实现队列

题目

题目大意

解题思路

代码

相关题目