剑指offer面试题7：用两个栈实现队列&用两个队列实现栈

用两个栈实现一个队列

1、要求：一个队列包含两个栈stack1和stack2，用这两个“先进后出”的栈实现一个“先进先出”的队列queue，主要实现appendTail和deleteHead函数。
2、思路：首先向stack1压入元素a、b和c，则stack1中元素有{a,b,c}，其中c位于栈顶，而stack2是空的。
这时，要从队列中删除一个元素，按照队列先入先出的规则，由于a比b、c先插入到队列中，最先被删除的元素应该是a。元素a在stack1中，但并不在栈顶，因此不能直接删除。如果把stack1中的元素逐个弹出并压入stack2，元素在stack2中的顺序正好和原来在stack1中的顺序相反。因此经过3次弹出stack1和压入stack2操作结束之后，stack1为空，而stack2中的元素为{c,b,a}，这个时候就可以弹出stack2的栈顶元素a了。
如果要继续删除队列的头部，剩下的两个元素b和c，b比c早进入队列，因此b先删除，而此时b恰好在栈顶上，因此直接弹出stack2的栈顶即可。这次弹出操作之后，stack1中任然为空，而stack2为{c}。
接下来再插入一个元素d，还是把它压入stack1，如果下一次要删除队列头部的元素，因为stack2不为空，可以直接弹出它的栈顶元素c，而串的确是比d先进入队列，应该在d之前在队列中删除，因此不会出现任何矛盾。
具体的插入和删除操作如图所示：

小结：队列中插入元素只插入到stack1的栈顶，删除元素只从stack2的栈顶删除，当stack2中不为空时，在stack2中的栈顶元素是最先进入队列的元素，可以弹出。如果stack2为空时，先把stack1中元素逐个压入stack2.由于先进入队列的元素被压入到stack1的低端，经过弹出和压入之后就处于stack2的顶端了，则可以直接弹出。

代码实现：

//尾插
void appendTail(stack<int> *stack1,int data)
{
    stack1->push(data);
}
//头删
void deleteHead(stack<int> *stack1,stack<int> *stack2,int *val)
{
    if (stack2->size()<=0)
    {
        while (s1->size()>0)
        {
            int data = stack1->top();
            stack1->pop();
            stack2->push(data);
        }
    }
    if (stack2->size()==0)
    {
        printf("queue is empty\n");
        return;
    }
    *val = stack2->top();
    stack2->pop();
}

用两个队列实现一个栈

1、要求：一个栈包含两个队列queue1和queue2，用这两个“先进先出”的队列实现一个“先进后出”的栈stack，主要实现Top、Push和Pop三个函数。
2、思路：先往一个栈内压入一个元素a。由于两个队列现在都是空的，可以把a插入两个队列中的任意一个。不妨插入queue1.接下来继续往栈内压入b、c两个元素，把它们都插入queue1。这时，queue1包含3个元素a、b和c，其中a位于队列的头部，c位于队列的尾部。
然后从栈内弹出一个元素。根据栈的先入后出原则，最后被压入栈的c应该最先被弹出。由于c位于queue1的尾部，而每次只能从队列的头部删除元素，因此可以先从queue1中依次删除元素a、b并插入到queue2中，再从queue1中删除元素c。这就相当于从栈中弹出元素c了。可以用同样的方法从栈内弹出元素b。
接下来再往栈内压入一个元素d。此时queue1已经有一个元素a，就把d插入queue1的尾部。如果再从栈内弹出一个元素，此时被弹出的应该是最后被压入的d。由于d位于queue1的尾部，只能先从头部删除queue1的元素a并压入到队列queue2中，直到queue1中遇到d再直接把它删除。
具体的插入和删除算法如图所示：

小结：往栈顶插入元素时，如果有一个队列中有元素，则插入该队列的尾部，如果没有，可以任选一个插入；从栈顶删除元素时，如果有一个队列中元素不为空，则依次先将队头元素删除并插入另一个队列中，直到该队列中留下最后一个元素，则获取该元素的值，并将它出队。
代码实现：

//压栈
void Push(queue<int> *queue1,queue<int> *queue2,int data)
{
    if(queue1->size() == 0 && queue2->size() != 0)
    {
        queue<int> *temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }
    queue1->push(data);
}
//出栈
void Pop(queue<int> *queue1,queue<int> *queue2,int *val)
{
    if (queue1->size()+queue2->size()==0)
    {
        printf("stack is empty\n");
        return;
    }
    else if(queue1->size()==0)
    {
        queue<int> *temp = q1;
        q1 = q2;
        q2 = temp;
    }
    //将先进去的元素顺序压入另一个队列，并出队，最后只剩下一个元素，然后出队
    while (queue1->size()>1)
    {
        int temp = queue1->front();//获取队首元素
        queue2->push(temp);
        queue1->pop();
    }
    *val = queue1->front();
    queue1->pop();
}
//获取栈顶元素
void Top(queue<int> queue1,queue<int> queue2,int *val)
{
    if (queue1.size()+queue2.size()==0)
    {
        printf("stack is empty\n");
        return;
    }
    else if(q1.size()==0)
    {
        *val = q1.back();//获取队列的队尾元素
    }
    else
    {
        *val = q2.back();//获取队列的队尾元素
    }
}

测试代码：

#include <stdio.h>
#include <stack>
#include <queue>
using namespace std;

int main()
{
    //两个栈实现一个队列
    stack<int> s1,s2;
    int i;
    for (i=0;i<3;++i)
    {
        appendTail(&s1,i+1);
    }
    appendTail(&s1,5);
    printf("queue--------size:%d\n",s1.size()+s2.size());
    int data;
    deleteHead(&s1,&s2,&data);
    printf("delete_data-------%d\n",data);
    printf("queue--------size:%d\n",s1.size()+s2.size());

    //两个队列实现一个栈
    queue<int> q1,q2;
    for (i=0;i<5;++i)
    {
        Push(&q1,2*i+1);
    }
    int val;
    Pop(&q1,&q2,&val);
    Pop(&q1,&q2,&val);
//  Pop(&q1,&q2,&val);
    Top(q1,q2,&val);
    printf("length:%d\n",q1.size()+q2.size());
    printf("val:%d\n",val);
}