数据结构初学者的几个问题,请帮忙
(1),如果进栈序列为123则可能的出栈序列为什麽有很多呢?栈的特点是后进先出,不是应该只有一种可能321吗?类似的,进栈序列为123456出栈序列可以得到135426不能得到435612,“因为4356出栈说明12已在栈中1不可能在2之前出栈”,不明白 1不可能在2之前出栈,又怎会有出栈序列135426呢?
根据先进后出原则:我们考虑题目123456顺序进栈,为什么可以是135426的顺序出栈?我们定义push(a)为入栈,po()p为出栈
那么整个过程是:
push(1)
pop()
push(2)
push(3)
pop()
push(4)
push(5)
pop()
pop()
p...全部
(1),如果进栈序列为123则可能的出栈序列为什麽有很多呢?栈的特点是后进先出,不是应该只有一种可能321吗?类似的,进栈序列为123456出栈序列可以得到135426不能得到435612,“因为4356出栈说明12已在栈中1不可能在2之前出栈”,不明白 1不可能在2之前出栈,又怎会有出栈序列135426呢?
根据先进后出原则:我们考虑题目123456顺序进栈,为什么可以是135426的顺序出栈?我们定义push(a)为入栈,po()p为出栈
那么整个过程是:
push(1)
pop()
push(2)
push(3)
pop()
push(4)
push(5)
pop()
pop()
pop()
push(6)
pop()
同理,435216无法实现。
////////////////////////////////////////////////////////
(2)在栈的基本操作函数原型说明中,为什麽有Status StackTraverse(SqStack S,Status(*visit) ())而在队列的基本操作函数原型说明中,是Status QueueTraverse(LikeQueue Q,visit() )?
不知道你的书的思路,每一种书对栈和队列的操作函数有自己的特点,但基本原则不会变,即栈和队列的性质不变。
////////////////////////////////////////////////////////
(3)在构造空对栈时有: se=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType));;而在栈的插入操作中又栈满时准价存储空间: se=(ElemType*)realloc( se,( acksize+STACKINCREMENT)*sizeof(ElemType)),其中的(ElemType*)也应该是(SElemType*)吧。
是的,就你写得来看,S的结构已定就是SElemType*
///////////////////////////////////////////////////
(4)有一个算法中有如下语句:
InitStack(S);//构造空栈
scanf("%d",N );
。
。。
Pop(S,e);
应该是
InitStack(&S);//构造空栈
scanf("%d",&N );
。。。
Pop(&S,&e);才对吧。
那要看S ,N代表什么,如果是普通变量,你说的就对,如果是指针,原题目就对。
//////////////////////////////////////////////////
(5)队列满判断:if(( ar+1)%MAXQSIZE== ont)为什麽不像栈满的判断那样:if( ont〉=MAXQSIZE)?
这里用到循环队列的知识,如果是普通的栈和队列那么判断方法大同小异,但循环队列的特点是提高利用率相当于一个圆环,所以通过模运算来达到目的,比如模8运算,无论数字多大,模8后始终在0-7之间,这样就的好处就是节省空间。
所以判断循环队列满的条件应该是队列的尾部不能把队列的头部覆盖了,根据这一原则,如题目所示的判断正确。收起