堆栈和队列

第四章 堆栈和队列 第四章 堆栈和队列 在在计计算算机机领领域 域 程序设计 枚举法、回溯法 递归程序的执行过程 编译程序 变量的存储空间的分配 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 达式的翻译与求值计算 操作系统 作业调度、进程调度 内存空间的分配¼ 堆 栈 堆 栈 队 列 队 列 4.1 堆栈的基本概念 4.2 堆栈的顺序存储结构 4.3 堆栈的链式存储结构 4.4 堆栈的应用举例(习 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 课) 4.5 队列的基本概念 4.6 队列的顺序存储结构 4.7 队列的链式存储结构 本章内容本章内容 4.1堆栈的基本概念4.1堆栈的基本概念 一. 堆栈的定义 是一种只允许在表的一端进行插入操 作和删除操作的线性表。允许操作的一端称为栈 顶，栈顶元素的位置由一个称为栈顶指针的变量 给出。当表中没有元素时，称之为空栈。 堆栈堆栈 后进先出后进先出 a b c d e x top 进栈 dcba e top 出栈 a1 a2 a3 an-1 an … 进 栈 进 栈 退 栈 退 栈 toptop 栈顶 栈底 后 进 先 出 后 进 先 出 二.堆栈的基本操作二.堆栈的基本操作 （进栈、入栈）（进栈、入栈）1. 插入1. 插入 2. 删除2. 删除（出栈、退栈）（出栈、退栈） 3. 测试堆栈是否为空3. 测试堆栈是否为空 4. 测试堆栈是否已满4. 测试堆栈是否已满 5. 检索当前栈顶元素5. 检索当前栈顶元素 特 殊 性 特 殊 性 1. 其操作仅仅是一般线性表的 操作的一个子集。 1. 其操作仅仅是一般线性表的 操作的一个子集。 2. 插入和删除操作的位置受到 限制。 2. 插入和删除操作的位置受到 限制。 Ö Ö Ö 0 1 2 3 4 …… M-1 STACK[0: M-1] a b c d e top=4 描述堆栈的顺序存储结构最简单的方法是利用 一维数组 STACK[ 0: M–1 ] 来表示,同时定义一个 整型变量(不妨取名为top) 给出栈顶元素的位置。 描述堆栈的顺序存储结构最简单的方法是利用 一维数组 STACK[ 0: M–1 ] 来表示,同时定义一个 整型变量(不妨取名为top) 给出栈顶元素的位置。 一. 构造原理 4.2堆栈的顺序存储结构4.2堆栈的顺序存储结构 上溢 下溢 上溢 下溢 —当堆栈已满时做插入操作。 (top=M–1)—当堆栈已满时做插入操作。 (top=M–1) —当堆栈为空时做删除操作。 (top=–1)—当堆栈为空时做删除操作。 (top=–1) 数组: 静态结构 堆栈: 动态结构 数组: 静态结构 堆栈: 动态结构 溢出溢出 #define M 1000 SElemType STACK[M]; int top; 类型定义类型定 义 初始时,top= –1初始时,top= –1 void INITIALS( int &top ) { top= –1; } int EMPTYS( int top ) { return top== –1; } 栈空,返回1,否则,返回0。栈空,返回1,否则,返回0。 1. 初始化堆栈 2. 测试堆栈是否为空 二. 堆栈的基本算法 int FULLS( int top ) { return top==M–1; } 栈满,返回1,否则,返回0。栈满,返回1,否则,返回0。 3. 测试堆栈是否已满 0 1 2 3 4 M-1 a dcb top …item STACK[++top]=item ； return 1; 算法算法int PUSH( SElemType STACK[ ], int &top, SElmeType item ) { if( FULLS(top) ) return 0; else { } } 插入成功,返回1, 否则,返回0。 插入成功,返回1, 否则,返回0。 4. 插入(进栈)算法 0 1 2 3 4 M-1 a dcb top …e item=STACK[top--]; return 1; item=STACK[top--]; return 1; 算法算法int POP( SElemType STACK[ ], int &top, SElemType item ) { if( EMPTYS(top) ) return 0; else{ } } int POP( SElemType STACK[ ], int &top, SElemType item ) { if( EMPTYS(top) ) return 0; else{ } } 删除成功,返回1, 否则,返回0。 删除成功,返回1, 否则,返回0。 5. 删除(出栈)算法 三. 多栈共享连续空间问题 （以两个堆栈共享一个数组为例） STACK[0: M-1] top[0]、top[1] 分别为第1个与第2个栈的栈顶元素指针。 可用空间 0 1 2 … M-1 第 1 个栈 第 2 个栈 top[0] top[1] 插入： 当i=1时，将item 插入第1个栈， 当i=2时，将item 插入第2个栈。 可用空间 0 1 2 … M-1 第 1 个栈 第 2 个栈 top[0] top[1] top[0]++； STACK[top[0]]=item； i=1i=1 top[1]--； STACK[top[1]]=item； i=2i=2 0 1 2 … M-1 第 1 个栈 第 2 个栈 top[0] top[1] 栈满的条件是 top[0]=top[1]–1top[0]=top[1]–1 栈满栈满 int PUSH( SElemType STACK[ ], int top[ ], int i, SelemType item ) { if (top[0]==top[1]–1) return 0; else { if (i==1) STACK[++top[0]]=item; else STACK[– –top[1]]=item; return 1; } } 算法算法 int PUSH( SElemType STACK[ ], int top[ ], int i, SElemType item ) { if (top[0]==top[1]–1) return 0; else { if (i==1) top[0]++; else top[1]– –; STACK[top[i–1]]=item; return 1; } } 算法算法 删除： 当i=1时，删除第1个栈的栈顶元素， 当i=2时，删除第2个栈的栈顶元素。 可用空间 0 1 2 … M-1 第 1 个栈 第 2 个栈 top[0] top[1] top[0]– –; i=1i=1 top[1]++; i=2i=2 0 1 2 … M-1 可用空间 top[0]=-1 top[1]=M 第1栈栈空的条件第1栈栈空的条件 第2栈栈空的条件 栈空栈空 int POP( SElemType STACK[ ], int top[ ], int i, SElemType item ) { if (i==1) if (top[0]==–1) return 0; else { item=STACK[top[0]– –]; return 1; } else if (top[1]==M) return 0; else { item=STACK[top[1]++]; return 1; } } 算法算法 对第一个栈进行操作对第一个栈进行操作 对第二个栈进行操作对第二个栈进行操作 链接堆栈就是用一个线性链表来实现一个 堆栈结构, 同时设置一个指针变量( 这里不妨 仍用top表示)指出当前栈顶元素所在链结点的 位置。栈为空时，有top=NULL。 链接堆栈就是用一个线性链表来实现一个 堆栈结构, 同时设置一个指针变量( 这里不妨 仍用top表示)指出当前栈顶元素所在链结点的 位置。栈为空时，有top=NULL。 4.3堆栈的链式存储结构4.3堆栈的链式存储结构 一.构造原理一.构造原理 链接堆栈链接堆栈 链栈链栈 在一个初始为空的链接堆栈中依次插入元素 A, B, C, D 以后, 堆栈的状态为 D C B A ^ top 栈顶元素栈顶元素 typedef struct node { SElmeType data; struct node *link; } STNode, *STLink; typedef struct node { SElmeType data; struct node *link; } STNode, *STLink; 类型定义类型定 义 void INITIAL( STLink &top ) { top=NULL; } int EMPTYS( STLink top ) { return top==NULL; } 2.测试堆栈是否为空2.测试堆栈是否为空 1.堆栈初始化1.堆栈初始化 二.基本算法二.基本算法 3.插入(进栈)算法3.插入(进栈)算法 top ...... ^item p int PUSH_LINK( 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.删除(退栈)算法4.删除(退栈)算法 top ...... ^ p int POP_LINK( STLink &top, SElemType &item ) { STLink p; if ( EMPTYS(top) ) return 0; /* 删除失败*/ else { p=top; /* 暂时保存栈顶结点的地址*/ item=top->data; /*保存被删栈顶的数据信息*/ top=top->link; /* 删除栈顶结点 */ free(p); /* 释放被删除结点*/ return 1; /* 删除成功*/ } } 算法算法 仍然要判断栈空！仍然要判断栈空！ 见习题课 (2) 见习题课 (2) 4.4 堆栈的应用举例4.4 堆栈的应用举例 4.5 队列的基本概念4.5 队列的基本概念 一. 队列的定义 简称 。是一种只允许在表的一端 进行插入操作，而在表的另一端进行删除操作 的线性表。允许插入的一端称为队尾，队尾元 素的位置由rear指出； 允许删除的一端称为队 头, 队头元素的位置由front指出。 简称 。是一种只允许在表的一端 进行插入操作，而在表的另一端进行删除操作 的线性表。允许插入的一端称为队尾，队尾元 素的位置由rear指出； 允许删除的一端称为队 头, 队头元素的位置由front指出。 队队队列队列 a b c d ea 队头元素队头元素 e 队尾元素队尾元素 eb f 队尾元素队尾元素队头元素队头元素 先进先出先进先出 anan-1a3 a4a2a1 … 进队进队出队出队 队头元素 队尾元素 先进先出先进先出 二. 队列的基本操作 1. 队列的插入（进队、入队） 3. 测试队列是否为空 2. 队列的删除（出队、退队） 4. 检索当前队头元素 5. 创建一个空队 特 殊 性 特 殊 性 1. 其操作仅是一般线性表 的操作的一个子集。 1. 其操作仅是一般线性表 的操作的一个子集。 2. 插入和删除操作的位置 受到限制。 2. 插入和删除操作的位置 受到限制。 Ö Ö Ö 4.6 队列的顺序存储结构4.6 队列的顺序存储结构 在实际程序设计过程中，通常借助一个一维 数组QUEUE[0: M–1]来描述队列的顺序存储结构， 同时,设置两个变量 front与rear分别指出当前队 头元素与队尾元素的位置。 在实际程序设计过程中，通常借助一个一维 数组QUEUE[0: M–1]来描述队列的顺序存储结构， 同时,设置两个变量 front与rear分别指出当前队 头元素与队尾元素的位置。 QUEUE[0: M-1] 0 1 2 3 M-1 a b c d ea e 队头元素 队尾元素 一.构造原理一.构造原理 约定约定 rear 指出实际队尾元素所在的位置,rear 指出实际队尾元素所在的位置, front 指出实际队头元素所在位置的前一个位置。front 指出实际队头元素所在位置的前一个位置。 front rear QUEUE[0: M–1] 0 1 2 3 4 5 M-1 a b c da d 初始时, 队列为空, 有 front= –1 rear= –1 测试队列为空的条件是 front=rear #define M 1000 QElemType QUEUE[M]; int front, rear; 类型定义类型定 义 1. 初始化队列1. 初始化队列 void INITIALQ( int &front, int &rear ) { front= –1; rear= –1; } 2、测试队列是否为空2、测试队列是否为空 int EMPTYQ( int front,int rear ) { return front==rear; } 队空,返回1,否则,返回0。队空,返回1,否则,返回0。 二.基本算法二.基本算法 3. 插入(进队)算法3. 插入(进队)算法 0 M-1 a c db front rear item int ADDQ( QElemType QUEUE[], int &rear, int &item ) { if (rear==M-1) /* 队列满，插入失败 */ return 0; else { QUEUE[++rear]=item; return 1; /* 队列未满，插入成功 */ { } 算法算法 4. 删除(出队)算法4. 删除(出队)算法 0 1 2 3 4 M-1 a c db front rear int DELQ( QElemType QUEUE[], int &front, int &rear, QElemType &item ) { if ( EMPTYQ(front,rear) ) return 0; /* 队列为空，删除失败 */ else { item=QUEUE[++front]; return 1; /* 队列非空，删除成功 */ } } 算法算法 0 1 2 3 4 5 6 7 =M-1 a b c d e f g h front rear rear=M-1=7rear=M-1=7 item int ADDQ( QElemType QUEUE[], int &rear, int &item ) { if (rear==M-1) /* 队列满，插入失败 */ return 0; else { QUEUE[++rear]=item; return 1; /* 队列未满，插入成功 */ { } 假 溢 出 假 溢 出 …… 0 1 2 3 4 …… M-2 M-1 0 1 2 3 4 M-1M-2 : : QUEUE[0: M-1] 把队列(数组)设想成头尾相连的循环表，使 得数组前部由于删除操作而导致的无用空间尽可 能得到重复利用，这样的队列称为循环队列。 三.循环队列三.循环队列 队列的链式存储结构是用一个线性链表表 示一个队列，指针front 与rear分别指向实际 队头元素与实际队尾元素所在的链结点。 队列的链式存储结构是用一个线性链表表 示一个队列，指针front 与rear分别指向实际 队头元素与实际队尾元素所在的链结点。 4.7 队列的链式存储结构4.7 队列的链式存储结构 约定约定 rear 指出实际队尾元素所在的位置, front 指出实际队头元素所在位置的前一个位置。 一.构造原理一.构造原理 在一个初始为空的链接队列中依次插入数 据元素 A, B, C, D 以后, 队列的状态为 A B C D ^ front rear 空队对应的链表为空链表，空队的标志是 front = NULL typedef struct node { QElmeType data; struct node *link; } QNode, *QLink; 类型定义类型定 义 1. 初始化队列1. 初始化队列 void INITIALQ( QLink &front, QLink &rear ) { front=NULL; rear=NULL； } 2. 测试队列是否为空2. 测试队列是否为空 int EMPTYQ( QLink front ) { return front==NULL; } 队空,返回1,否则,返回0。队空,返回1,否则,返回0。 一.基本算法一.基本算法 3. 插入算法3. 插入算法 p item ^ front rear … front rear p item ^ rear->link=p; rear=p; 为什么为什么 分两种情况分两种情况 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; /* 插入非空队的情况 */ return 1; } } 算法算法 4. 删除算法4. 删除算法 … front rear ^ int DEL_LINKQ( QLink &front, QLink &rear, QElemType &item ) { Qlink p; if ( EMPTYQ(front) ) return 0; /* 队列为空，删除失败 */ else { p=front; front=front->link; item=p->data; free(p); return 1; /* 队列非空，删除成功 */ } } 算法算法 front=front->link;front=front->link; 5. 销毁一个队列5. 销毁一个队列 所谓销毁一个队列是指将队列所对应的 链表中所有结点都删除，并且释放其存储空 间，使队列成为一个空队(空链表)。 所谓销毁一个队列是指将队列所对应的 链表中所有结点都删除，并且释放其存储空 间，使队列成为一个空队(空链表)。 … ^ front rear 归结为一个线性链表的删除归结为一个线性链表的删除 void DESLINKQ(QLink &front, QLink &rear) { while(front){ /* 队列非空时 */ rear=front->link; free(front); /* 释放一个结点空间 */ front=rear; } } 算法算法 … ^ front rear 本章内 容小结本章内 容小结 本章内 容小结 堆 栈 、 队 列 堆 栈 、 队 列 堆栈、队列的基本概念堆栈、队列的基本概念 堆栈、队列的顺序存储结构堆栈、队列的顺序存储结构 堆栈、队列的链式存储结构堆栈、队列的链式存储结构 堆栈、队列的应用举例堆栈、队列的应用举例 堆栈、队列是特殊线性表(特殊性) （循环队列） 堆栈、队列的定义 堆栈、队列的基本操作 构造原理、特点 对应的插入、删除操作的算法设计 构造原理、特点 对应的插入、删除操作的算法设计 操作的时间都为O(1) 操作的时间都为O(1)