福建省建设注册中心网站,wordpress主题乱,电子商务营销策略,网站建设学习步骤摘要#xff1a; **Leetcode的AC指南 —— 栈与队列#xff1a;225.用队列实现栈 **。题目介绍#xff1a;请你仅使用两个队列实现一个后入先出#xff08;LIFO#xff09;的栈#xff0c;并支持普通栈的全部四种操作#xff08;push、top、pop 和 empty#xff09;。 … 摘要 **Leetcode的AC指南 —— 栈与队列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双端队列来模拟一个队列 , 只要是标准的队列操作即可。 文章目录 一、题目二、解析 go语言版1、两个队列实现栈2、一个队列实现栈 三、其他语言版本JavaCPython 一、题目 题目介绍请你仅使用两个队列实现一个后入先出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:
输入
[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 都保证栈不为空 进阶
你能否仅用一个队列来实现栈
二、解析 go语言版 1、两个队列实现栈
思路 根据栈先进后出和队列先进先出的特点 将后进栈的元素放入队列的头部实现后进先出进栈的实现 将后进栈的元素压进队列2然后在依次将队列1中的元素压入队列2内最后交换队列1指向队列2队列2置空 出栈直接弹出队列1的头元素。 时间复杂度: pop为O(n)其他为O(1)空间复杂度: O(n) package maintype MyStack struct {que1 []intque2 []int
}
// 栈的初始化
func Constructor() MyStack {return MyStack{que1: make([]int, 0),que2: make([]int, 0),}
}// 将队列1中的元素压入队列2并交换队列1和队列2
func (this *MyStack) Move() {if len(this.que1) 0 { // 当队列1中的没有元素后交换队列1为队列2队列2为空this.que1, this.que2 this.que2, this.que1} else {// 将队列1中的元素依次弹出压入队列2this.que2 append(this.que2, this.que1[0])this.que1 this.que1[1:]this.Move()}
}// 进栈 向栈中添加元素
func (this *MyStack) Push(x int) {// 将元素压入栈2this.que2 append(this.que2, x)// 更新栈1和栈2的数据this.Move()
}// 出栈 将队列1中的头元素弹出
func (this *MyStack) Pop() int {val : this.que1[0]this.que1 this.que1[1:]return val
}// 获取栈顶元素的值
func (this *MyStack) Top() int {return this.que1[0]}// 判断栈是否为空
func (this *MyStack) Empty() bool {return len(this.que1) 0
}2、一个队列实现栈
思路 将进栈的元素放在队列的队头位置 实现 将新元素压入队列的队尾将队头元素依次出队然后在重新入队直到新压入的元素成为队头
package maintype MyStack struct {que []int
}func Constructor() MyStack {return MyStack{que: make([]int, 0),}
}func (this *MyStack) Push(x int) {// 将进栈元素压入队列this.que append(this.que, x)// 将该元素前面的元素依次出队在重新进队使后进栈的元素在队头for i : 0; i len(this.que)-1; i {// 将队头元素出队列val : this.que[0]this.que this.que[1:]// 将出队列的队头元素入队列this.que append(this.que, val)}
}func (this *MyStack) Pop() int {val : this.que[0]this.que this.que[1:]return val
}func (this *MyStack) Top() int {return this.que[0]
}func (this *MyStack) Empty() bool {return len(this.que) 0
}
三、其他语言版本 Java
class MyStack {QueueInteger queue1; // 和栈中保持一样元素的队列QueueInteger queue2; // 辅助队列/** Initialize your data structure here. */public MyStack() {queue1 new LinkedList();queue2 new LinkedList();}/** Push element x onto stack. */public void push(int x) {queue2.offer(x); // 先放在辅助队列中while (!queue1.isEmpty()){queue2.offer(queue1.poll());}QueueInteger queueTemp;queueTemp queue1;queue1 queue2;queue2 queueTemp; // 最后交换queue1和queue2将元素都放到queue1中}/** Removes the element on top of the stack and returns that element. */public int pop() {return queue1.poll(); // 因为queue1中的元素和栈中的保持一致所以这个和下面两个的操作只看queue1即可}/** Get the top element. */public int top() {return queue1.peek();}/** Returns whether the stack is empty. */public boolean empty() {return queue1.isEmpty();}
}
C
class MyStack {
public:queueint que1;queueint que2; // 辅助队列用来备份/** Initialize your data structure here. */MyStack() {}/** Push element x onto stack. */void push(int x) {que1.push(x);}/** Removes the element on top of the stack and returns that element. */int pop() {int size que1.size();size--;while (size--) { // 将que1 导入que2但要留下最后一个元素que2.push(que1.front());que1.pop();}int result que1.front(); // 留下的最后一个元素就是要返回的值que1.pop();que1 que2; // 再将que2赋值给que1while (!que2.empty()) { // 清空que2que2.pop();}return result;}/** Get the top element. */int top() {return que1.back();}/** Returns whether the stack is empty. */bool empty() {return que1.empty();}
};Python
from collections import dequeclass MyStack:def __init__(self):Python普通的Queue或SimpleQueue没有类似于peek的功能也无法用索引访问在实现top的时候较为困难。用list可以但是在使用pop(0)的时候时间复杂度为O(n)因此这里使用双向队列我们保证只执行popleft()和append()因为deque可以用索引访问可以实现和peek相似的功能in - 存所有数据out - 仅在pop的时候会用到self.queue_in deque()self.queue_out deque()def push(self, x: int) - None:直接append即可self.queue_in.append(x)def pop(self) - int:1. 首先确认不空2. 因为队列的特殊性FIFO所以我们只有在pop()的时候才会使用queue_out3. 先把queue_in中的所有元素除了最后一个依次出列放进queue_out4. 交换in和out此时out里只有一个元素5. 把out中的pop出来即是原队列的最后一个tip这不能像栈实现队列一样因为另一个queue也是FIFO如果执行pop()它不能像stack一样从另一个pop()所以干脆in只用来存数据pop()的时候两个进行交换if self.empty():return Nonefor i in range(len(self.queue_in) - 1):self.queue_out.append(self.queue_in.popleft())self.queue_in, self.queue_out self.queue_out, self.queue_in # 交换in和out这也是为啥in只用来存return self.queue_out.popleft()def top(self) - int:写法一1. 首先确认不空2. 我们仅有in会存放数据所以返回第一个即可这里实际上用到了栈写法二1. 首先确认不空2. 因为队列的特殊性FIFO所以我们只有在pop()的时候才会使用queue_out3. 先把queue_in中的所有元素除了最后一个依次出列放进queue_out4. 交换in和out此时out里只有一个元素5. 把out中的pop出来即是原队列的最后一个并使用temp变量暂存6. 把temp追加到queue_in的末尾# 写法一# if self.empty():# return None# return self.queue_in[-1] # 这里实际上用到了栈因为直接获取了queue_in的末尾元素# 写法二if self.empty():return Nonefor i in range(len(self.queue_in) - 1):self.queue_out.append(self.queue_in.popleft())self.queue_in, self.queue_out self.queue_out, self.queue_in temp self.queue_out.popleft() self.queue_in.append(temp)return tempdef empty(self) - bool:因为只有in存了数据只要判断in是不是有数即可return len(self.queue_in) 0
