资源描述：
《数据结构(C语言版)第3章栈和队列讲义.电子教案.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构(C语言版)第3章栈和队列讲义.栈是限定仅在表的一端进行插入和删除操作的线性表。栈顶(top)：允许插入和删除的一端。栈底(bottom)：不允许插入和删除的另一端。空栈：不含元素的空表。a1a2an入栈出栈栈顶栈底特点先进后出（FILO）后进先出（LIFO）插入：入栈、进栈、压栈删除：出栈、弹栈栈的示意图栈的抽象数据类型定义ADTStack{数据对象：D＝{ai
2、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
3、ai-1,ai∈D,i=2,...,n}基本操作：InitSt
4、ack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。 操作结果：栈S被销毁。ClearStack(&S)初始条件：栈S已存在。 操作结果：将S清为空栈StackEmpty(S)初始条件：栈S已存在。 操作结果：若栈S为空栈，则返回TRUE，否则返回FALSE。StackLength(S)初始条件：栈S已存在。 操作结果：返回栈S中元素个数，即栈的长度。GetTop(S,&e)初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。Push(&S,e)初始条件：栈S已存在。 操作
5、结果：插入元素e为新的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值。StackTraverse(S,visit())初始条件：栈S已存在且非空，visit()为元素的访问函数。 操作结果：从栈底到栈顶依次对S的每个元素调用函数visit()，一旦visit()失败，则操作失败。}ADTStack栈的顺序存储（顺序栈）利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。结构定义：#defineSTACK_INIT_SIZE100;//存储空间初始分配量#defin
6、eSTACKINCREMENT10;//存储空间分配增量typedefstruct{ SElemType*base;//存储空间基址SElemType*top;//栈顶指针intstacksize;//当前已分配的存储空间，以元素为单位}SqStack;top=0123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0top123450进栈Atop出栈栈满BCDEF设数组大小为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop
7、123450ABCDEFtoptoptoptoptoptop栈空进栈：top加1出栈：top减1基本操作的算法描述StatusInitStack(SqStack&S) {//构造一个空栈SS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}//InitStackStatusGetTop(
8、SqStackS,SElemType&e) {//若栈不空，则用e返回S的栈顶元素，并返回OKif(S.top==S.base)returnERROR;//空栈e=*(S.top-1);//返回非空栈中栈顶元素returnOK;}//GetTopStatusPush(SqStack&S,SElemTypee) {//插入元素e为新的栈顶元素if(S.top-S.base>=S.stacksize){//栈满，追加存储空间S.base=(SElemType*)realloc(S.base, (S.stacksize+STACK
9、INCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT; }*(S.top++)=e;//插入新的元素returnOK;}//PushStatusPop(Stack&S,ElemType&e) {//栈不空，删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERRORif(S.top==S.base)returnERROR;//空栈e=*(--S.
10、top);//返回非空栈中栈顶元素returnOK;}//Pop链栈：栈的链接存储结构栈的链接存储结构及实现heada1a2an∧ai链栈需要加头结点吗？如何改造链表实现栈的链接存储？将哪一端作为栈顶？将链头作为栈顶，方便操作。链栈不需要附设头结点。栈顶栈底链栈：栈的链接存储结构栈的链接存
