资源描述：
《数据结构-第三章栈和队列》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第3章限定性线性表—栈和队列3.1栈3.2队列栈和队列是两种常用的数据类型线性表栈队列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栈与队列栈是限定仅在表尾进行插入和删除的线性表。队列是限定仅在表尾进行插入、在表头进行删除的线性表。23.1栈3.1.1栈的定义3.1.2栈的表示和实现3.1.3栈的应用举例3.1.4栈与递归的实现33.1.1栈的定义：ADTStack{数据对象：D＝{ai
2、ai∈ElemSet,i
3、=1,2,...,n,n≥0}数据关系：R1＝{
4、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作:}ADTStack一、栈的类型定义栈是限定仅在表尾进行插入和删除的线性表。表尾被称为栈顶，表头被称为栈底。栈又被称为后进先出(lifo)的线性表。4InitStack(S)初始化一个空栈S。基本操作：ClearStack(S)将S清为空栈IsEmpty(S)若S为空栈,则返回true,否则false。GetTop(S)若S非空,则返回它的栈顶元素,否则返回'false'。Push(S,e)入栈
5、,插入元素e为新的栈顶元素。Pop(S)出栈,若S非空,则删除并返回它的栈顶元素,否则返回'false'。IsFull(S)若S为满栈,则返回true,否则false。5二、进栈、出栈图例根据栈定义，每次进栈的元素都被放在原栈顶元素之上而成为新的栈顶，而每次出栈的总是当前栈中“最新”的元素，即最后进栈的元素。进栈出栈进栈出栈栈顶栈底an…a2a163.1.2栈的表示和实现栈在计算机中主要有两种基本的存储结构：顺序存储结构和链式存储结构。顺序存储的栈为顺序栈；链式存储的栈为链栈。7一、顺序栈1、顺序栈的存储结构定义#defineMaxSize
6、50StackElementTypeS[MaxSize];/*用来存放栈中元素的一维数组*/inttop;/*栈顶指针，全局变量*/82、顺序栈中的进栈和出栈图例top=-1栈空FEDCBAtop=5栈满Atop=0插入ACBAtop=2栈长度393.顺序栈的基本操作特点下溢：栈空时再做退栈运算将产生溢出。1）栈底位置固定在顺序表的低端，即S[0]----表示栈底元素2）入栈：top++，保存元素；3）出栈：取元素,top--；4）空栈：top=-1；5）栈满：top=MaxSize-1；上溢：栈满时再做进栈运算（一种出错状态，应设法避免）
7、。103、顺序栈基本操作的实现1）初始化voidInitStack(int*S){/*构造一个空栈S*/top=-1;}112）判栈空intIsEmpty(int*S)/*判栈S为空栈时返回值为1，反之为0*/{return(top==-1?1:0);}123）判栈满intIsFull(int*S)/*判栈S为满时返回真，否则返回假*/{return(top==MaxSize-1?TRUE:FALSE);}134）进栈intPush(int*S,intx){if(top==MaxSize-1)return(FALSE);/*栈已满*/top
8、++;S[top]=x;return(TRUE);}145）出栈intPop(int*S,int*x){if(top==-1)/*栈为空*/return(FALSE);else{*x=S[top];top--;/*修改栈顶指针*/return(TRUE);}}156）取栈顶元素intGetTop（int*S,int*x）{/*将栈S的栈顶元素取出，放入x所指的单元，但栈顶指针保持不变*/if(top==-1)/*栈为空*/return(FALSE);else{*x=S[top];return(TRUE);}}16〖例〗设有一个空栈，栈顶指针
9、为1000H，现有输入序列为12345，PUSH,PUSH,POP,PUSH,POP,PUSH,PUSH后，输出序列为______，栈顶指针为_______2,31003Htop=1000H1top=1001Htop=1002H23top=1003H45输出序列：〖例〗在一个n个单元的顺序栈中，假定以地址高端(下标为n-1的单元)作为栈底，则向栈中压入一个元素时，栈顶指针top的变化是______top不变top=ntop=top-1top=top+1栈低栈顶top=-1n-1n-2…10〖例〗若一个栈的输入序列是1，2，…，n，输出序列的
10、第一个元素是n，则第i个输出元素是______n-in-i+1in-i-1top=-1nn-1…12top=n-1方法一：将栈的容量加到足够大，但这种方法由于事先难以估计容量，有
