《数据结构--第三章栈和队列课件.pptx》由会员分享，可在线阅读，更多相关《数据结构--第三章栈和队列课件.pptx（67页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、栈和队列是两种常用的数据类型 线性表 栈 队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1in+1 Delete(L,i)Delete(S,n)Delete(Q,1)1in栈与队列 栈是限定仅在表尾进行插入和删除的线性表。队列是限定仅在表尾进行插入、在表头进行删除的线性表。13.1 栈3.1.1 栈的定义3.1.2 栈的表示和实现3.1.3 栈的应用举例3.1.4 栈与递归的实现23.1.1 栈的定义：ADT Stack 数据对象：D ai|ai ElemSet,i=1,2,.,n,n0 数据关系：R1|ai-1,aiD,i=2,.,n 约定an 端
2、为栈顶，a1 端为栈底。基本操作:ADT Stack一、栈的类型定义栈是限定仅在表尾进行插入和删除的线性表。表尾被称为栈顶，表头被称为栈底。栈又被称为后进先出(lifo)的线性表。3InitStack(S)初始化一个空栈 S。基本操作：ClearStack(S)将 S 清为空栈IsEmpty(S)若 S 为空栈,则返回true,否则false。GetTop(S)若 S 非空,则返回它的栈顶元素,否则 返回 false。Push(S,e)入栈,插入元素 e 为新的栈顶元素。Pop(S)出栈,若 S 非空,则删除并返回它的栈 顶元素,否则返回 false。IsFull(S)若 S 为满栈,则返回t
3、rue,否则false。4二、进栈、出栈图例 根据栈定义，每次进栈的元素都被放在原栈顶元素之上而成为新的栈顶，而每次出栈的总是当前栈中“最新”的元素，即最后进栈的元素。进栈 出栈进栈出栈栈顶栈底ana2a153.1.2 栈的表示和实现栈在计算机中主要有两种基本的存储结构：顺序存储结构和链式存储结构。顺序存储的栈为顺序栈；链式存储的栈为链栈。6一、顺序栈1、顺序栈的存储结构定义#define MaxSize 50StackElementType SMaxSize;/*用来存放栈中元素的一维数组*/int top;/*栈顶指针，全局变量*/72、顺序栈中的进栈和出栈图例top=-1栈空FEDCBA
4、top=5栈满Atop=0插入ACBAtop=2栈长度383.顺序栈的基本操作特点下溢：栈空时再做退栈运算将产生溢出。1）栈底位置固定在顺序表的低端，即S0-表示栈底元素2）入栈：top+，保存元素；3）出栈：取元素,top-；4）空栈：top=-1；5）栈满：top=MaxSize-1；上溢：栈满时再做进栈运算（一种出错状态，应设法避免）。93、顺序栈基本操作的实现1）初始化void InitStack(int*S)/*构造一个空栈S*/top=-1;102）判栈空int IsEmpty(int*S)/*判栈S为空栈时返回值为1，反之为0*/return(top=-1?1:0);113）判栈满int IsFull(int*S)/*判栈S为满时返回真，否则返回假*/return(top=MaxSize-1?TRUE:FALSE);124）进栈int Push(int*S,int x)if(top=MaxSize-1)return(FALSE);/*栈已满*/top+;Stop=x;return(TRUE);135）出栈int Pop(int*S,int*x)if(top=-1)/*栈为空*/return(FALSE);else*x=Stop;top-;/*修改栈顶指针*/return(TRUE);14