c语言课件：栈和队列

《c语言课件：栈和队列》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、栈和队列栈抽象数据类型栈的定义栈的表示和实现栈的应用举例数制转换表达式求解队列是限制仅在线性表的一端进行插入和删除运算的线性表。an...a2a1栈顶TOP栈底Bottom栈顶（TOP）允许插入和删除的一端。栈底（bottom)不允许插入和删除的一端。空栈表中没有元素。栈(Stack)an...a2a1进栈退栈栈顶栈底进栈最先插入的元素放在栈的底部。退栈最后插入的元素最先退栈。栈的基本概念栈:又称为后进先出的线性表（LIFO表，LastInFirstOut）一叠书或一叠盘子。栈与子程序调用调用子程序时，计算机将子程序要用到的参数及返回地址等信息存放在栈里子程序返回时，从栈顶

2、取回返回地址，转回主调程序继续运行。处理递归调用顺序栈用数组定义（类似于顺序表），将栈底位置设置在向量两端的任意一个端点；用top（整型量，栈顶指针）来指示栈当前栈顶位置。定义：typedef(type)Element;/*栈元素的数据类型*/#definemaxsize100/*栈初始的容量*/typedefstructstack{Elementdata[maxsize];inttop;}Stack;/*顺序栈类型定义*/Stack*s;/*s是顺序栈类型指针*/3210Top=-1空栈A3210TOPA进栈3210DCBAB、C、D依次进栈TOP3210BATOPD、C

3、依次退栈3210Top=-1，B、A退栈顺序栈：栈顶指针与栈中元素间的关系顺序栈栈底位置固定在数组的低端，即：S->data[0]----表示栈底元素；进栈：S->TOP加1（正向增长）。退栈：S->TOP减1。空栈：S->TOP<0栈满：S->TOP=maxsize-1上溢：栈满时再做进栈运算（一种出错状态，应设法避免）。顺序栈的几种基本运算置空栈判栈空进栈退栈取栈顶元素顺序栈的几种基本运算置空栈：Create(Stack&S)voidCreate(Stack&S)/*将顺序栈S置为空*/{S.top=-1}顺序栈的几种基本运算判栈空：BoolEmpty(Stack&S

4、)/*判定顺序栈S是否为空*/{if(S.top>=0)returnFalse;elsereturnTrue;}/*Empty*/voidPush(Stack&S,Elemente)/*将元素e插入栈S顶部*/{if(S.top==maxsize-1)Serr=StackOverflow;else{S.top++;S.data[S.top]=e;}}/*Push*/顺序栈的几种基本运算进栈：/*若栈S非空，取出栈顶元素删除*/voidPop(Element&e,Stack&S)/*Pop*/{if(Empty(S))Serr=StackUnderflow;else{e=S.

5、data[S.top];S.top--;}}退栈：Pop(S)顺序栈的几种基本运算/*取顺序栈S的栈顶*/ElementTop(Stack&S)/*Top*/{if(Empty(S)){输出“栈空”;returnNULL;}else{return(S.data[S.top]);}}取栈顶：Top(S)顺序栈的几种基本运算链栈栈的链式存储结构（当顺序栈的最大容量事先无法估计时，可采用链栈结构）。TOPe1next栈顶..链栈的定义：typedefstructcell*Position;typedefstructcell{Elemente1;Positionnext;}Cell

6、;typedefstructstack{Position*top;}Stack;链栈的特点插入和删除（进栈/退栈）仅能在表头位置上（栈顶）进行。链栈中的结点是动态产生的，可不考虑上溢问题。不需附加头结点，栈顶指针就是链表（即链栈）的头指针。voidPush(Elemente,Stack&S){Positionp;p=new(Cell);p->e1=e;p->next=S.top;S.top=p;}^…...栈底xs.top链栈进栈运算链栈退栈运算voidPop(Element&e,Stack&S){Positionp;if(S.top==NULL)SErr=StackUnd

7、erflow;else{e=S.top->e1;p=S.top;S.top=S.top->next;free(p);}}top^…...栈底topq栈小结顺序栈有发生上溢的可能，而链栈通常不会发生栈满（除非整个空间均被占满）只要满足LIFO原则，均可采用栈结构。栈的应用实例：递归调用。栈的应用举例一数制转换十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:N=(ndivd)*d+(nmodd)（185）10=（？）8（185）10=（271）882………780………