class MyQueue {
private:
stack<int> instack;
stack<int> outstack;
public:
/** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
while(!outstack.empty()){//若出栈为空,则全部赋值
instack.push(outstack.top());
outstack.pop();
}
instack.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
while(!instack.empty()){
outstack.push(instack.top());
instack.pop();
}
int ele = outstack.top();
outstack.pop();
return ele;
}
/** Get the front element. */
int peek() {
while(!instack.empty()){
outstack.push(instack.top());
instack.pop();
}
int ele = outstack.top();
return ele;
}
/** Returns whether the queue is empty. */
bool empty() {
return instack.empty()&&outstack.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
class MyQueue {
private:
stack<int> instack;
stack<int> outstack;
public:
/** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
instack.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
if(outstack.empty())
{
while(!instack.empty()){
outstack.push(instack.top());
instack.pop();
}
}
int ele = outstack.top();
outstack.pop();
return ele;
}
/** Get the front element. */
int peek() {
if(outstack.empty())
{
while(!instack.empty()){
outstack.push(instack.top());
instack.pop();
}
}
int ele = outstack.top();
return ele;
}
/** Returns whether the queue is empty. */
bool empty() {
return instack.empty()&&outstack.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
题目,难度为简单
大意是使用两个栈来实现队列的操作,只能用基础栈操作。要求摊还复杂度O(1),即N个动作复杂度O(n)
题解一:脑抽解法
摊还O(N)
虽然在执行中击败了100%,但这其实并不满足题目要求,因为每一次切换输入输出的时候都会清空一次栈。
当时的想法就是认为一个栈必须是空的,这样倒腾才能够维持内部数据的顺序。但其实并不一定要这样
解法二:正确解法
与解法一的区别有二,第一是删除了入队操作时要把输出栈导入到输入栈的操作;第二是在出队时,输入栈往输出栈运送元素处增加了一个判定。 之前有点死脑经,可能是学AVL学上头了,一直想着说要维持数据结构。其实根本不用维持,因为输出栈在完全输出之前,是可以不用输入的,这就形成了一个局部有序的情况。