问题描述

请你仅使用两个队列实现一个**后入先出（LIFO）**的栈，并支持普通栈的全部四种操作：

• push：将元素x压入栈顶。
• pop：移除并返回栈顶元素。
• top：返回栈顶元素。
• empty：如果栈为空，返回true；否则返回false。

说明

• 只能使用标准的队列操作，即push to back，peek/pop from front，size和is empty。
• 语言内置的栈数据结构不可使用。
• 只能使用两个队列来实现上述操作。

格式

输入

• 一系列操作序列和对应的参数。

输出

• 每个操作的返回值（对于无返回值的操作，如push，返回null）。

样例

样例1

输入

6
MyStack push push top pop empty
0 1 2 0 0 0

输出

null null null 2 2 false

解释

MyStack myStack = new MyStack(); myStack.push(1); // 栈是 [1] myStack.push(2); // 栈是 [1, 2] myStack.top(); // 返回 2 myStack.pop(); // 返回 2，栈变成 [1] myStack.empty(); // 返回 false

提示

• 1 <= x <= 9
• 最多调用100次push、pop、top和empty。
• 每次调用pop和top时，栈中至少存在一个元素。

进阶

• 你是否可以只用一个队列来实现栈？