(6)--第3章 栈和队列-栈数据结构.ppt

栈;1.栈和队列的定义和特点

2.栈的表示和操作的实现

3.栈的应用

4队列的的表示和操作的实现

5队列的应用;栈;栈的定义和特点;栈的定义和特点;数据对象:;栈的抽象数据类型描述;;Push和Pop可以穿插交替进行；

按照操作系列

(1)Push(S,A),Push(S,B),Push(S,C),Pop(S),Pop(S),Pop(S)

堆栈输出是？

(2)而Push(S,A),Pop(S),Push(S,B),Push(S,C),Pop(S),Pop(S)

堆栈输出是?;已知入栈顺序是ABCD，若栈不空时，可以出栈，则出栈序列有哪些，有多少个？;设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是（）。;已知入栈顺序是1,2,3，……，n，若栈不空时，可以出栈，如何判断是否为合法的出栈序列？;若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为;#defineMAXSIZE100//顺序栈存储空间的初始分配量

typedefstruct

{

SElemType*base;//栈底指针

SElemType*top;//栈顶指针

intstacksize;//栈可用最大容量

}SqStack;;空栈

base==top

stacksize=4;构造一个空栈

步骤：

(1)分配空间并检查空间是否分配失败，若失败则返回错误;StatusInitStack(SqStackS)

{

S.base=newSElemType[MAXSIZE]；

if(!S.base)returnOVERFLOW;

S.top=S.base;

S.stackSize=MAXSIZE;

returnOK;

};boolStackEmpty(SqStackS)

{

if(S.top==S.base)returntrue;

elsereturnfalse;

};intStackLength(SqStackS)

{

returnS.top–S.base;

};思路：

(1)判断是否栈满，若满则出错

(2)元素e压入栈顶

(3)栈顶指针加1;StatusPush(SqStackS,SElemTypee)

{

if(S.top-S.base==S.stacksize)//栈满

returnERROR;

*S.top++=e;

returnOK;

};(1)判断是否栈空，若空则出错

(2)栈顶指针减1

(3)获取栈顶元素e;(1)判断是否空栈，若空则返回错误

(2)否则通过栈顶指针获取栈顶元素;是运算受限的单链表，只能在链表头部进行操作，故没有必要附加头结点。栈顶指针就是链表的头指针。

;typedefstructStackNode{

SElemTypedata;

structStackNode*next;

}StackNode,*LinkStack;

LinkStackS;;voidInitStack(LinkStackS)

{

S=NULL;

};StatusStackEmpty(LinkStackS)

{

if(S==NULL)returnTRUE;

elsereturnFALSE;

}

;StatusPush(LinkStackS,SElemTypee)

{

p=newStackNode;//生成新结点p

if(!p)exit(OVERFLOW);

p-data=e;p-next=S;S=p;

returnOK;

};;SElemTypeGetTop(LinkStackS)

{

if(S==NULL)exit(1)；

elsereturnS–data;

};;表达式求值;

;

;算法描述;算法描述;OPTR;表达式的三种标识方法：;例如:Exp=a?b+(c?d/e)?f

前缀式:+?ab??c/def

中缀式:a?b+c?d/e?f

后缀式:ab?cde/?f?+;表达式a*(b+c)-d的后缀表达式是()。;如何从后缀式求值？;如何从原表达式求得后缀式？;从原表达式求得后缀式的