题目描述
题目链接:232. Implement Queue using Stacks
Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue (
push
,peek
,pop
, andempty
).Implement the MyQueue class:
void push(int x)
Pushes element x to the back of the queue.int pop()
Removes the element from the front of the queue and returns it.int peek()
Returns the element at the front of the queue.boolean empty()
Returnstrue
if the queue is empty,false
otherwise.
例子
例子 1
Input:
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
Output:[null, null, null, 1, 1, false]
Explanation:
Follow Up
Can you implement the queue 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.
Note
You must use only standard operations of a stack, which means only
push to top
,peek/pop from top
,size
, andis empty
operations are valid. Depending on your language, the stack may not be supported natively. You may simulate a stack using a list or deque (double-ended queue) as long as you use only a stack’s standard operations.
解题思路
本题要求用栈实现队列的功能,这两个数据结构的区别在于数据的出入顺序不同,栈是先入后出(FILO),队列是先入先出(FIFO)。因此实现的关键的是逆转栈中存储数据的顺序,题目提示可以用两个栈,因此只要在每次 push
的时候将维护的栈的元素弹出到另一个栈中,压入新元素,将重新将新栈的元素压回原栈中,此时栈顶元素即为队列首元素。代码如下:
#include <stack>
class MyQueue {
public:
/** Initialize your data structure here. */
MyQueue() {}
/** Push element x to the back of queue. */
void push(int x) {
std::stack<int> temp = ordered_;
std::stack<int> reversed;
while (!temp.empty()) {
reversed.push(temp.top());
temp.pop();
}
reversed.push(x);
temp.swap(reversed);
ordered_ = std::stack<int>();
while (!temp.empty()) {
ordered_.push(temp.top());
temp.pop();
}
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
int val = ordered_.top();
ordered_.pop();
return val;
}
/** Get the front element. */
int peek() { return ordered_.top(); }
/** Returns whether the queue is empty. */
bool empty() { return ordered_.empty(); }
private:
std::stack<int> ordered_;
};
- 时间复杂度:
push: O(n)
pop: O(1)
peek: O(1)
empty: O(1)
- 空间复杂度:
O(n)
GitHub 代码同步地址: 232.ImplementQueueUsingStacks.cpp
其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions