资源描述：
《数据结构名师课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章栈和队列通常称，栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)1≤i≤n栈和队列是两种常用的数据类型3.1栈的类型定义3.2栈类型的实现3.3栈的应用举例3.4队列的类型定义3.5队列类型的实现栈（stack）定义栈是只能在一端插入和删除的线性表特性：后进先出（LIFO）或先进后出（FILO）设栈s=（a1，a2，...,
2、ai，...，an），其中a1是栈底元素，an是栈顶元素。栈顶（top)：允许插入和删除的一端；约定top始终指向新数据元素将存放的位置。栈底（bottom):不允许插入和删除的一端。a1a2….an进栈出栈栈顶栈底3.1栈的类型定义ADTStack{数据对象：D＝{ai
3、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
4、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：}ADTStackInitStack(&S)DestroyStack(
5、&S)ClearStack(&S)StackEmpty(s)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则FALE。StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。
6、GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。a1a2an……ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为空栈。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。a1a2ane……Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。a1a2anan-1……设数组S是一个顺序栈，栈的最大容量stacksize=4，初始状态top=010S[4]2310bases[top]=xtop=to
7、p+1top102530S[4]2310topbasetop=top-1x=s[top]栈空10进栈30出栈S[4]2310Top=0top栈满top=stacksize10253040S[4]2310top=4base3.2栈类型的实现顺序栈链栈a1a2top1.顺序栈：一维数组s[M]用顺序存储结构表示的栈。顺序栈用一组连续的存储单元存放自栈底到栈顶的数据元素，一般用一维数组表示，设置一个简单变量top指示栈顶位置，称为栈顶指针，它始终指向待插入元素的位置。top=0123450栈空栈顶指针top,指向实际栈
8、顶后的空位置，初值为0top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空//-----栈的顺序存储表示-----#defineSTACK_INIT_SIZE100;//存储空间的初始分配量#defineSTACKINCREMENT10;//存储空间的分配增量typedefstruct{SElemTyp
9、e*base;//栈底指针SElemType*top;//栈顶指针(栈顶元素的下一个位置)intstacksize;//当前分配的存储容量}SqStack;类似于线性表的顺序映象实现，指向表尾的指针可以作为栈顶指针。1）和顺序表一样采用增量式的空间分配；2）操作和栈顶相关： 插入操作（入栈）：将待插元素插入到栈顶元素的下一个位置； 删除操作（出栈）：删除栈顶元素； 取元素操作：取栈顶元素的值。 各操作的操作位置与栈顶元素的位置或其下一个位置相关，希望在O(1)时间内能获取操作位置，故可设置专门的栈顶指针top。3
10、）约定：top指向栈顶元素的下一个位置（便于表示空栈）。4）栈顶的初始化：S.top=S.base(在上述3)约定下的空栈形式)，5）栈空：S.base==S.top，栈满：S.top-S.base>=S.stacksize6）入栈：*S.top++=e，出栈：e=*--S.top注意：4),5),6)步受3)制约。约定不同，相应的判定和处理也不一样。如假设top就指向栈
