第3章栈和队列

《第3章栈和队列》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章栈和队列北京师范大学教育技术学院杨开城一、栈——栈的定义如果一个线性表的插入和删除操作只能在线性表的一端进行，而不能在其他位置上进行，那么这个线性表被称为栈(Stack)。后进先出(LastInFirstOut)栈的操作包括：①初始化空栈②销毁栈③判断栈的空和满④入栈⑤出栈一、栈——顺序栈(1)顺序栈的数据类型定义如下：typedefstructstack_tag{elemtype*elem;/*指向存放数据元素的内存块*/inttop;/*栈顶标识，elem[top]是栈顶元素*/intsize;/*栈的容量*/}SQSTACK;一、栈——顺序栈(2)1．初始

2、化栈intInitSqstack(SQSTACK*S,intn){/*初始化顺序栈，栈的容量是n。成功则返回1，否则返回0*/S->elem=(elemtype*)malloc(n*sizeof(elemtype));/*为数据元素分配内存*/if(S->elem==NULL)return0;/*初始化失败*/S->size=n;/*设置栈的容量*/S->top=-1;/*设置栈为空栈*/return1;}2．销毁栈voidDestroySqstack(SQSTACK*S){/*释放栈所占有的内存*/free(S->elem);/*释放内存，并设置为NULL*/S->

3、elem=NULL;S->top=-1;/*将其他成员设置成安全值*/S->size=0;}一、栈——顺序栈(3)3．入栈intPush(SQSTACK*S,elemtypee){/*在栈顶一端插入数据元素e，操作成功，则返回1，否则返回0*/if(IsSqstackFull(*S))return0;/*栈满，操作失败*/S->top++;/*top增1*/S->elem[S->top]=e;/*将e赋值成新的栈顶*/return1;}4．出栈intPop(SQSTACK*S,elemtype*e){/*获取栈顶数据元素，并删除栈顶。操作成功，则返回1，否则返回0*/

4、if(IsSqstackEmpty(*S))return0;/*如果栈空，操作失败*/*e=S->elem[S->top];/*获取栈顶元素*/S->top--;/*删除栈顶*/return1;}一、栈——顺序栈(4)5．判断栈空、栈满intIsSqstackEmpty(SQSTACKS){/*如果栈空，则返回1，否则返回0*/returnS.top==-1;/*top是栈顶标识，是-1时表示空栈*/}intIsSqstackFull(SQSTACKS){/*如果栈满，则返回1，否则返回0*/returnS.top==S.size-1;/*top作为elem的下标，其

5、最大值是size-1*/}一、栈——链式栈(1)链式栈的数据类型定义：typedefstructnode_tag{elemtypedata;structnode_tag*next;}NODE,*NODEPTR,*LINKSTACK;链式栈的操作：1．入栈intPush(LINKSTACKL,elemtypee){/*将数据元素e入栈*/NODEPTRp;p=(NODEPTR)malloc(sizeof(NODE));if(p==NULL)return0;p->data=e;/*形成数据元素e的结点p*/p->next=L->next;/*将p插到头结点后面*/L->n

6、ext=p;return1;}一、栈——链式栈(2)2．出栈intPop(LINKSTACKL,elemtype*e){/*获取栈顶数据，删除栈顶*/NODEPTRp;p=L->next;/*p指向栈顶*/if(p==NULL)return0;L->next=p->next;/*摘除栈顶*/*e=p->data;/*获取原栈顶数据*/free(p);/*释放原栈顶结点*/return1;}二、栈的应用——括号匹配检查while(str[i]!=0){ch=str[i];if(ch=='(')Push(&s,ch);elseif(ch==')')if(!Pop(&s,&

7、ch)){/*缺少左括号与当前右括号配对*/DestroySqstack(&s);return0;}i++;}if(IsSqstackEmpty(s))i=1;elsei=0;/*说明有左括号没有配对*/DestroySqstack(&s);/*销毁栈*/returni;}【任务描述】要求设计算法，对于给定的表达式字符串，检查其中括号是否匹配。typedefcharelemtype;intCheckBracket(char*str){/*如果字符串str中括号配对，则返回1，否则返回0*/inti,len;SQSTACKs;/*定义一个栈*/elem