数据结构第3章栈和队列

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

1、第3章栈和队列3.1栈的概念3.2栈的存储结构3.3顺序栈的操作算法3.4链栈的操作算法3.5栈的应用举例---表达式求值第3章栈和队列3.6队列的概念3.7队列的存储结构3.8循环队列的操作算法3.9链队的操作算法第三章栈和队列3.1栈的概念1.定义：栈(Stack)是限定仅在表的一端进行插入或删除操作的线性表。2.栈的示意图P443.栈的抽象数据类型定义P453.2栈的存储结构有两种存储结构:顺序栈（常用）；链栈1、顺序栈顺序栈的类型定义：//------栈的顺序存储表示------#defineSTAC

2、K_NINT_SIZE100;//存储空间初始分配量#defineSTACKINCREMENT10;//存储空间分配增量typedefstruct{SElemType*base;//在栈构造之前和销毁之后，base的值为NULLSElemType*top;//栈顶指针intstacksize;//当前已分配的存储空间，以元素为单位}SqStack顺序栈的结构举例//------基本操作的函数原型说明------StatusInitStack(SqStack&S);    //构造一个空栈SStatusGetT

3、op(SqStackS,SElemType&e);    //若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORStatusPush(SqStack&S,SElemTypee);    //插入元素e为新的栈顶元素StatusPop(SqStack&S,SElemType&e);    //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR2、链栈链栈的类型定义：typedefstructLNode{//结点类型ElemTypedata;structLNode*nex

4、t;}Lnode,*Linkstack;LinkstackS;3.3顺序栈的操作算法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;}//InitStack2.取栈

5、顶元素StatusGetTop(SqStackS,SElemType&e)    //若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR    if(S.top==S.base)returnERROR;    e=*(S.top-1);    returnOK;}//GetTop3.压栈pushStatusPush(SqStack&S,SElemTypee){    //插入元素e为新的栈顶元素if(S.top-S.base>=S.stacksize){//栈满，追加存储空间S.bas

6、e=(SElemType*)realloc(S.base,      (S.stacksize+STACKINCREMENT)*sizeof(SElemType));      if(!S.base)exit(OVERFLOW);//存储分配失败S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;    }    *S.top++=e;    returnOK;}//push4.出栈popstatusPop(SqStack&S,SElemType

7、&e){    //若栈不为空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR    if(S.top==S.base)returnERROR;    e=*--S.top;    returnOK;}//Pop5判断栈是否为空intEmpty(SqStackS)    {//若栈为空，则返回0，否则返回1      if(s.top==s.base)return(0);       elsereturn(1);     }6判断栈是否为满intFull(SqStackS)

8、    {//若栈为满，则返回0，否则返回1    if(s.top-s.base)>=s.stacksizereturn(0);     elsereturn(1);    }3.4链栈的操作算法（自学）1.建立一个空栈（不带头结点）StatusInitLStack(Linkstack&S){    S=NULL;    returnok;}//InitLStack2.取