# 225. 用队列实现栈
简单
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（
push、top、pop和empty）。实现
MyStack类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。注意：
- 你只能使用队列的标准操作 —— 也就是
push to back、peek/pop from front、size和is empty这些操作。- 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
示例：
输入： ["MyStack", "push", "push", "top", "pop", "empty"] [[], [1], [2], [], [], []] 输出： [null, null, null, 2, 2, false] 解释： MyStack myStack = new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回 False提示：
1 <= x <= 9- 最多调用
100次push、pop、top和empty- 每次调用
pop和top都保证栈不为空进阶：你能否仅用一个队列来实现栈。
其实感觉用1个队列实现栈，比用2个队列更简单一点。
# 用2个队列实现栈
push： 把元素加到 queue1 中
pop/top：用 MoveWithoutLast() 将 queue1 中除最后一个外所有元素移入 queue2 ，就可以单独对栈顶元素操作了。pop: 返回栈顶元素并删除它；top: 返回栈顶元素，并将其加入 queue2 。最后 queue1 为空，queue2 包含所有元素，交换 queue1 和 queue2
empty： 判断 queue1 和 queue2 是否同时为空
动画演示：
模拟的队列执行语句如下：
queue.push(1);
queue.push(2);
queue.pop(); // 注意弹出的操作
queue.push(3);
queue.push(4);
queue.pop(); // 注意弹出的操作
queue.pop();
queue.pop();
queue.empty(); 
完整代码：
type MyStack struct {
// 2个队列
queue1 []int
queue2 []int
}
func Constructor() MyStack {
return MyStack {
queue1: []int{},
queue2: []int{},
}
}
func (s *MyStack) Push(x int) {
s.queue1 = append(s.queue1, x)
}
func (s *MyStack) Pop() int {
s.MoveWithoutLast()
val := s.queue1[0]
s.queue1 = s.queue1[1:] // 去除第一个元素，即变成空切片
s.queue1, s.queue2 = s.queue2, s.queue1 // 交换，把 queue1 置为 queue2， queue2 置为空
return val
}
func (s *MyStack) Top() int {
s.MoveWithoutLast()
val := s.queue1[0]
s.queue2 = append(s.queue2, val)
s.queue1 = s.queue1[1:] // 去除第一个元素，即变成空切片
s.queue1, s.queue2 = s.queue2, s.queue1 // 交换，把 queue1 置为 queue2， queue2 置为空
return val
}
func (s *MyStack) Empty() bool {
return len(s.queue1) == 0 && len(s.queue2) == 0
}
func (s *MyStack) MoveWithoutLast() {
// 除 queue1 最后一个元素，其余元素转移至 queue2
for i := 0; i < len(s.queue1) - 1; i++ {
s.queue2 = append(s.queue2, s.queue1[i])
}
// queue1 中只保留最后一个元素
s.queue1 = s.queue1[len(s.queue1)-1:]
}
/**
* 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();
*/
# 用1个队列实现栈
push： 直接加到队列末尾
pop/top： 把除栈顶元素（最后一个元素）以外的所有元素，一个一个移到队列尾，就可以对栈顶元素操作了。pop： 读取并删除它；top： 读取并将其添加到 queue 末尾。
empty： 判断 queue 是否为空
可以用以下方法快速找到栈顶元素，并将其他元素放到 queue 末尾：
for range len(s.queue) - 1 {
first := s.queue[0]
// 把第一个元素移到queue末尾
s.queue = append(s.queue, first)
s.queue = s.queue[1:] // 移除第一个元素
}完整代码：
type MyStack struct {
queue []int
}
func Constructor() MyStack {
return MyStack {
queue: []int{},
}
}
func (s *MyStack) Push(x int) {
s.queue = append(s.queue, x)
}
func (s *MyStack) Pop() int {
s.MoveWithoutLast()
val := s.queue[0]
s.queue = s.queue[1:]
return val
}
func (s *MyStack) Top() int {
s.MoveWithoutLast()
val := s.queue[0]
s.queue = append(s.queue, val)
s.queue = s.queue[1:]
return val
}
func (s *MyStack) Empty() bool {
return len(s.queue) == 0
}
func (s *MyStack) MoveWithoutLast() {
for range len(s.queue) - 1 {
first := s.queue[0]
// 把第一个元素移到queue末尾
s.queue = append(s.queue, first)
s.queue = s.queue[1:]
}
}
/**
* 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();
*/