用兩個棧實作一個隊列
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);
}