兩個棧實作一個隊列和兩個隊列實作一個棧【算法導論課後題】

關于兩個棧實作一個隊列和兩個隊列實作一個棧問題，網上有很多資料。這裡隻描述自己認為操作最少的方法。

兩個棧實作一個隊列

思想：假設兩個棧分别為s1,s2。對s1進行入隊，出隊時，先判斷s2是否為空，如果是則将s1中元素壓入s2并彈出最上面元素，如果不是，則直接彈出s2最上面的元素。

<span style="font-size:18px;">EnQueue(s1,s2,k){
push(s1,k)</span><span style="font-family:Arial, Helvetica, sans-serif;"><span style="font-size: 18px;">;</span></span><span style="font-size:18px;">
}
//出隊
DeQueue(s1,s2){
if( IsEmptyStack(s2)){
while(sizeofStack(s1) !=0){
push(s2,pop(s1));
}
}
if(IsEmptyStack(s2)){
printf("stack overflow");
}
return pop(s2);
}</span>
           

兩個隊列實作一個棧

思想：一個隊列用來入棧q1，另一個作為中轉站q2。對不為空的隊列進行入棧和出棧操作，入棧時直接入隊即可，出棧時，先将隊列中n-1個元素壓入中轉站，最後一個元素出隊

<span style="font-size:18px;">push(q1,q2,k){
if(IsEmptyQueue(q1)){
EnQueue(q2,k);
}
else{
EnQueue(q1,k);
}
}</span>
           

出棧時需要兩個臨時指針pushtmp和tmp作為入棧和中轉站（該方法消耗空間）

<span style="font-size:18px;">pop(q1,q2){
Queue pushtmp,tmp;
if(IsEmptyQueue(q1)){
pushtmp=q2;
tmp=q1;
}
else{
pushtmp=q1;
tmp=q2;
}
if(IsEmptyQueue(pushtmp)){
printf("OverFlow");
}
else{
while(sizeof(pushtmp) !=1)
DeQueue(tmp,DeQueue(pushtmp));
}
return Dequeue(pushtmp);
}</span>