【代码随想录】算法训练计划10

算法训练计划10"/>

【代码随想录】算法训练计划10

1、232. 用栈实现队列

题目：
实现 MyQueue 类：
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空，返回 true ；否则，返回 false

思路：

• 双栈模拟法，注意拿的是栈顶元素，拿完更新长度

// 代码一刷，很多细节需要注意
type MyQueue struct {stackIn []intstackOut []int
}// 作用就是初始化一个队列，的对象
func Constructor() MyQueue {return MyQueue{stackIn: make([]int, 0),stackOut: make([]int, 0),}
}func (this *MyQueue) Push(x int)  {this.stackIn = append(this.stackIn, x)
}func (this *MyQueue) Pop() int {// 最核心的最难的——把入栈元素都给放到out栈inLen, outLen := len(this.stackIn), len(this.stackOut)if outLen == 0 {if inLen == 0 {return -1}for i:=inLen-1; i>=0; i-- { //拿栈顶元素this.stackOut = append(this.stackOut, this.stackIn[i])}this.stackIn = []int{} // 清空，因为都赋值过了，别忘了outLen = len(this.stackOut) // 更新长度，否则又进入循环}val := this.stackOut[outLen-1] // 拿到栈顶元素值this.stackOut =  this.stackOut[:outLen-1] // 出栈return val
}func (this *MyQueue) Peek() int {val := this.Pop() // 出栈了if val == -1 {return -1}this.stackOut = append(this.stackOut, val) //但题意是返回开头元素，并没说让你出去，所以就再加回来return val
}func (this *MyQueue) Empty() bool {return len(this.stackIn) == 0 && len(this.stackOut) == 0
}

2、225. 用队列实现栈

题目：

思路：

• 一个队列,n-1个元素再次放入队列队尾即可

// 代码一刷
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
}