堆栈问题

来源：百度知道 编辑：UC知道 时间：2024/06/01 18:28:30
已知有两个栈 S1 和 S2 及其基本操作 Push(S , x)、Pop(S)、Full(S) 和 Empty(S)，给出用此二栈实现队列操作Enqueue、Dequeue、Fullq 和Emptyq的算法
谁能给我个思路，我觉得把栈底相连不行，想不出好办法

因为栈是先进后出
队列是先进先出

所以对于一个栈ABCDEF来说
Push(S,Z)后结果为ABCDEFZ
如果Pop(S)的话是ABCDE
但如果是队列Enqueue(Q,Z)
结果同样是ABCDEZ
但是Dequeue(Q)就不一样了是BCDEF

这里有两个栈
用一个栈来过渡
可以从第一个栈中获取栈底部的内容

Enqueue(Q,x)
{
Push(S1,x);
}

Dequeue(Q)
{
// 导入到栈2
while(!Empty(S1))
{
Push(S2,Pop(S1));
}

if(!empty(s2))
{
int res=pop(s2);//假设栈和队列的内容都是int型
//倒会栈1
while(!Empty(S2))
{
Push(S1,Pop(S2));
}
return res;
}
return -1;//空队列返回一个错误值
}

FullQ(q)
{
return Full(s1);
}

EmptyQ(q)
{
return Empty(S1);
}

数据结构与算法书上都会讲这个的，基本也都很详细。
要说思路。。。看看书上的图一眼就明白了

我打字打半天，你也不一定明白怎么回事~