第三章 栈和队列 栈和队列是两种重要的数据结构。

Presentation on theme: "第三章 栈和队列 栈和队列是两种重要的数据结构。"— Presentation transcript:

1 第三章 栈和队列 栈和队列是两种重要的数据结构。
从结构特性角度看，栈和对列也是线性表，其特殊性在于它们的基本操作是线性表的子集，是操作受限的线性表，可称为限定性的数据结构。 从数据类型角度看，其操作规则与线性表大不相同，是完全不同于线性表的抽象数据类型。

2 第一节 栈 一、栈的定义 栈是限定在表的一端进行插入和删除操作的线性表。 插入：称为进栈（或压栈）。 删除：称为出栈（或退栈）。
栈顶（top）：允许进行插入和删除操作的一端。 栈底（bottom）：不允许插入和删除操作的一端。 栈底 … an a2 a1 栈顶 基本操作： Initstack(&s): 栈初始化 Destroystack(&s)：撤消栈 Clearstack(&s)：置栈空 Stackempty(s) ：判栈空 Stacklength(S)：求栈中元素个数 Gettop(S,&e)： 取栈顶元素 Push(&S,e)： 入栈 Pop(&S,&e)： 出栈 特点：后进先出----LIFO Last In First Out

3 栈的表示与实现 三、栈的顺序存储结构----顺序栈 利用一组地址连续的存储单元依次存放从栈底到栈顶的数据元素。 顺序栈存储结构定义：
#define STACK_INIT_SIZE //存储空间初始分配量； #define STACKINCREMENT //存储空间分配增量 typedef struct { SElemType *base; SElemType *top; int stacksize; }SqStack; Base指向存储空间开始地址，top指示栈顶当前位置。 若栈空间未分配，则base为NULL； top==base:栈空 top-base==stachsize:栈满 元素进栈：在top位置插入元素，top增1 元素出栈：top减1。 top指针始终指向栈顶元素的下一个位置 。

4 顺序栈操作的实现 Status Initstack(Sqstack &s) { s.base=（SElemType *）
1、栈初始化：分配初始存储空间，初始化各变量。 Status Initstack(Sqstack &s) { s.base=（SElemType *） malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!b.base) exit(OVERFLOW); s.top=s.base; s.stacksize= STACK_INIT_SIZE ； return Ok； }

5 顺序栈操作的实现 2、撤消栈：释放栈空间。 status Destroystack(SqStack &s)
{ if(s.base) { free(s.base); s.base=NULL;return OK;} return ERROR; } 3、置栈空：将栈设置成空栈。 status Clearstack(SqStack &s) { if(s.base) { s.top=s.base;return OK;} 4、取栈顶元素：返回栈顶元素的值。 status GetTop(SqStack s,SElemType &e) { if(s.top==s.base) return ERROR; e=*(s.top-1); return OK

6 顺序栈操作的实现 if(!b.base) exit(OVERFLOW); e e 5、入栈操作：把元素压入栈中。
status Push(SqStack &s，SElemType e) { if(s.top-s.base>=s.stacksize) { s.base=（SElemType *）ralloc(s.base, (s.tacksize+STACKINCREMENT)*sizeof(SElemType)); if(!b.base) exit(OVERFLOW); s.top=s.base+s.stacksize; s.stacksize+=STACKINCREMENT; } *s.top=e; s.top++; return OK; top e B A base top B A base e 压栈操作

7 顺序栈操作的实现 { if (s.top==s.base) return ERROR; e=*(--s.top) return Ok }
6、出栈操作：删除栈顶元素。 Status Pop(Sqstack &s,Selemtype &e) { if (s.top==s.base) return ERROR; e=*(--s.top) return Ok } top Y B A base Y top B A base 出栈操作

8 链式栈的实现 用线性链表表示栈的存储结构，称为链栈。 链表头指针始终指向栈顶，同样用top表示。 无必要加头结点，栈空时：top=NULL
入栈：每当一个元素进栈时，申请一个新结点，插入到表头。 出栈：每当一个元素出栈时，从表头释放一个结点。 链栈结点结构描述如下 typedef struct stacknode{ ElemType data; struct stacknode *next; }StackNode; typedef struct { StackNode *top; }LinkStack; Data next S.top 栈顶 栈底

9 第二节 栈的应用 一、数制转换 将一个非负的十进制整数Ｎ转换为另一个等价的Ｂ进制数。
方法：不断用Ｎ及其商去除以Ｂ求余数直到商为０为止，所得余数的反序排列就是Ｎ的Ｂ进制表示。 5310的八进制表示　 (53)10＝(65)8 N　　 余数　　　商 5310的二进制表示　 (53)10＝(110101)2 N　　 余数　　　商 １ 5310的四进制表示　 (53)10＝(311)4 N　　　 余数　　　商 １ 实现方法：用一个栈来存放产生的余数，然后从栈顶到栈底依次输出余数就是所求的Ｂ进制数。

10 栈的应用 算法： typedef int DataType; void Comversion(int N,int B) { int i;
SeqStack S; InitStack(S); while(N) { Push(&S,N%B); N=N/B; } while(!StackEmpty(S)) { Pop(S,i); printf(“%d”,i); 算法的时间复杂度　O(logBN)。

11 栈的应用—表达式求值 一、算术四则运算法则： 先乘除后加减 从左至右 先括号内后括号外
方法：对运算符建立优先关系矩阵，按优先关系对表达式进行处理。 算符：运算符和界符。 根据法则1：乘除优先于加减，乘除优先级相同，加减优先级相同。 根据法则2：相邻两个同级运算符左优先。 根据法则3：“（”前面的运算符优先级低于“（”的优先级。“（”的优先级低于右边相邻算符。“）”左边的算符高于“）”的优先级。

12 栈的应用—表达式求值 + - * / ( ) # > < =

13 栈的应用—表达式求值 处理过程： 设置两个栈：操作数栈OPND和运算符栈OPTR。 设“#”表示表达式的开始和结束（作为界符），即
#表达式# 1、首先置操作数栈为空栈，把“#”移进运算符栈。 2、从左至右扫描表达式，凡遇到操作数一律进OPND栈；若遇到运算符，则把栈顶运算符与扫描运算符的优先数进行比较：若 < 扫描运算符进OPTR栈 = 若“（”和“）”，栈顶符号出栈；若为#，运算结束。 > 取OPND栈顶操作数与OPTR栈顶算符进行运算，参与运算的操作数和运算符出栈，运算结果进OPND栈 若表达式处理完，OPTR栈为#，OPND栈中只剩一项，表示表达式的运算结果，则分析成功。否则表明表达式有错。

14 栈的应用—表达式求值 例：3+5*(7-2) 步数 OPTR OPND 表达式 主要操作
# *（7-2）# push(OPND, 3) # *(7-2)# push(OPTR,’+’) # *(7-2)# push(OPND, 5) # , *(7-2)# push(OPTR,’*’) #+* , (7-2)# push(OPTR,’(’) #+*( , )# push(OPND,7) #+*( ,5, )# push(OPTR,’-’) #+*( ,5, )# push(OPND,2) #+*( ,5,7, )# opreate(7,’-’,2) #+*( ,5, )# pop(OPTR,‘(’),去掉‘）’ #+* ,5, # opreate(5,’*’,5) # ， # opreate(3,’+’,25) # # 成功

15 第三节 栈与递归的实现 递归函数：若在一个函数内部有直接或通过调用函数又间接调用自身，则称它们是递归函数，或者说是递归定义的。
n=0 n!= n*(n-1)! n>0 n<=1 f(n)= n*f(n-1)! n>0 int f( int n) { if (n <=1) then return (1) else return (n *f(n-1)); } Y=f(5); 1 f(1) return(1) 2 f(2) 递归函数的执行：递归调用通过栈实现;系统每调用一次函数, 系统就在栈顶分配该函数所需空间。 return(2) 3 f(3) return(6) 4 f(4) return(24) 5 f(5) return(120)

16 栈与递归的实现 递归算法设计一般分两步 ： ①将规模较大的原问题分解为一个或多个规模更小，但具有类似于原问题特性的子问题，即较大的问题递归地用较小的子问题来描述，解原问题的方法同样可用来解这些子问题。 ②确定一个或多个无须分解、可直接求解的最小子问题。 第一步称为递归步骤，第二步称为递归的终止条件。 在递归步骤里分解问题时，应使子问题相对于原问题更接近于递归终止条件，从而保证经过有限次递归步骤后达到递归终止条件而结束递归。

17 第四节 队列 队列是限定在表的一端进行插入，在另一端进行删除的线性表。 a1 a2 … an 一、队列的定义：
队头（Front）：允许删除的一端。 队尾(Rear)：允许插入的一端。 基本操作： InitQueue (&Q): 队列初始化 DestroyQueue (&Q)：撤消队列 ClearQueue (&Q)：置队列空 QueueEmpty(Q) ：判队列空 Queuelength(Q)：求队列元素个数 Gethead(Q,&e)： 取队列头元素 EnQueue (&Q,e)： 入队列 DeQueue (&Q,&e)：出队列 a1 a2 … an 删除 插入 特点：先入队列的元素总是先离开队列，所以称队列为先进先出（First In First Out）的线性表，简称FIFO。

18 队列的链式表示及实现 typedef struct QNode{ QElemType data; Struct QNode *next;
二、链队列：用线性链表表示队列的存储结构。 头指针----指向删除的一端 尾指针----指向插入的一端 链队列结点结构描述如下 typedef struct QNode{ QElemType data; Struct QNode *next; }Qnode,*QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue; LinkQueue Q; Q.front Q.reart

19 链队列基本操作 置空队列：保留头结点，头、尾指针置成初始状态。 1、队列初始化：建立链队列头结点，初始化头、尾指针。
Status Initqueue(linkqueue &Q) { Q.front =Q.rear=（QueuePtr）malloc(sizeof(Qnode)); Q.front->next=NULL; return OK; } 2、撤消队列：删除队列中所有结点（包括头结点）。 Status Destroyqueue(linkqueue &Q) { while (Q.front) {p= Q.front->next; free(Q.front); Q.front= p; 置空队列：保留头结点，头、尾指针置成初始状态。

20 链队列基本操作 3、入队操作：为入队元素申请结点，并插入到队尾。 Q x ۸ e ۸
Status Enqueue(linkqueue &Q,Qelemtype e) { p=(Qnode *)malloc(sizeof(Qnode)); if(!p) exit(OVERFLLOW); p->data=e; p->next=NULL; Q.rear->next=p; Q.rear=p; return OK; }

21 链队列基本操作 Status Dequeue(linkqueue &Q,Qelemtype &e)
3、出队操作：删除队头结点，并返回被删结点的值。 Q x z ۸ y Status Dequeue(linkqueue &Q,Qelemtype &e) { if (Q.front==Q.rear) return ERROR; p=Q.front->next; e=p->data; Q.front->next =p->next; if (Q.rear==p) Q.rear=Q.front; free(p); return OK; }

22 队列的顺序表示及实现 四、顺序队列：队列的顺序存储分配称为顺序队列。 顺序队列存储结构描述如下 #define MAXQSIZE 100
typedef struct { QElemType *base; int front; int rear; }SqQueue; SqQueue Q; 操作： 初 始：Q.front=Q.rear=0 元素进队：Q.base[Q.rear]=x;Q.rear++; 元素出队：e=Q.base[Q.front];Q.front++; 队 列 空：Q.front==Q.rear 队 列 满：Q.rear==MAXQSIZE

23 队列的顺序表示及实现 a3 a2 a1 四、顺序队列操作可能出现的问题 设MAXQSIZE=6 再有元素进队会怎样？ a6 a5 a4
Q.rear a4 a5 a6 出队 Q.front a4 a5 a6 Q.rear 进队 Q.front Q.rear Q.front 初态 Q.front a1 a2 a3 Q.rear 进队 Q.rear a1 a2 a3 出队 Q.front

24 队列的顺序表示及实现 a2 an a1 删除 Q.front 插入 队满的三种情况： 1、所有单元都有元素； 2、部分单元有元素；
3、所有单元均无元素。 当队满时再要插入元素，称为上溢。 假上溢：队空间中还有存储单元未使用，但不能再插入元素。 假上溢原因：头、尾指针值总是不断增加，已使用过的单元无法再使用。 解决假上溢的方法： 1、将队中元素依次向队头方向移动。 缺点：浪费时间。每移动一次，队中元素都要移动。 ２、将队空间设想成一个循环的表，即分配给队列的ｍ个存储单元可以循环使用，当rear为m时，若向量的开始端空着，又可从头使用空着的空间。当front为m时，也是一样。 Q.front a1 a2 an Q.rear 删除 插入

25 循环队列 实现方法：模(mod) 运算。 插入元素： Q.base[Q.rear]=x;
Q.rear=(Q.rear+1)％ MAXQSIZE; 删除元素: x=Q.base[s.front] Q.front=(Q.front+1)％ MAXQSIZE 循环队列：循环使用为队列分配的存储空间。 问题：队空队满都有：Q.front=Q.rear 区分队空队满的方法： 1、设置一个标志字段Q.tag区分队空队满（初值：tag=0 ） Q.tag=0 Q.front=Q.rear 队空 Q.tag=1 Q.front=Q.rear 队满 若进队操作前tag=0,进队操作后有Q.front=Q.rear，则置tag=1.   2、少用一个元素空间，ｍ个元素单元最多只存放ｍ－１个元素，且 front=rear 队空 在入队时，若（Q.rear+1）％MAXQSIZE=Q.front，则为队满。 ３、设置一个计数器记录队列中元素的个数。

26 循环队列算法 Status InitQueue(SqQueue &Q) { Q.base=（QElemType*）
1、循环队列初始化：为队列分配存储空间，头尾指针赋初值。 Status InitQueue(SqQueue &Q) { Q.base=（QElemType*） malloc(MAXQSIZE*sizeof(QElemType)); if(!Q.base) exit(OVERFLOW); Q.front =Q.rear=0; return OK; } 2、求队列长度 Status QueueLength(SqQueue Q) { return (Q.rear-Q.front+Maxsise)%Maxsize;

27 循环队列算法 Status Enqueue(sqqueue &Q,Qelemtype e)
3、入队操作：在队尾插入新元素。 Status Enqueue(sqqueue &Q,Qelemtype e) { if ((Q.rear+1)%Maxsize==Q.front) return ERROR; Q.base[Q.rear]=e; Q.rear=(Q.rear+1)%Maxsize; return OK; }

28 循环队列算法 { if (Q.front == Q.rear ) return ERROR; e=Q.base[Q.front];
4、出队操作：删除队头元素，并返回队头元素的值。 Status DeQueue(SqQueue &Q,QElemType &e) { if (Q.front == Q.rear ) return ERROR; e=Q.base[Q.front]; Q.front=(Q.front+1)%Maxsize; return OK; }

29 队列的应用 二、队列的应用 １、脱机打印输出：按申请的先后顺序依次输出。 ２、多用户系统中，多个用户排成队，分时地循环使用ＣＰＵ和主存。
3、按用户的优先级排成多个队，每个优先级一个队列。 ４、时时控制系统中，信号按接收的先后顺序依次处理。 5、网络信道信息传输，按到达的时间先后顺序依次进行。

30 作业 P22 3.17 √ 3.25 √ 3.29 √ 实验：下列题中任选一题 P96 2.1 停车场管理 2.5 算术表达式求值