课件第四章堆栈和队列

1、逻辑结构存储结构运算建立结构线性表广义表串树二叉树文件图数组堆栈和队列顺序存储链式存储索引散列清除结构插入数据元素删除数据元素修改数据元素排序检索 数据结构的基本问题空间堆栈和队列特别感谢论坛上发言的同学魏嘉亮、马 骏、李嘉良、李欣阳、谭传奇、向 峰高 超、梁 鸿、赵继伟、李欣阳、陈俊平、程 志肖 遥、张庆余、董 适、王伟东 三个问题的说明1、期中考试（不设置期中考试）2、18个学时的实验课（自行安排 ）3、第一次作业相似度极高的问题 第四章 堆栈和队列栈：stack堆：heap 堆和栈的主要区别： 在计算机领域程序设计回溯法递归程序的执行过程编译程序变量的存储空间的分配表达式的翻译与求值计算

2、操作系统作业调度、进程调度堆栈队列后续章节二叉树的层次遍历堆栈和队列的整体印象逻辑结构：线性结构特点：操作仅允许在线性表一端或两端进行，是一般线性表操作的子集a1a2a3an-1an进栈退栈top栈顶 栈底 堆栈后进先出适于处理具有递归结构的数据QUEUE0.M1 0 1 2 3 4 5 M-1abcdadrearFront出队进队队列先进先出适于存放需要按一定次序依次处理但尚未处理的数据4.1 堆栈的基本概念4.2 堆栈的顺序存储结构4.3 堆栈的链式存储结构4.4 队列的基本概念4.5 队列的顺序存储结构4.6 队列的链式存储结构本章内容重点堆栈和队列习题课4.1 堆栈的基本概念 是一种只

3、允许在表的一端进行插入操作和删除操作的线性表。允许操作的一端称为栈顶，栈顶元素的位置由一个称为栈顶指针的变量给出。当表中没有元素时，称之为空栈。堆栈后进先出abcdextop进栈dcbaetop(一) 堆栈的定义出栈a1a2a3an-1an进栈退栈top栈顶 栈底 后进先出堆栈的示意图特殊性1. 其操作仅仅是一般线性表的 操作的一个子集。2. 插入和删除操作的位置受到 限制。(二) 堆栈的基本操作1. 插入（进栈、入栈）2. 删除（出栈、退栈）3. 测试堆栈是否为空4. 测试堆栈是否已满5. 检索当前栈顶元素abcdetop=4 描述堆栈的顺序存储结构最简单的方法是利用一维数组 STACK 0

4、.M1 来表示,同时定义一个整型变量( 不妨取名为top) 给出栈顶元素的位置。 4.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-1top#define M 1000SElemType STACKM;int top;类型定义初始时,top= 11. 初始化堆栈void INITIALS( int &top ) top= 1;2. 测试堆栈是否为空int EMPT

5、YS( int top ) return top= 1; 栈空,返回1,否则,返回0。(二) 堆栈的基本算法0 1 2 3 M-1topint FULLS( int top ) return top=M1;栈满,返回1,否则,返回0。3. 测试堆栈是否已满0 1 2 3 M-1STACK0.M-1top0 1 2 3 4 M-1 adcbtopitemSTACK+top=item；return 1;算法int PUSH( SElemType STACK , int &top, SElmeType item ) if( FULLS(top) ) return 0; else 插入成功,返回1,否

6、则，返回0。4. 插入(进栈)算法0 1 2 3 4 M-1 adcbtopeitem=STACKtop-;return 1;算法删除成功,返回1,否则,返回0。5. 删除(出栈)算法int POP( SElemType STACK , int &top, SElemType &item ) if(EMPTYS(top) return 0; else (三) 多栈共享连续空间问题（以两个堆栈共享一个数组为例）STACK10.M1-1top1已用空间 可用空间STACK20.M2-1top2已用空间 可 用 空 间STACK0.M-1当i=1时，将item 插入第1个栈，当i=2时，将item

7、插入第2个栈。插入 可用空间0 1 2 M-1top0 top1第1个栈第2个栈top0、top1 分别给出第1个与第2个栈的栈顶元素的位置。top0+；STACKtop0=item；i=1top1-；STACKtop1=item；i=2栈满的条件是top0=top11栈满0 1 2 M-1第1个栈第2个栈top0 top1可用空间0 1 2 M-1top0 top1第1个栈第2个栈int PUSH( SElemType STACK , int top , int i, SelemType item ) if(top0=top11) /* 栈满 */ return 0; else if(i=1

8、) /* 插入第1个栈 */ STACK+top0=item; else /* 插入第2个栈 */ STACK top1=item; return 1; 算法int PUSH( SElemType STACK , int top , int i, SElemType item ) if (top0=top11) return 0; else if (i=1) top0+; /* 修改第1个栈顶指针 */ else top1 ; /* 修改第2个栈顶指针 */ STACKtopi1=item; return 1; 算法当i=1时，删除第1个栈的栈顶元素，当i=2时，删除第2个栈的栈顶元素。top

9、0 ;i=1top1+;i=20 1 2 M-1可 用 空 间第1栈栈空的条件删除 栈空top0=-1 top1=M第2栈栈空的条件可用空间0 1 2 M-1top0 top1第1个栈第2个栈int POP( SElemType STACK , int top , int i, SElemType item ) if(i=1) if(top0=1) return 0; else item=STACKtop0 ; return 1; else if(top1=M) return 0; else item=STACKtop1+; return 1; 算法对第一个栈进行操作对第二个栈进行操作 链接堆

10、栈就是用一个线性链表来实现一个堆栈结构, 同时设置一个指针变量( 这里不妨仍用top表示)指出当前栈顶元素所在链结点的位置。栈为空时，有top=NULL。 4.3 堆栈的链式存储结构(一)构造原理链接堆栈链栈栈顶元素 在一个初始为空的链接堆栈中依次插入元素 A, B, C, D 以后, 堆栈的状态为例ABCDtoptypedef struct node SElmeType data; struct node *link; STNode, *STLink;类型定义void INITIAL( STLink &top ) top=NULL;1.堆栈初始化(二)基本算法int EMPTYS( STLi

11、nk top ) return top=NULL;2.测试堆栈是否为空3.插入(进栈)算法top . itempint PUSHLINK( STLink &top, SElemType item ) STLink p; if( !(p=(STLink)malloc(sizeof(STNode) ) return 0; else p-data=item; /*将item送新结点数据域*/ p-link=top; /*将新结点插在链表最前面*/ top=p; /*修改栈顶指针的指向*/ return 1; 算法不必判断栈满等效于在链表最前面插入一个新结点4.删除(退栈)算法top . pint P

12、OPLINK( STLink &top, SElemType &item ) STLink p; if ( EMPTYS(top) ) return 0; /* 删除失败*/ else p=top; /* 暂时保存栈顶结点的地址*/ item=top-data; /*保存被删栈顶的数据信息*/ top=top-link; /* 删除栈顶结点 */ free(p); /* 释放被删除结点*/ return 1; /* 删除成功*/ 算法仍然要判断栈空！堆栈与递归（见课程网站上压缩文件中的栈和队列中的递归过程）课程网站：关于堆栈和递归.rar 4.4 队列的基本概念 简称 。是一种只允许在表的一端

13、进行插入操作，而在表的另一端进行删除操作的线性表。允许插入的一端称为队尾，队尾元素的位置由rear指出； 允许删除的一端称为队头, 队头元素的位置由front指出。队队列abcdea队头元素e队尾元素ebf先进先出(一) 队列的定义队头元素队尾元素anan-1a3a4a2a1进队出队队头元素队尾元素先进先出队列的示意图(二) 队列的基本操作1. 队列的插入（进队、入队）3. 测试队列是否为空2. 队列的删除（出队、退队）4. 检索当前队头元素5. 创建一个空队特殊性1. 其操作仅是一般线性表 的操作的一个子集。2. 插入和删除操作的位置 受到限制。 4.5 队列的顺序存储结构 在实际程序设计过

14、程中，通常借助一个一维数组QUEUE0.M1来描述队列的顺序存储结构，同时，设置两个变量 front与rear分别指出当前队头元素与队尾元素的位置。QUEUE0.M-1 0 1 2 3 M-1abcdeae(一)构造原理front队头位置rear队尾位置QUEUE0.M1 0 1 2 3 4 5 M-1abcdad初始时, 队列为空, 有 front= 1 rear= 1测试队列为空的条件是 front=rear约定 front 指出实际队头元素所在位置的前一个位置。rear 指出实际队尾元素所在的位置,rearfront#define M 1000QElemType QUEUEM;int f

15、ront, rear;类型定义void INITIALQ( int &front, int &rear ) front= 1; rear= 1;2、测试队列是否为空int EMPTYQ( int front, int rear ) return front=rear;队空，返回1,否则，返回0。(二)基本算法1. 初始化队列3. 插入(进队)算法frontrearitem int ADDQ(QElemType QUEUE , int &rear, QElemType item) if(rear=M-1) /* 队满，插入失败 */ return 0; else QUEUE+rear=item;

16、 return 1; /* 队未满，插入成功 */ 算法0 1 M-1acdb4. 删除(出队)算法frontrearint DELQ(QElemType QUEUE , int &front, int &rear, QElemType &item) if(EMPTYQ(front,rear) return 0; /* 队空，删除失败 */ else item=QUEUE+front; return 1; /* 队非空，删除成功 */ 算法0 1 M-1acdb0 1 2 3 4 5 6 7 =M-1abcdefghfrontrearrear=M-1=7 int ADDQ(QElemType

17、QUEUE , int &rear, QElemType item) if(rear=M-1) /* 队满，插入失败 */ return 0; else QUEUE+rear=item; return 1; /* 队未满，插入成功 */ 算法假溢出插入 item01234M-1M-2:(三)循环队列 把队列(数组)设想成头尾相连的循环表，使得数组前部由于删除操作而导致的无用空间尽可能得到重复利用，这样的队列称为 。循环队列QUEUE0.M-10 1 2 3 4 M-2 M-1留课后学习 队列的链式存储结构是用一个线性链表表示一个队列，指针front与rear分别指向实际队头元素与实际队尾元素所

18、在的链结点。 4.6 队列的链式存储结构(一)构造原理rear指出实际队尾元素所在的位置; front指出实际队头元素所在位置的前一个位置。约定链接队列链队front与rear分别指向实际队头和队尾元素 空队对应的链表为空链表，空队的标志是 front = NULL 在一个初始为空的链接队列中依次插入 数据元素 A, B, C, D 以后, 队列的状态为例DCBAfrontrear队尾元素队头元素typedef struct node QElmeType data; struct node *link; QNode, *QLink;类型定义void INITIALQ(QLink &front,

19、 QLink &rear) front=NULL; rear=NULL；int EMPTYQ(QLink front) return front=NULL;队空,返回1否则,返回0(二)基本算法1. 初始化队列2. 测试队列是否为空pitemfront rearfrontrearpitemrear-link=p;rear=p;分两种情况3. 插入(进队)front=rear=NULL1初始队列为空2初始队列非空#define LEN sizeof(QNode)int ADDLINKQ( QLink &front, QLink &rear, QElemType item ) QLink p; if(!(p=(Qlink)malloc(LEN) /* 申请链结点 */ return 0; p-data=item; p-link=NULL; if(front=NULL) front=p; /* 插入空队的情况 */ else rear-link=p; rear=p; /* 插入非