《程序设计04-队栈》由会员分享，可在线阅读，更多相关《程序设计04-队栈（74页珍藏版）》请在金锄头文库上搜索。
1、晏海华数据结结构与程序设计设计 基础础 数据结构 （Data Structures and Programming）北航计算机学院 晏海华1第三讲：栈与队(Stack and Queue) 北航计算机学院 晏海华晏海华逻辑结构存储结构运算运算建立结构建立结构线性表广义表串树 二叉树文件图数组堆栈和队列顺序存储链式存储索引散列清除结构清除结构插入数据元素插入数据元素删除数据元素删除数据元素修改数据元素修改数据元素排序排序检索检索数据结构的基本问题空间堆栈和队列堆栈和队列晏海华第三讲 栈和队列晏海华4这些红圈所标注的功能所涉及的数据是如何组织的 栈和队是解决问题时常用的数据组织方式晏海华在计算机领
2、域程序设计 回溯法 递归程序的执行过程 编译程序 变量的存储空间的分配 表达式的翻译与求值计算 操作系统 作业调度、进程调度栈队 列后续章节 二叉树的层次遍历晏海华栈和队列的整体印象逻辑结构：线性结构 特 点：操作仅允许在线性表一端或 两端进行，是一般线性表操作的子集a1a2a3an-1an进 栈退 栈top 栈顶 栈底 栈后进先出 (Last In First Out,LIFO)适于处理具有递 归结构的数据QUEUE0.M10 1 2 3 4 5 M-1 ab cdadrearFront 出队进队队列先进先出 (First In First Out,FIFO)适于存放需要按一定次 序依次处理
3、但尚未处理 的数据晏海华3.1 栈的基本概念 3.2 栈的顺序存储结构 3.3 栈的链式存储结构3.4 队列的基本概念 3.5 队列的顺序存储结构 3.6 队列的链式存储结构本章内容重点晏海华3.1 堆栈栈的基本概念是一种只允许在表的一端进行插入操 作和删除操作的线性表。允许操作的一端称为栈 顶，栈顶元素的位置由一个称为栈顶指针的变量 给出。当表中没有元素时，称之为空栈。栈(Stack)后进先出a b c d extop进栈dcbaetop(一) 栈栈的定义义出栈晏海华a1a2a3an-1an进 栈退 栈 top 栈顶 栈底 栈的示意图LIFOLIFO（Last-In-First-OutLas
4、t-In-First-Out）栈的特点：1）元素间呈线性关系2）插入删除在一端进行3）后进先出，先进后出晏海华特 殊 性1. 其操作仅仅是一般线性表的操作的一个子集。 2. 插入和删除操作的位置受到限制。(二) 栈栈的基本操作1. 插入（进栈、入栈、压栈 ）2. 删除（出栈、退栈、弹出 ）3. 测试栈是否为空 4. 测试栈是否已满 5. 检索当前栈顶元素晏海华栈栈的基本操作nvoid push(Stack s, ElemType e) /压一个元素进栈nElemType pop(Stack s) /从栈中弹出一个元素nint isEmpty(Stack s) /判断栈是否为空nint isFu
5、ll(Stack s) /判断栈是否已满nElemType getTop(Stack s) /获取栈顶 元素11晏海华ab cd etop=4描述栈的顺序存储结构最简单的方法是 利用一维数组 STACK 0.M1 来表示,同时 定义一个整型变量( 不妨取名为top) 给出栈顶 元素的位置。3.2 栈栈的顺顺序存储结储结 构（顺顺序栈栈）(一) 构造原理0 1 2 3 4 M-1STACK0.M-1晏海华上溢 下溢 当栈已满时做插入操作。 当栈为空时做删除操作。溢出数组:栈:静态结构 动态结构(top=M1) (top=1)0 1 2 3 M-1STACK0.M-1top0 1 2 3 M-1t
6、op晏海华#define MAXSIZE 1000 ElemType STACKMAXSIZE; int Top;类型定义初始时,Top= 1由于Top变量需要在多 个函数间共享，在此 定义为全局变量。晏海华1. 初始化堆栈栈void initStack( ) Top= 1; 2. 测试测试 堆栈栈是否为为空int isEmpty( ) return Top= 1; 栈空,返回1,否则,返回0。(二) 顺顺序栈栈的基本算法0 1 2 3 M-1top晏海华int isFull( ) return Top=MAXSIZE1; 栈满,返回1,否则,返回0。3. 测试测试 堆栈栈是否已满满0 1 2
7、 3 M-1STACK0.M-1Top晏海华0 1 2 3 4 M-1 adcbtopitems+Top=item；算法void push( ElemType s , ElmeType item ) if( isFull() )Error(“Full Stack!”);else入栈成功4. 进栈进栈 算法void Error(char s) printf(“%sn”, s);exit( -1); 晏海华0 1 2 3 4 M-1 adcbtopereturn sTop-;算法出栈成功5. 出栈栈算法ElemType pop( ElemType s )if(isEmpty()Error(“Emp
8、yt Stack!”);else晏海华(三) 多栈栈共享连续连续 空间问题间问题（以两个栈共享一个数组为例）STACK10.M1-1top1已用空间 可用空间STACK20.M2-1top2已用空间 可 用 空 间STACK0.M-1当i=1时，将item 插入第1个栈， 当i=2时，将item 插入第2个栈。进栈 可用空间0 1 2 M-1top1 top2第1个栈第2个栈Top1、Top2 分别给出第1个与第2个栈的栈顶元素的位置。晏海华top1+； STACKtop1=item；栈栈1top2-； STACKtop2=item；栈栈2栈满的条件是 top1=top21栈满0 1 2 M-
9、1第1个栈第2个栈top1 top2可用空间0 1 2 M-1top1 top2第1个栈第2个栈晏海华void push( ElemType s , int i, ElemType item ) if(top1=top21) /* 栈满 */Error(“Full Stack!”);else if(i=1) /* 插入第1个栈 */STACK+top1=item;else /* 插入第2个栈 */STACK top2=item;return 1;算法晏海华当i=1时，删除第1个栈的栈顶元素， 当i=2时，删除第2个栈的栈顶元素。top1 ;i=1 top2+;i=20 1 2 MAXSIZE-
10、1 可 用 空 间第1栈栈空的条件出栈 栈空top1=-1 top2=MAXSIZE第2栈栈空的条件可用空间0 1 2 M-1top1 top2第1个栈第2个栈晏海华EleType pop( ElemType s , int i) if(i=1) if(top1=1) Error(“Empty Stack1!”);else return stop1 ;elseif(top2=MAXSIZE)Error(“Empty Stack2!”); elsereturn stop2+;算法对第一个栈进行操作对第二个栈进行操作晏海华链接栈就是用一个线性链表来实现一 个栈结构, 同时设置一个指针变量( 这里
11、不妨仍用top表示)指出当前栈顶元素所在链 结点的位置。栈为空时，有top=NULL。3.3 栈栈的链链式存储结储结 构(一)构造原理链接栈 链栈晏海华栈顶元素在一个初始为空的链接栈中依次插入元素A, B, C, D以后, 栈的状态为例ABCDtop链栈是一种特殊的链表，其结点的插入（进栈）和删 除（出栈）操作始终在链表的头。晏海华struct node SElmeType data;struct node *link; ; typedef struct node *Nodeptr; typedef struct node Node; Nodeptr Top; /即为链为链 表的头结头结 点指针针 类型定义由于Top变量需要在多 个函数间共享，在此 定义为全局变量。晏海华void initStack( ) Top=NULL; 1.栈初始化(二)链栈的基本算法int isEmpty( )return Top=NULL;2.测试堆栈是否为空思考为什么不需要测试 栈是否已满 晏海华3.进栈算法top. item pvoid push( ElemType item ) Nodeptr p;if( (p=(Nodeptr)malloc(sizeof(Node)=NULL
