【数据结构电子课件】 栈和队列.ppt

《【数据结构电子课件】 栈和队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、栈队列递归第三章栈和队列栈(Stack)定义:是限定仅在表尾进行插入或删除操作的线性表。允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点：后进先出(LIFO)a1topbottoman....进栈出栈栈的主要操作ADTStack{//对象由数据类型为StackData的元素构成intPush(stack*S,StackDatax);//进栈intPop(stack*S,StackData&x);//出栈intGetTop(stack*S,StackData&x);//取栈顶voidInitStack(stack*S);//置空栈i

2、ntStackEmpty(stack*S);//判栈空否intStackFull(stack*S);//判栈满否}栈的表示和实现顺序栈：栈的顺序存储结构，利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，指针top指向栈顶元素在顺序栈中的下一个位置，base为栈底指针，指向栈底的位置。base空栈a进栈b进栈aabtopbasetopbasetoptoptopabcdee进栈abcdef进栈溢出abde出栈cbasebasebasetop顺序栈的类型表示:#defineSTACK_INIT_SIZE100；#defineSTACKINCREMENT

3、10；typedefcharStackData;typedefstruct{//顺序栈定义StackData*base;//栈底指针StackData*top;//栈顶指针intstacksize；//当前已分配的存储空间}SeqStack；判栈空intStackEmpty(SeqStack*S){if(S->top==S->base)return1//判栈空,空则返回1elsereturn0;//否则返回0}判栈满intStackFull(SeqStack*S){if(S->top-S->base>=S->StackSize)return1//判栈满,满

4、则返回1elsereturn0;//否则返回0}顺序栈的基本运算:初始化voidInitStack(SeqStack*S){//置空栈S->base=(StackData*)malloc(STACK_INIT_SIZE*sizeof(StackData));if(!S->base)exit(OVERFLOW);S->top=S->base;S->stacksize=STACK_INIT_SIZE;Returnok;}入栈intPush(SeqStack*S,StackDatax){//插入元素x为新的栈顶元素if(StackFull(S)){S->bas

5、e=(StackData*)malloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(StackData));if(!S->base)exit(overflow);S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT;//追加存储空间}*(S->top)=x;（S->top）++;Returnok}取栈顶元素intGettop(SeqStack*S,StackData&x){//若栈空返回0,否则栈顶元素读到x并返回1if(StackEmpty(S))

6、return0;(S->top)--;x=*(S->top);return1;}出栈intpop(SeqStack*S,StackData&x){//若栈空返回0,否则栈顶元素退出到x并返回1if(StackEmpty(S))return0;--(S->top);x=*(S->top);return1;}链式栈:栈的链接表示链式栈无栈满问题，空间可扩充插入与删除仅在栈顶处执行链式栈的栈顶在链头适合于多栈操作top链式栈(LinkStack)的定义typedefintStackData;typedefstructnode{StackDatadata;//结点

7、structnode*link;//链指针}StackNode;typedefstruct{StackNode*top;//栈顶指针}LinkStack;链式栈操作实现初始化voidInitStack(LinkStack*S){S->top=NULL;}入栈intPush(LinkStack*S,StackDatax){StackNode*p=(StackNode*)malloc(sizeof(StackNode));p->data=x;p->link=S->top;S->top=p;return1;}判栈空intStackEmpty(LinkStack*

8、S){returnS->top==NULL;}出栈intPop(L