利用两个栈S1和S2来模拟一个队列.若不存在栈溢出问题,则请写出用栈的操作来实现队列的插入和删除的算法.

Question

如题所述

Answer 1

使用两个栈，分别依元素加入的顺序和其反序保存元素，在适当的时机将元素在两个栈中进行转移，从而模拟队列的操作。
令S1中元素的顺序为自底向上与元素添加顺序一致，S2与其相反，则：
加入队列时，若S2不空，则将S2中的元素依次出栈，每出栈一个向S1中入栈一个；将入队元素入S1栈；
从队列中取出时，若S1不空，则将S1中元素依次出栈，每出栈一个向S2中入栈一个；从S2栈顶出栈一个即队列中取出的元素。

用伪代码描述如下：
Enqueue(elem)
while(!S2.empty())

temp = S2.pop();

S1.push(temp);

S1.push(elem);

Dequeue()
while(!S1.empty())

temp = S1.pop();

S2.push(temp);

return S2.pop();本回答被提问者和网友采纳