双栈实现队列
思路一:
刚拿到这题的时候,最直接的思路就是,我每次push,我就把一号栈里的东西塞到二号栈,然后在一号栈中压入我的元素,最后再把二号栈的东西弹回一号栈,进而保证了队列的先进先出顺序。
该方法时间复杂度很大,每一次挪都是O(N)的时间复杂度,其中N表示已有队列内元素的个数
思路二:
为了优化上述思想,即每次都要把所有的元素挪动两次,我们能不能一个元素从头到尾只挪动一次就解决问题呢?
我们思考一下,我们其实只需要保证一个栈中的顺序是按照队列的顺序排列的,即可让他做到FIFO,我们可以充分的利用辅助栈来干这样一件事。
一号栈,我们只负责压数据,当个没有感情的机器。但是,如果我们将一号栈的东西顺序弹出压入二号栈,那么二号栈的元素顺序就符合队列的要求呢?
借助这个思想,我们可以设计出算法:
int pop()
{
如果辅助栈是空的{ //if(st2.empty())
把一号栈中的东西丢进辅助栈 //while(!st1.empty())int t = st1.top(), st2.push(t), st1.pop();
取出辅助栈的最高位置 //int res = st2.top();
对辅助栈弹栈 //st2.pop();
//return res;
}
如果辅助栈不是空的{
直接取出辅助栈的最高位置
对辅助栈弹栈
}
}
peek函数的思想同pop()一样,所以就不再赘述,最后的解题代码如下:
解题代码如下:
class MyQueue {
public:
stack<int> st1, st2;
int size;
/** Initialize your data structure here. */
MyQueue() {
size = 0;
while(!st1.empty()){
st1.pop();
}
while(!st2.empty()){
st2.pop();
}
}
/** Push element x to the back of queue. */
void push(int x) {
st1.push(x);
size ++;
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
if(st2.empty()){
while(!st1.empty()){
int t = st1.top();
st1.pop();
st2.push(t);
}
}
int res = st2.top();
st2.pop();
size --;
return res;
}
/** Get the front element. */
int peek() {
if(st2.empty()){
while(!st1.empty()){
int t = st1.top();
st1.pop();
st2.push(t);
}
}
int res = st2.top();
return res;
}
/** Returns whether the queue is empty. */
bool empty() {
return !(size > 0);
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* bool param_4 = obj.empty();
*/