湛江市建设局官方网站,仿新浪首页网站模板,潮品服饰网站建设规划书,自己做网站的选修课题目链接#xff1a;https://leetcode.cn/problems/implement-stack-using-queues/
1. 题目介绍#xff08;225. 用队列实现栈#xff09; 请你仅使用两个队列实现一个后入先出#xff08;LIFO#xff09;的栈#xff0c;并支持普通栈的全部四种操作#xff08;push、t…题目链接https://leetcode.cn/problems/implement-stack-using-queues/
1. 题目介绍225. 用队列实现栈 请你仅使用两个队列实现一个后入先出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双端队列来模拟一个队列 , 只要是标准的队列操作即可。 【测试用例】 示例 输入 [“MyStack”, “push”, “push”, “top”, “pop”, “empty”] [[], [1], [2], [], [], []] 输出 [null, null, null, 2, 2, false] 解释 MyStack myStack new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回 False 【条件约束】 提示 1 x 9最多调用100 次 push、pop、top 和 empty每次调用 pop 和 top 都保证栈不为空 【跟踪】 进阶你能否仅用一个队列来实现栈。 2. 题解
2.1 两个队列实现栈 – O(n)
时间复杂度O(n)空间复杂度O(n)
class MyStack {// 1. 定义两个队列对象private QueueInteger queue1;private QueueInteger queue2;// 2. 定义一个变量用于记录当前的queue元素长度private int curSize 0;// 3. 构造方法创建队列对象public MyStack() {queue1 new LinkedList();queue2 new LinkedList();}// 4. 入栈方法如果哪个队列有值先添加到哪个默认添加queue1public void push(int x) {if (!queue1.isEmpty()) queue1.offer(x);else if (!queue2.isEmpty()) queue2.offer(x);else queue1.offer(x);}// 5. 出栈方法public int pop() {// 判空if (empty()) return -1;// 至少有一个非空// 当queue1非空时将queue1中size-1的元素出队存入queue2// 循环结束queue1中只剩下一个元素即栈顶元素最后添加的元素if (!queue1.isEmpty()){curSize queue1.size();for (int i 0; i curSize-1; i){queue2.offer(queue1.poll());}return queue1.poll();// queue1为空说明queue2非空步骤基本同上}else {curSize queue2.size();for (int i 0; i curSize-1; i){queue1.offer(queue2.poll());}return queue2.poll();}}// 6. 返回栈顶方法public int top() {// 定义一个临时值变量用于记录queue出队值int ret -1;// 判空if (empty()) return -1;// 至少有一个非空// 当queue1非空时将queue1中所有的元素出队存入queue2// 同时通过临时值变量ret记录出队值循环结束返回ret即为栈顶元素if (!queue1.isEmpty()){curSize queue1.size();for (int i 0; i curSize; i){//System.out.println(queue1.size());ret queue1.poll(); queue2.offer(ret);}System.out.println(ret);return ret;// queue1为空说明queue2非空步骤基本同上}else {curSize queue2.size();for (int i 0; i curSize; i){ret queue2.poll(); queue1.offer(ret);}return ret;}}// 判空方法queue1与queue2全为空则为空public boolean empty() {return queue1.isEmpty() queue2.isEmpty();}
}/*** Your MyStack object will be instantiated and called as such:* MyStack obj new MyStack();* obj.push(x);* int param_2 obj.pop();* int param_3 obj.top();* boolean param_4 obj.empty();*/改进官方题解 这里的改进点在于push方法的巧妙设置数据首先会存入queue2并检查queue1是否为空如果不为空则将queue1中的元素全部出队并存入queue2然后借助临时变量交换queue1和queue2保证每次push方法后queue2始终为空queue1为真正的栈结构做到后进先出。
class MyStack {QueueInteger queue1;QueueInteger queue2;/** Initialize your data structure here. */public MyStack() {queue1 new LinkedListInteger();queue2 new LinkedListInteger();}/** Push element x onto stack. */public void push(int x) {queue2.offer(x);while (!queue1.isEmpty()) {queue2.offer(queue1.poll());}QueueInteger temp queue1;queue1 queue2;queue2 temp;}/** Removes the element on top of the stack and returns that element. */public int pop() {return queue1.poll();}/** Get the top element. */public int top() {return queue1.peek();}/** Returns whether the stack is empty. */public boolean empty() {return queue1.isEmpty();}
}
2.2 一个队列实现栈 – O(n)
时间复杂度O(n)空间复杂度O(n) 核心方法当有新元素加入时将原来的元素依次出队并重新入队让队列中的元素始终保持倒序的状态。
class MyStack {QueueInteger queue;/** Initialize your data structure here. */public MyStack() {queue new LinkedListInteger();}/** Push element x onto stack. */public void push(int x) {int n queue.size();queue.offer(x);for (int i 0; i n; i) {queue.offer(queue.poll());}}/** Removes the element on top of the stack and returns that element. */public int pop() {return queue.poll();}/** Get the top element. */public int top() {return queue.peek();}/** Returns whether the stack is empty. */public boolean empty() {return queue.isEmpty();}
}3. 参考资料
[1] 用队列实现栈官方题解-- 部分代码来源 [2] 【LeetCode】No.232. 用栈实现队列 – Java Version相似题目 [3] 【LeetCode】剑指 Offer 09. 用两个栈实现队列 p68 – Java Version相似题目
