## [Leetcode]225. Implement Stack using Queues(C++)

### 题目描述

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.

### 解题思路

``````#include <queue>

class MyStack {
public:
/** Initialize your data structure here. */
MyStack() {}

/** Push element x onto stack. */
void push(int x) {
std::queue<int> temp;
temp.push(x);
while (!ordered_.empty()) {
temp.push(ordered_.front());
ordered_.pop();
}
ordered_.swap(temp);
}

/** Removes the element on top of the stack and returns that element. */
int pop() {
int val = ordered_.front();
ordered_.pop();
return val;
}

/** Get the top element. */
int top() { return ordered_.front(); }

/** Returns whether the stack is empty. */
bool empty() { return ordered_.empty(); }

private:
std::queue<int> ordered_;
};
``````
• 时间复杂度:
• `push: O(n)`
• `pop: O(1)`
• `peek: O(1)`
• `empty: O(1)`
• 空间复杂度: `O(n)`

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

Built with Hugo
Theme Stack designed by Jimmy