栈与队列
232.用栈实现队列
思路
一道模拟题，不涉及到算法部分。如果想用栈来实现队列，至少需要2个栈，一个输入栈一个输出栈。
- 在进行
push操作时，将数据放入到输入栈中。 - 在进行
pop操作时，将数据从输出栈中取出，如果输出栈为空时，则将输入栈的数据全部放入输出栈。 - 如果输入栈和输出栈都为空，则队列为空。
type MyQueue struct {
stackIn, stackOut []int
}
func Constructor() MyQueue {
return MyQueue{}
}
func (q *MyQueue) Push(x int) {
q.stackIn = append(q.stackIn, x)
}
func (q *MyQueue) in2out() {
n := len(q.stackIn)
for i := n - 1; i >= 0; i-- {
q.stackOut = append(q.stackOut, q.stackIn[i])
q.stackIn = q.stackIn[:i]
}
}
func (q *MyQueue) Pop() int {
if len(q.stackOut) == 0 {
q.in2out()
}
x := q.stackOut[len(q.stackOut)-1]
q.stackOut = q.stackOut[:len(q.stackOut)-1]
return x
}
func (q *MyQueue) Peek() int {
x := q.Pop()
q.stackOut = append(q.stackOut, x)
return x
}
func (q *MyQueue) Empty() bool {
return len(q.stackIn) == 0 && len(q.stackOut) == 0
}
总结
在实际代码书写过程中，因为pop和peek实现的功能类似，因为在peek方法中，可以调用pop的方法，然后将pop出来的数据再插入回输出栈。
225.用队列实现栈
思路
使用双队列
- 队列
queue1进行入队操作 - 当执行
pop操作时，需要将queue1中的数据除了第0个元素外，都添加到queue2中进行备份，然后弹出queue1的第0个元素。接下来执行将queue2的队列赋值给queue1，即：queue1=queue2，清空queue2队列。
type MyStack struct {
queue1 []int
queue2 []int
}
func Constructor() MyStack {
return MyStack{
queue1: make([]int, 0),
queue2: make([]int, 0),
}
}
func (s *MyStack) Push(x int) {
s.queue1 = append(s.queue1, x)
}
func (s *MyStack) Pop() int {
for n := len(s.queue1) - 1; n > 0; n-- {
s.queue2 = append(s.queue2, s.queue1[0])
s.queue1 = s.queue1[1:]
}
val := s.queue1[0]
s.queue1 = s.queue1[1:]
s.queue1, s.queue2 = s.queue2, s.queue1
return val
}
func (s *MyStack) Top() int {
val := s.Pop()
s.queue1 = append(s.queue1, val)
return val
}
func (s *MyStack) Empty() bool {
return len(s.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();
*/
优化
使用一个队列完成栈的模拟操作，当需要弹出栈顶时，将队列中的前n-1个元素全部放入到队列的尾部，那么队列出队时第1个元素就是栈顶。
type MyStack struct {
queue []int
}
func Constructor() MyStack {
return MyStack{
queue: make([]int, 0),
}
}
func (s *MyStack) Push(x int) {
s.queue = append(s.queue, x)
}
func (s *MyStack) Pop() int {
for n := len(s.queue) - 1; n > 0; n-- {
s.queue = append(s.queue, s.queue[0])
s.queue = s.queue[1:]
}
val := s.queue[0]
s.queue = s.queue[1:]
return val
}
func (s *MyStack) Top() int {
val := s.Pop()
s.queue = append(s.queue, val)
return val
}
func (s *MyStack) Empty() bool {
return len(s.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();
*/
总结
使用队列模拟栈的操作，可以利用单队列的方式完成。每次pop操作将队列头部的元素（不包括最后一个元素）放到队列的尾部重新加入队列，此时弹出的第0个元素就是栈顶的元素，然后再移除第0个元素。