请利用两个栈s1和s2来模拟一个队列。已知栈的三个运算定义如下: (1)push(st,x):元素x入st栈: (2)pop(st,x):st栈顶元素出栈,赋给变量x; (3)sempty(st):判st栈是否为空。 那么如

admin2017-11-14  44

问题 请利用两个栈s1和s2来模拟一个队列。已知栈的三个运算定义如下:
    (1)push(st,x):元素x入st栈:
    (2)pop(st,x):st栈顶元素出栈,赋给变量x;
    (3)sempty(st):判st栈是否为空。
    那么如何利用栈的运算来实现该队列的三个运算:
    (1)enqueue:插入一个元素入队列;
    (2)dequeue:删除一个元素出队列:
    (3)queue_empty:判队列为空。
(请写明算法的思想及必要的注释。)

选项

答案栈的特点是后进先出,队列的特点是先进先出。所以,用两个栈s1和s2模拟一个队列时,s1作输入栈,逐个元素压栈,以此模拟队列元素的入队。当需要出队时,将栈s1退栈并逐个压入栈s2中,s1中最先入栈的元素,在s2中处于栈顶。s2退栈,相当于队列的出队,实现了先进先出。显然,只有栈s2为空且s1也为空,才算是队列空。 (1)int enqueue(stack s1,elemtp x){ //sl是容量为n的栈,栈中元素类型是elemtp。本算法将x入栈, //若入栈成功返回1,否则返回0 if(topl==n&&!sempty(s2)) //topl是栈s1的栈顶指针,是全局变量 {printf(”栈满”);return(O);} //sl满s2非空,这时s1不能再入栈 if(top1==n&&sempty(s2)) //若s2为空,先将sl退栈,元素再压栈到s2 {while(!sempty(s1)){pop(s1,x);push(s2,X);} push(s1,x);return(1); //x入栈,实现了队列元素的入队 } (2)void dequeue(stack s2,s1){ //s2是输出栈,本算法将s2栈顶元素退栈,实现队列元素的出队 if(!sempty(s2)) //栈s2不空,则直接出队 {pop(s2,x);printf(”出队元素为”,X);} else //处理s2空栈 if(sempty(s1)){printf(”队列空”);exit(0);} //若输入栈也为空,则判定队空 else //先将栈s1倒入s2中,再做出队操作 {while(!sempty(s1)){pop(s1,x);push(s2,x);} pop(s2,x); //s2退栈相当于队列出队 printf(”出队元素”,X); } (3)int queue_empty(){ //本算法判用栈s1和s2模拟的队列是否为空 if(sempty(s1)&&sempty(s2))return(1); //队列空 else return(0); //队列不空 }

解析
转载请注明原文地址:https://kaotiyun.com/show/qxRi777K
0

随机试题
最新回复(0)