需要一个输出栈和输入栈
先将数据放到输入栈，再把数据从输入栈放到输出栈，此时输出栈输出数据的顺序就和队列一样了，先入先出
type MyQueue struct {
instack []int
outstack []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) intoout(){
for len(this.instack)>0{
this.outstack=append(this.outstack,this.instack[len(this.instack)-1])
this.instack=this.instack[:len(this.instack)-1]
}
}
func (this *MyQueue) Pop() int {
if len(this.outstack)==0{
this.intoout()
}
val:=this.outstack[len(this.outstack)-1]
this.outstack=this.outstack[:len(this.outstack)-1]
return val
}
func (this *MyQueue) Peek() int {
if len(this.outstack)==0{
this.intoout()
}
return this.outstack[len(this.outstack)-1]
}
func (this *MyQueue) Empty() bool {
return len(this.instack)==0&&len(this.outstack)==0
}
方法一：两个队列实现
type MyStack struct {
//创建两个队列
queue1 []int
queue2 []int
}
func Constructor() MyStack {
return MyStack{ //初始化
queue1:make([]int,0),
queue2:make([]int,0),
}
}
func (this *MyStack) Push(x int) {
//先将数据存在queue2中
this.queue2 = append(this.queue2,x)
//将queue1中所有元素移到queue2中，再将两个队列进行交换
this.Move()
}
func (this *MyStack) Move(){
if len(this.queue1) == 0{
//交换，queue1置为queue2,queue2置为空
this.queue1,this.queue2 = this.queue2,this.queue1
}else{
//queue1元素从头开始一个一个追加到queue2中
this.queue2 = append(this.queue2,this.queue1[0])
this.queue1 = this.queue1[1:] //去除第一个元素
this.Move() //重复
}
}
func (this *MyStack) Pop() int {
val := this.queue1[0]
this.queue1 = this.queue1[1:] //去除第一个元素
return val
}
func (this *MyStack) Top() int {
return this.queue1[0] //直接返回
}
func (this *MyStack) Empty() bool {
return len(this.queue1) == 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();
*/
方法二：
使用一个队列，在弹栈的时候，只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时在去弹出元素就是栈的顺序了。
type MyStack struct {
queue []int//创建一个队列
}
/** Initialize your data structure here. */
func Constructor() MyStack {
return MyStack{ //初始化
queue:make([]int,0),
}
}
/** Push element x onto stack. */
func (this *MyStack) Push(x int) {
//添加元素
this.queue=append(this.queue,x)
}
/** Removes the element on top of the stack and returns that element. */
func (this *MyStack) Pop() int {
n:=len(this.queue)-1//判断长度
for 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
}
/** Get the top element. */
func (this *MyStack) Top() int {
//利用Pop函数，弹出来的元素重新添加
val:=this.Pop()
this.queue=append(this.queue,val)
return val
}
/** Returns whether the stack is empty. */
func (this *MyStack) Empty() bool {
return len(this.queue)==0
}
func isValid(s string) bool {
queue:=[]byte{}
m:=map[byte]byte{
')' :'(',
']': '[',
'}': '{',
}
arr:=[]byte(s)
for _,v:=range arr{
if v=='('||v=='{'||v=='['{
queue=append(queue,v)
}else if v==')'||v=='}'||v==']'{
if len(queue)==0||queue[len(queue)-1]!=m[v]{
return false
}else{
queue=queue[:len(queue)-1]
}
}
}
if len(queue)!=0{
return false
}else{
return true
}
}
func removeDuplicates(s string) string {
str:=[]byte(s)
queue:=make([]byte,0)
for _,v:=range str{
if len(queue)>0&&queue[len(queue)-1]==v{
queue=queue[:len(queue)-1]
}else{
queue=append(queue,v)
}
}
return string(queue)
}
func evalRPN(tokens []string) int {
queue:=make([]int,0)
for _,v:=range tokens{
if v=="+"||v=="-"||v=="/"||v=="*"{
num1,num2 := queue[len(queue)-2], queue[len(queue)-1]
queue=queue[:len(queue)-2]
switch v{
case "+":
queue=append(queue,num1+num2)
case "-":
queue=append(queue,num1-num2)
case "/":
queue=append(queue,num1/num2)
case "*":
queue=append(queue,num1*num2)
}
}else{
n,_:=strconv.Atoi(v)
queue=append(queue,n)
}
}
return queue[0]
}
单调队列实现
单调队列思想：
队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。
单调队列不是单纯的给队列中元素排序，那和优先级队列没有什么区别了。
设计时要注意的：
- pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
- push(value)：如果push的元素value大于入口元素的数值，那么就将队列出口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止
type MyQueue struct{ //创建结构体
queue []int
}
func NewMyQueue() *MyQueue { //初始化函数
return &MyQueue{
queue: make([]int, 0),
}
}
func (m *MyQueue) Push(k int){
//将单调队列中比k小的全都弹出
if len(m.queue)>0 && k>m.queue[0]{ //队列中所有的元素都比k小
m.queue=[]int{}
}
for len(m.queue)>0 && m.queue[len(m.queue)-1]<k{ // 队列中所可能存在元素比k小
m.queue=m.queue[:len(m.queue)-1]
}
m.queue=append(m.queue,k)
}
func (m *MyQueue) Pop(t int){
if m.queue[0]==t{ //判断滑动窗口最左边元素t是不是单调队列最大值，若是弹出，否则什么都不用做
m.queue=m.queue[1:]
}
}
func maxSlidingWindow(nums []int, k int) []int {
queue:=NewMyQueue()
arr:=make([]int,0)
left,right:=0,k-1
for i:=left;i<=right;i++{
queue.Push(nums[i])
}
arr=append(arr,queue.queue[0])
right++
for right<=len(nums)-1{
queue.Pop(nums[left])
queue.Push(nums[right])
arr=append(arr,queue.queue[0])
left++
right++
}
return arr
}
用了 heap 库
func topKFrequent(nums []int, k int) []int {
map_num:=map[int]int{}
//记录每个元素出现的次数
for _,item:=range nums{
map_num[item]++
}
h:=&IHeap{}
heap.Init(h)
//所有元素入堆，堆的长度为k
for key,value:=range map_num{
heap.Push(h,[2]int{key,value})
if h.Len()>k{
heap.Pop(h)
}
}
res:=make([]int,k)
//按顺序返回堆中的元素
for i:=0;i<k;i++{
res[k-i-1]=heap.Pop(h).([2]int)[0]
}
return res
}
//构建小顶堆
type IHeap [][2]int
func (h IHeap) Len()int {
return len(h)
}
func (h IHeap) Less (i,j int) bool {
return h[i][1]<h[j][1]
}
func (h IHeap) Swap(i,j int) {
h[i],h[j]=h[j],h[i]
}
func (h *IHeap) Push(x interface{}){
*h=append(*h,x.([2]int))
}
func (h *IHeap) Pop() interface{}{
old:=*h
n:=len(old)
x:=old[n-1]
*h=old[0:n-1]
return x
}
/构建小顶堆
type IHeap [][2]int
func (h IHeap) Len()int {
return len(h)
}
func (h IHeap) Less (i,j int) bool {
return h[i][1]<h[j][1]
}
func (h IHeap) Swap(i,j int) {
h[i],h[j]=h[j],h[i]
}
func (h *IHeap) Push(x interface{}){
*h=append(*h,x.([2]int))
}
func (h *IHeap) Pop() interface{}{
old:=*h
n:=len(old)
x:=old[n-1]
*h=old[0:n-1]
return x
}