只用一个栈来实现队列,pop和top的时间复杂度为$O(N)$
class MyStack {
public:
queue<int> q;
/** Initialize your data structure here. */
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
q.push(x);
}
/** Removes the element on top of the stack and returns that element. */
int pop() { //逐个弹出元素并插入到队列尾部,直到队列中只剩一个元素为止
int size = q.size();
while (size -- > 1)
{
q.push(q.front());
q.pop();
}
int res = q.front();
q.pop();
return res;
}
/** Get the top element. */
int top() {
int size = q.size();
while (size -- > 1)
{
q.push(q.front());
q.pop();
}
int res = q.front();
q.push(q.front()); //与pop操作的不同之处,取得最后一个元素值后还会放回去
q.pop();
return res;
}
/** Returns whether the stack is empty. */
bool empty() {
return q.empty();
}
};