0%

### 题目描述

Implement a last in first out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal queue (`push`, `top`, `pop`, and `empty`).

Implement the `MyStack` class:

• `void push(int x)` Pushes element `x` to the top of the stack.
• `int pop()` Removes the element on the top of the stack and returns it.
• `int top()` Returns the element on the top of the stack.
• `boolean empty()` Returns true if the stack is empty, false otherwise.

### 例子

#### 例子 1

Input:
`["MyStack", "push", "push", "top", "pop", "empty"]`
`[[], [1], [2], [], [], []]`
Output: `[null, null, null, 2, 2, false]`
Explanation:
`MyStack myStack = new MyStack();`
`myStack.push(1);`
`myStack.push(2);`
`myStack.top(); // return 2`
`myStack.pop(); // return 2`
`myStack.empty(); // return False`

Can you implement the stack such that each operation is amortized `O(1)` time complexity? In other words, performing `n` operations will take overall `O(n)` time even if one of those operations may take longer. You can use more than two queues.

### Note

• You must use only standard operations of a queue, which means only `push to back`, `peek/pop from front`, `size`, and `is empty` operations are valid.
• Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue), as long as you use only a queue’s standard operations

### Constraints

• `1 <= x <= 9`
• At most `100` calls will be made to `push`, `pop`, `top`, and `empty`.
• All the calls to `pop` and `top` are valid.

### 解题思路

• 时间复杂度:
• `push: O(n)`
• `pop: O(1)`
• `peek: O(1)`
• `empty: O(1)`
• 空间复杂度: `O(n)`

GitHub 代码同步地址： 225.ImplementStackUsingQueues.cpp

GitHub: Leetcode-C++-Solution