两个栈实现一个队列 两个队列实现一个栈

转自：http://www.cnblogs.com/tracyhan/p/5490775.html

1、两个栈实现一个队列

三种思路：
思路一
将stack1作为存储空间，stack2作为临时缓冲区。整个流程分为两种状态，即入队时，直接将stack1压入栈中；出队时，将stack1中的所有元素依次出栈压入stack2中，再将stack2的栈顶元素弹出，最后将其倒回stack1。见下图所示，

思路二
注意：
思路中有一个细节需要优化下，在出队时，将stack1的元素逐个“倒入”stack2时，原在stack1栈底的元素，不用“倒入”stack2（即只“倒”stack1.Count()-1个），可直接弹出作为出队元素返回。这样可以减少一次压栈的操作。（图中s1代表stack1，s2代表stack2）

那么，经过修改后，上面的思路可以修改为：
入队时，先判断s1是否为空，若不为空，说明所有的元素都在s1中，此时入队元素直接压入s1；若为空，将s2的元素逐个“倒回”s1，再压入入队元素；

出队时，先判断s2是否为空，如不为空，直接弹出s2的顶元素并出队；如为空，将s1的元素逐个“倒入”s2，把最后一个元素弹出并出队。

分析：相对于思路一，思路二的s2好像比较“懒”，每次出队后，并不将元素“倒回”s1，如果赶上下次还是出队操作，效率会高一些，但下次如果是入队操作，效率不如第一种方法。

思路三
入队时，直接压入s1中
出队时，判断s2是否为空，如不为空，则直接弹出顶元素；如为空，则将s1的元素逐个“倒入”s2，把最后一个元素弹出并出队。

这个思路，避免了反复“倒”栈，仅在需要时才“倒”一次，执行效率较前两种思路来说效率高很多。

思路三的代码实现

//入队操作
void EnQueue(stack<int> &s1,stack<int> &s2,int m)
{
    s1.push(m);
}

//出队操作
void DeQueue(stack<int> &s1,stack<int> &s2,int &m)
{
    if (s2.empty())
    {
        for (int i=0;i<s1.size();i++)
        {
            s2.push(s1.top());
            s1.pop();
        }    
    }
    m = s2.top();
    s2.pop();
}

2、两个队列实现一个栈

将queue1用作进栈出栈，queue2作为一个中转站

入栈时，直接压入queue1中;
出栈时，先将queue1中的元素除最后一个元素外依次出队列，并压入队列queue2中，将留在queue1中的最后一个元素出队列即为出栈元素，最后还要把queue2中的元素再次压入queue1中。

//进栈操作
void stackpush(queue<int> &q1,queue<int> &q2,int m)
{
    q1.push(m);
}

//出栈操作
void stackpop(queue<int> &q1,queue<int> &q2,int &m)
{
    for (int i=0;i<q1.size()-1;i++)
    {
        q2.push(q1.front());
        q1.pop();
    }
    m = q1.front();
    q1.pop();
    
    for (int j = 0;j<q2.size();j++)
    {
        q1.push(q2.front());
        q2.pop();
    }
}