力扣刷题第二十一天--栈与队列

前言

周末玩了两天，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.inStack=append(this.inStack,x)
}func (this *MyQueue) Pop() int {inLen,outLen:=len(this.inStack),len(this.outStack)if outLen==0{if inLen==0{return -1}for i:=inLen-1;i>=0;i--{this.outStack=append(this.outStack,this.inStack[i])}this.inStack=[]int{} //导出后清空outLen=len(this.outStack)//更新长度值}val:=this.outStack[outLen-1]this.outStack=this.outStack[:outLen-1]return val
}func (this *MyQueue) Peek() int {
val:=this.Pop()
if val==-1{return -1
}
this.outStack=append(this.outStack,val)
return val
}func (this *MyQueue) Empty() bool {
return len(this.inStack)==0&&len(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.Data=append(this.Data,x)
}func (this *MyQueue) Pop() int{c:=this.Peek()if !this.Empty(){this.Data=this.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.Queue=append(this.Queue,x)
}func (this *MyStack) Pop() int {n:=len(this.Queue)-1for n!=0{//除了最后一个，其余的都重新添加到队列里val:=this.Queue[0]this.Queue=this.Queue[1:]this.Queue=append(this.Queue,val)n--}//弹出元素val:=this.Queue[0]this.Queue=this.Queue[1:]return val
}func (this *MyStack) Top() int {
val:=this.Pop()
this.Queue=append(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.queue2=append(this.queue2,x)for len(this.queue1)>0{this.queue2=append(this.queue2,this.queue1[0])this.queue1=this.queue1[1:]}this.queue1,this.queue2=this.queue2,this.queue1
}func (this *MyStack)Pop()int{v:=this.queue1[0]this.queue1=this.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就是append，pop就是调整切片长度，top就是返回最后一个元素
使用标准库container/list包装
自定义list，标准库的list是个双链表且将值定为interface{}类型，这里可以简化为单链表并确定数据类型为int

这里用切片

type MyStack struct{slice []int
}
func Constructor() MyStack{return MyStack{}
}func (this *MyStack) Push(x int){this.slice=append(this.slice,x)
}func (this *MyStack) Pop()int{if len(this.slice)==0{return -1}r:=this.slice[len(this.slice)-1]this.slice=this.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
}

最后

熟练掌握基本操作。