题目描述
题目链接:225. Implement Stack using Queues
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
, andempty
).Implement the
MyStack
class:
void push(int x)
Pushes elementx
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
Follow Up
Can you implement the stack such that each operation is amortized
O(1)
time complexity? In other words, performingn
operations will take overallO(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
, andis 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 topush
,pop
,top
, andempty
.- All the calls to
pop
andtop
are valid.
解题思路
思路比较简单,由于栈是先入后出,因此每 push
一个元素我们要确保它在我们使用的 queue
的前面,因此只需要用一个临时 queue
将 x
压入,然后依次压入我们维护的 queue
的元素,最后将临时 queue
与我们维护的 queue
交换即可;其他操作可以直接使用 queue
的相应操作,代码如下:
#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
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions