用两个栈实现一个队列
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()<=)
{
while (s1->size()>)
{
int data = stack1->top();
stack1->pop();
stack2->push(data);
}
}
if (stack2->size()==)
{
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() == && queue2->size() != )
{
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()==)
{
printf("stack is empty\n");
return;
}
else if(queue1->size()==)
{
queue<int> *temp = q1;
q1 = q2;
q2 = temp;
}
//将先进去的元素顺序压入另一个队列，并出队，最后只剩下一个元素，然后出队
while (queue1->size()>)
{
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()==)
{
printf("stack is empty\n");
return;
}
else if(q1.size()==)
{
*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=;i<;++i)
{
appendTail(&s1,i+);
}
appendTail(&s1,);
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=;i<;++i)
{
Push(&q1,*i+);
}
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);
}