[toc]
# 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（双端队列）来模拟一个栈，只要是标准的栈操作即可。
示例 1：
输入： ["MyQueue", "push", "push", "peek", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 1, 1, false] 解释： MyQueue myQueue = new MyQueue(); myQueue.push(1); // queue is: [1] myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue) myQueue.peek(); // return 1 myQueue.pop(); // return 1, queue is [2] myQueue.empty(); // return false提示：
1 <= x <= 9- 最多调用
100次push、pop、peek和empty- 假设所有操作都是有效的 （例如，一个空的队列不会调用
pop或者peek操作）进阶：
- 你能否实现每个操作均摊时间复杂度为
O(1)的队列？换句话说，执行n个操作的总时间复杂度为O(n)，即使其中一个操作可能花费较长时间。
用栈实现队列，需要一个输入栈，一个输出栈。
需要先用 Go 实现一个栈（这里使用 slice），然后再用该栈模拟队列。
原本需要在 stack.Len() 中加读锁，但在 LeetCode 中再多加一个读锁就会时间超限。。
下面动画模拟以下队列的执行过程：
执行语句：
queue.push(1);
queue.push(2);
queue.pop(); 注意此时的输出栈的操作
queue.push(3);
queue.push(4);
queue.pop();
queue.pop();注意此时的输出栈的操作
queue.pop();
queue.empty();
push 数据，只要把数据放进输入栈即可。
pop 数据：如果输出栈为空，就把输入栈的数据全部导入输出栈，再从输出栈 Pop 数据。
fillStackOut： 将数据全部导入输出栈写成一个方法
peek 和 empty： 如果输出栈为空，就把输入栈的数据全部导入输出栈，再查看 stackOut 的栈顶元素、判断 stackOut 是否为空。
见详细代码：
// 用 slice 实现栈
type myStack struct {
Ints []int
Lock sync.RWMutex
}
func NewStack() *myStack {
return &myStack{
Ints: []int{}, // 字面量 []int{} 已经分配好内存空间
}
}
// Push 入栈
func (s *myStack) Push(t int) {
s.Lock.Lock()
defer s.Lock.Unlock()
s.Ints = append(s.Ints, t)
}
// Pop 出栈
func (s *myStack) Pop() int {
s.Lock.Lock()
defer s.Lock.Unlock()
if s.Empty() {
return 0
}
val := s.Ints[s.Len()-1]
s.Ints = s.Ints[:s.Len()-1]
return val
}
// Len 栈内存储的元素数量
func (s *myStack) Len() int {
return len(s.Ints)
}
// Peek 查看栈顶元素
func (s *myStack) Peek() int {
if s.Empty() {
return 0
}
return s.Ints[s.Len()-1]
}
// Empty 检查栈是否为空
func (s *myStack) Empty() bool {
return s.Len() == 0
}
// ==========分割线==========
type MyQueue struct {
stackIn *myStack
stackOut *myStack
}
func Constructor() MyQueue {
return MyQueue {
stackIn: NewStack(),
stackOut: NewStack(),
}
}
func (q *MyQueue) Push(x int) {
q.stackIn.Push(x)
}
func (q *MyQueue) Pop() int {
// 如果 q.stackOut 中没有元素，把 stackIn 元素全部 Push 到 stackOut 中
q.fillStackOut()
// 如果 q.stackOut 中有元素则直接 Pop 元素
return q.stackOut.Pop()
}
func (q *MyQueue) Peek() int {
q.fillStackOut()
return q.stackOut.Peek()
}
func (q *MyQueue) Empty() bool {
q.fillStackOut()
return q.stackOut.Empty()
}
func (q *MyQueue) fillStackOut() {
if q.stackOut.Empty() {
for !q.stackIn.Empty() {
val := q.stackIn.Pop()
q.stackOut.Push(val)
}
}
}
/**
* 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();
*/