03-数据结构-栈与队列1

《03-数据结构-栈与队列1》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第三章栈与队列栈与队列：限定操作的线性表。第一节栈一、逻辑结构lx栈的定义限定只能在表的一端进行插入、删除的线性表。退栈进栈（弹出）（压入）后进先出LIFO表（LastInFirstOut）实例：“进制数转换”、“表达式求值”、“函数调用关系”、“括号匹配问题”、“汉诺塔问题”、“迷宫问题"……2、基本操作进栈Push/出栈Pop取栈顶元素GetTop判别栈空StackEmpty/栈满StackFull3、栈的应用背景许多问题的求解分为若干步骤，而当前步骤的解答，是建立在后继步骤的解答基础上的。二》问题分解的步骤和求解的步骤次序恰好

2、相反。二.顺序存储结构动态顺序存储结构：存储空间随栈的大小而变化。ttdefineSTACK_INIT_SIZE100//初始化时分配的空间typedefstruct//定义栈类型{ElemType*base,*top;//栈底、栈顶指针intstacksize;//栈的存储空间大小}SqStock;SqStackS;//定义一个栈结构1、初始化栈StatusSqStacklnit(SqStack&S){S・base=malloc(STACK_INIT_SIZE*sizeof(ElemType));if(!S.base)return

3、(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;return(OK);}扌戋空:S・top二二S・base扌戋》蕎:S・top二二S・base+S・stacksize2、进栈StatusSqStack_Push(SqStack&S,ElemTypee){if(S・top==S・base+S・stacksize)return(OVERFLOW);S・top二e;S・top++;return(OK);}3、出栈算法StatusSqStack_Pop(SqStack&S,ElemTy

4、pe&e){if(S.top二二S.base)return(UNDERFLOW);S・top一一;e二S・top;return(OK);^7//77777//77/7/7/77777777/777/7//7777>//才////////////a

5、i]b[l]#definemaxsize=100intstack[maxsize],topO=0,topl二maxsizeT;intpushO(inte){if(topO>topi)return(0);stack[topO]=e;top0++;return(1);}intpushl(inte){if(topO>topi)return(0);stack[topl]=e;topi—;return(1);}intpopO(int*e){if(top0==0)return(0);topO--；*e=stack[topO];return(l)

6、;}intpopl(int*e){if(top0~0)return(0);top0++;*e=stack[topl];return(l);}三、链栈typedefstructlinknode//栈中结点类型{ElemTypedata;structlinknode}LinkNode;typedefstruct{LinkNode*top;intstacksize;}LinkStack;*link;//定义栈类型//栈顶指针//栈的大小（可选）LinkStackS;初始化：S.top二二NULL;S.stacksize~O栈空：S・top

7、二二NULL栈满：系统内存不够K进栈StatusLinkStackPush(LinkStack&S，ElemTypee){LinkNode*p;p=(LinkNode*)malloc(sizeof(LinkNode));if(p==NULL)return(OVERFLOW);//上溢p->dato二e;p->link=S.top;S.top=p;return(OK);}2、出栈StatusLinkStackPop(LinkStack&S,ElemType&e){LinkNode*p;if(S.top==NULL)return(UND

8、ERFLOW);p=S.top;e=S・top->data;S・top=S・top->link;free(p);return(OK);3.特殊头结点的讨论进栈、出栈是最常用的操作二》链栈的头指针频繁变更二》参数传递的负担二》应约定链栈