9.md

用两个栈实现队列

题目

用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。 队列中的元素为 int 类型。

思路

如何快速晾冷一杯热水, 用两个杯子来回倒啊

• 队列是 FIFO, 栈是 FILO
• push 操作就直接往 stack1 中 push
• pop 时如果 stack2 为空，那么需要将 stack1 中的数据转移到 stack2 中，然后在对 stack2 进行pop
• 如果 stack2 不为空，直接 pop 就 ok

实现

package main

import "fmt"

var stack1 []int
var stack2 []int

func main() {
	Push(1)
	Push(2)
	Push(3)
	fmt.Println(Pop())
	fmt.Println(Pop())
	Push(4)
	fmt.Println(Pop())
	Push(5)
	fmt.Println(Pop())
	fmt.Println(Pop())
}

func Push(node int) {
	stack1 = append(stack1, node)
}

func Pop() int {
	// 如果 stack2 空则去 stack1 里倒
	if len(stack2) == 0 {
		for i := len(stack1) - 1; i >= 0; i-- {
			stack2 = append(stack2, stack1[i])
		}
		stack1 = []int{}
	}

	// 这是 stack2 还没有说明 stack1 也是空的
	if len(stack2) == 0 {
		return -1
	}

	// pop 出 stack2 第一个元素
	index := len(stack2) - 1
	res := stack2[index]
	stack2 = stack2[:index]
	return res
}