备案关闭网站,墨刀怎么做网站,淘宝放单网站怎么做,网页设计制作表格的步骤前言
周末玩了两天#xff0c;s赛看的难受。。。还是和生活对线吧
内容
一、用栈实现队列
232.用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作#xff08;push、pop、peek、empty#xff09;#xff1a;
实现 MyQueue 类#…前言
周末玩了两天s赛看的难受。。。还是和生活对线吧
内容
一、用栈实现队列
232.用栈实现队列
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作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的时候输出栈如果为空就把进栈数据全部导入进来注意是全部导入再从出栈弹出数据如果输出栈不为空则直接从出栈弹出数据就可以了
可以发现pop() 和 peek()两个函数功能类似代码实现上也是类似的。peek()的实现直接复用了pop()一定要懂得复用功能相近的函数要抽象出来不要大量的复制粘贴很容易出问题
时间复杂度push 和empty 为O(1)pop 和peek 为均摊 O(1)。对于每个元素至多入栈和出栈各两次故均摊复杂度为 O(1)。
空间复杂度O(n)。其中 n 是操作总数。对于有 n次 push 操作的情况队列中会有 n 个元素故空间复杂度为 O(n)。
type MyQueue struct {inStack []intoutStack []int
}func Constructor() MyQueue {return MyQueue{inStack:make([]int,0),outStack:make([]int ,0),}
}func (this *MyQueue) Push(x int) {this.inStackappend(this.inStack,x)
}func (this *MyQueue) Pop() int {inLen,outLen:len(this.inStack),len(this.outStack)if outLen0{if inLen0{return -1}for i:inLen-1;i0;i--{this.outStackappend(this.outStack,this.inStack[i])}this.inStack[]int{} //导出后清空outLenlen(this.outStack)//更新长度值}val:this.outStack[outLen-1]this.outStackthis.outStack[:outLen-1]return val
}func (this *MyQueue) Peek() int {
val:this.Pop()
if val-1{return -1
}
this.outStackappend(this.outStack,val)
return val
}func (this *MyQueue) Empty() bool {
return len(this.inStack)0len(this.outStack)0
}/*** Your MyQueue object will be instantiated and called as such:* obj : Constructor();* obj.Push(x);* param_2 : obj.Pop();* param_3 : obj.Peek();* param_4 : obj.Empty();*/
切片
type MyQueue struct{Data []int
}func Constructor() MyQueue{return MyQueue{}
}func (this *MyQueue) Push(x int){this.Dataappend(this.Data,x)
}func (this *MyQueue) Pop() int{c:this.Peek()if !this.Empty(){this.Datathis.Data[1:]}return c
}func (this *MyQueue) Peek() int{if !this.Empty(){return this.Data[0]}return 0
}func (this *MyQueue) Empty() bool{return len(this.Data)0
}
二、用队列实现栈
请你仅使用两个队列实现一个后入先出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双端队列来模拟一个队列 , 只要是标准的队列操作即可。 很多算法题目主要是对知识点的考察和教学意义远大于其工程实践的意义所以面试题也是这样
一个队列
出队再入队到队尾 想象成一个环
type MyStack struct {Queue []int
}func Constructor() MyStack {return MyStack{Queue:make([]int,0),}
}func (this *MyStack) Push(x int) {this.Queueappend(this.Queue,x)
}func (this *MyStack) Pop() int {n:len(this.Queue)-1for n!0{//除了最后一个其余的都重新添加到队列里val:this.Queue[0]this.Queuethis.Queue[1:]this.Queueappend(this.Queue,val)n--}//弹出元素val:this.Queue[0]this.Queuethis.Queue[1:]return val
}func (this *MyStack) Top() int {
val:this.Pop()
this.Queueappend(this.Queue,val)
return val
}func (this *MyStack) Empty() bool {
return len(this.Queue)0
}/*** Your MyStack object will be instantiated and called as such:* obj : Constructor();* obj.Push(x);* param_2 : obj.Pop();* param_3 : obj.Top();* param_4 : obj.Empty();*/
两个队列
que2是一个备份的作用把que1最后面的元素以外的元素都备份到que2然后弹出最后面的元素再把其他元素从que2导回que1
type MyStack struct{queue1,queue2 []int
}func Constructor() MyStack{return MyStack{}
}func (this *MyStack)Push(x int){this.queue2append(this.queue2,x)for len(this.queue1)0{this.queue2append(this.queue2,this.queue1[0])this.queue1this.queue1[1:]}this.queue1,this.queue2this.queue2,this.queue1
}func (this *MyStack)Pop()int{v:this.queue1[0]this.queue1this.queue1[1:]return v
}func (this *MyStack)Top()int{return this.queue1[0]
}
func (this *MyStack)Empty()bool{return len(this.queue1)0
}
切片
Go标准库里没有队列可以用数组切片或链表来实现
使用数组切片push就是appendpop就是调整切片长度top就是返回最后一个元素 使用标准库container/list包装 自定义list标准库的list是个双链表且将值定为interface{}类型这里可以简化为单链表并确定数据类型为int
这里用切片
type MyStack struct{slice []int
}
func Constructor() MyStack{return MyStack{}
}func (this *MyStack) Push(x int){this.sliceappend(this.slice,x)
}func (this *MyStack) Pop()int{if len(this.slice)0{return -1}r:this.slice[len(this.slice)-1]this.slicethis.slice[:len(this.slice)-1]return r
}
func (this *MyStack)Top()int{if len(this.slice)0{return -1}return this.slice[len(this.slice)-1]}
func (this *MyStack)Empty()bool{return len(this.slice)0
}
最后
熟练掌握基本操作。
