跳至主要內容

9. 用两个栈实现队列


9. 用两个栈实现队列open in new window

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

题目

使用两个栈实现先入先出队列。需要实现对应的两个函数:

  • appendTail:在队列尾部插入整数。
  • deleteHead:在队列头部删除整数(如果队列中没有元素,deleteHead 返回 -1)。

Example:

输入:["CQueue","appendTail","deleteHead","deleteHead"], [[], [3], [], []]

输出:[null,null,3,-1]

Constraints:

  • 1 <= values <= 10000
  • 最多会对 appendTaildeleteHead 进行 10000 次调用

注意

本题与 LeetCode 第 232 题 相同。

解题思路

我们可将两个“书车”看作两个“栈”,则本题可被转化为“用两个栈实现一个队列”。

代码

class CQueue {
	constructor() {
		this.push_stack = [];
		this.pop_stack = [];
	}
	// @param {number} value
	// @return {void}
	appendTail(value) {
		this.push_stack.push(value);
	}
	// @return {number}
	deleteHead() {
		if (this.pop_stack.length + this.push_stack.length === 0) return -1;
		if (this.pop_stack.length > 0) {
			return this.pop_stack.pop();
		}
		while (this.push_stack.length > 0) {
			this.pop_stack.push(this.push_stack.pop());
		}
		return this.pop_stack.pop();
	}
}
/**
 * Your CQueue object will be instantiated and called as such:
 * var obj = new CQueue()
 * obj.appendTail(value)
 * var param_2 = obj.deleteHead()
 */