刷leetcode-用队列实现栈 | 刷题打卡
一、题目描述:
请你仅使用两个队列实现一个后入先出(LIFO)的栈,并支持普通队列的全部四种操作(push、top、pop 和 empty)。
实现 MyStack 类:
- void push(int x) 将元素 x 压入栈顶。
- int pop() 移除并返回栈顶元素。
- int top() 返回栈顶元素。
- boolean empty() 如果栈是空的,返回 true ;否则,返回 false 。
注意:
- 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
- 你所使用的语言也许不支持队列。 你可以使用 list (列表)或者 deque(双端队列)来模拟一个队列 , 只要是标准的队列操作即可。
提示:
- 1 <= x <= 9
- 最多调用100 次 push、pop、top 和 empty
- 每次调用 pop 和 top 都保证栈不为空
二、思路分析:
- 用数组模拟栈和队列
- 栈的话,先进后出,就只使用数组的push和pop
- 队列的话,先进先出,就只使用数组的push和shift
- 两个队列
- 一个队列,主队列,元素是倒序的,这样就能先进后出
- 一个队列,辅助队列,负责将后来的元素往前排,排好之后,两个队列身份互换
- push的时候,先往辅助队列里扔,再将主队列的元素挨个扔过来,两队列身份互换,辅助队列变成空队列
- pop的时候,直接将主队列的元素扔出去一个就好
- empty和top直接判断主队列即可
借用官方图分析思路:
网络异常,图片无法展示
|
三、AC 代码:
var MyStack = function() { this.mainQueue = [] this.subQueue = [] }; /** * Push element x onto stack. * @param {number} x * @return {void} */ MyStack.prototype.push = function(x) { this.subQueue.push(x) for(let i=0;i<this.mainQueue.length;i++){ this.subQueue.push(this.mainQueue.shift()) i-- } const temp = this.subQueue this.subQueue = this.mainQueue this.mainQueue = temp }; /** * Removes the element on top of the stack and returns that element. * @return {number} */ MyStack.prototype.pop = function() { return this.mainQueue.shift() }; /** * Get the top element. * @return {number} */ MyStack.prototype.top = function() { return this.mainQueue[0] }; /** * Returns whether the stack is empty. * @return {boolean} */ MyStack.prototype.empty = function() { return !this.mainQueue.length };
四、总结:
- 还是熟练掌握队列和栈的特点
- 让栈倒序排列:挨个去另一个栈
- 让队列倒序排列:插入时去辅助队列里,然后将主队列的挨个去辅助队列,最后交换两个队列身份,辅助队列的状态还是为空