教 师：曾晓东 电 话：13679007201 E_mail: zengxiaodong@263.net 计算机软件技术基础 教 师：曾晓东 电 话：13679007201 E_mail: zengxiaodong@263.net.

Presentation on theme: "教 师：曾晓东 电 话：13679007201 E_mail: zengxiaodong@263.net 计算机软件技术基础 教 师：曾晓东 电 话：13679007201 E_mail: zengxiaodong@263.net."— Presentation transcript:

1 教 师：曾晓东 电 话：13679007201 E_mail: zengxiaodong@263.net
计算机软件技术基础 教 师：曾晓东 电 话： E_mail:

2 3.4 栈 一、栈的定义 二、栈的运算 三、栈的存储结构及算法 四、栈的应用 计算机软件技术基础 数据结构——栈和队列

3 一、栈的定义 an a n-1 a1 stack[n-1] top 进栈 stack[0] 栈底 出栈
栈顶 进栈 stack[0] 栈底 出栈 栈是限定只能在表的一端进行插入和删除操作的线性表。允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)。 设栈s=(a1,a2,...,an)，a1称为栈底元素，an称为栈顶元素。 栈中元素按a1,a2,...,an次序进栈，又按an,...,a2,a1次序退栈。因此栈的操作特点是：后进先出（LIFO）；n=0时称为空栈。 计算机软件技术基础 数据结构——栈和队列

4 二、栈的运算 1.初始化栈 INISTACK(S) 将栈S置成空栈 2.判空栈 ISEMPTY(S) 若栈S是空栈，返回“真”， 否则返回“假” 3.进栈 PUSH(S,x) 在栈S顶部插入（压入）元素x 4.出栈 POP(S) 若栈S不空，删除顶部元素 5.取栈顶 GETTOP(S) 取栈顶元素，并不改变栈中内容 计算机软件技术基础 数据结构——栈和队列

5 三、栈的存储结构及算法 1.顺序栈 1)类型定义 顺序栈用向量作为栈的存储结构，可用一维数组s[1:m]表示。其中m表示栈的最大容量。用一个简单变量top来指示栈顶位置，称为栈顶指示器。top=0表示栈空，top=m表示栈满。 类型定义 struct SeqStack{ elemtype stack[MAXSIZE]; int top; }; 计算机软件技术基础 数据结构——栈和队列

6 三、栈的存储结构及算法 2）顺序栈初始化 ⑴ 操作: 建一空栈，将栈顶位设置为-1 ⑵ 接口： 入口和出口参数均为堆栈指针s ⑶ 算法描述：令栈顶位 s.top为-1 ⑷ 函数实现： void iniStack(SeqStack &s){ s.top = -1; } 计算机软件技术基础 数据结构——栈和队列

7 三、栈的存储结构及算法 3)进栈算法 ⑴ 操作: 先将栈顶位置加一 将数据放入栈顶位置 ⑵ 接口： 入口参数：堆栈指针s，新数据元素x
函数值： 成功则返回 1 ( 用true表示), 失败则返回 0 ( 用false表示) 计算机软件技术基础 数据结构——栈和队列

8 三、栈的存储结构及算法 (3)算法描述 计算机软件技术基础 数据结构——栈和队列

9 三、栈的存储结构及算法 (4) 函数实现 int push(SeqStack &s, elemtype x) { if(s.top >= MAXSIZE-1) return (false); s.top++; s.stack[s.top]=x; return (true); } 计算机软件技术基础 数据结构——栈和队列

10 三、栈的存储结构及算法 4)出栈算法 (1) 操作 取栈顶位置内数据. 再将栈顶位置减一 (2) 接口 入口参数：堆栈指针s
函数值： 成功则返回数据元素x, 失败则返回NULL 计算机软件技术基础 数据结构——栈和队列

11 三、栈的存储结构及算法 (3) 算法描述 计算机软件技术基础 数据结构——栈和队列

12 三、栈的存储结构及算法 (4) 函数实现 elemtype pop(SeqStack &s) { if(s.top < 0) return NULL; s.top--; return s.stack[s.top+1]; } 计算机软件技术基础 数据结构——栈和队列

13 三、栈的存储结构及算法 a1 a2 …… an …… bm …… b2 b1
5)双栈操作 顺序栈的缺点：栈满后不能进行进栈操作，否则将产生“上溢”错误 同时使用同类的两个栈，充分利用剩余空间 两栈共用一个存储空间，分别从两端向中间增长 a a …… an …… bm …… b b1 n 出栈 MAXSIZE-m MAXSIZE-2 MAXSIZE -1 栈1底 栈1顶 入栈 栈2顶 栈2底 计算机软件技术基础 数据结构——栈和队列

14 三、栈的存储结构及算法 ai a2 a1 NULL 2.链栈
链栈是用链表作为栈的存储结构，top为栈顶指针，指示栈顶元素位置，若top=NULL,则表示栈空。链栈一般不会出现上溢，除非内存中已不存在可用空间。 使用单链表，不设头结点 插入和删除仅在表头一端 栈顶top ：指始结点，浮动 空栈用 top=NULL 实现 链栈结点动态分配，空间无限 链栈定义与单链表相同 struct link *top； . a2 top ai a1 NULL 计算机软件技术基础 数据结构——栈和队列

15 四、栈的应用 表达式求值 1）高级语言中的表达式是用人们熟悉的公式形式书写的，编译系统要根据表达式的运算顺序将它翻译成机器指令序列。
2）为解决运算顺序问题，把运算符分成若干等级，称为优先数。 3）为进行表达式的翻译，需设立两个栈，分别存放操作数(NS)和运算符(OS)。 计算机软件技术基础 数据结构——栈和队列

16 四、栈的应用 4）首先在OS中放入表达式结束符“#”，然后自左至右扫描表达式，根据扫描的每一个符号作如下不同处理：
① 若为操作数，将其压入NS栈 ② 若为运算符，需看当前OS的栈顶元素： 若OS栈顶运算符小于或等于当前运算符的优先数，则将当前运算符压入OS栈。 若OS栈顶运算符大于当前运算符的优先数，则从NS栈中弹出两个操作数，设为x、y，再从OS栈中弹出一个运算符，设为θ，由此构成一条机器指令：y θ x → T，并将结果T送入NS栈。 ③ 若当前运算符为“#”，且OS栈顶也为“；”，则表示表达式处理结束，此时NS栈顶的元素即为此表达式的值。 计算机软件技术基础 数据结构——栈和队列

17 四、栈的应用 5)算符优先 + - * / ( ) # > < = 计算机软件技术基础 数据结构——栈和队列

18 int top(seqstack &s) { if(s. top==-1) return(NULL); return(s. data[s
int top(seqstack &s) { if(s.top==-1) return(NULL); return(s.data[s.top]); } 四、栈的应用 6)函数实现 double Exp(){ inistack(OS); inistack(NS);//初始化栈OS和NS push (OS,’#’); //在OS栈中压入结束符 t=0; //t=0表示扫描下一个符号 while (t!=2){ //当处理没有结束时循环 if (t==0) w=getchar(); //读取一个符号 if (w为操作数) push(NS,w); //操作数压NS栈 else{ q=top(OS); //查看OS栈顶元素 if (q<=w){ push (OS,w); t=0; }//不大于时 else{ //处理结束,t= if (q==‘#’&&w==‘#’){ z=pop (NS); t=2; } else{//计算,t=1 x=pop (NS); y=pop (NS); q=pop (OS); x=y q x; push(NS,x); t=1;}}}}} 需编写函数实现 计算机软件技术基础 数据结构——栈和队列

19 四、栈的应用 7)举例 步骤 操作符栈 操作数栈 输入字符 操作 1 # 3*(7-2)# 压入“3”
设表达式为： 3*(7-2)# 步骤 操作符栈 操作数栈 输入字符 操作 # *(7-2)# 压入“3” # *(7-2)# 压入“*” #* (7-2)# 压入“(” #*( )# 压入“7” #*( )# 压入“-” #*( )# 压入“2” #*( )# 弹出“-”压入7-2 #*( )# 弹出“(” #* # 计算3*5 # # 操作符栈空，结束 计算机软件技术基础 数据结构——栈和队列

20 3.4 栈 五、小结 1、理解栈的概念和特点 2、掌握进/出栈的算法 3、了解栈的应用：表达式求值，背包问题 计算机软件技术基础
数据结构——栈和队列

21 3.5 队列 一、队列的定义及运算 二、顺序队列 三、链队列 四、队列的应用 计算机软件技术基础 数据结构——栈和队列

22 3.5 队列 一、队列的定义及基本操作 1、队列的定义
队是限定在表的一端进行插入，在表的另一端进行删除的线性表。允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)。队用移动rear和front指示器进行插入和删除。 队中元素按a1,a2,…,an次序入队和出队。因此队的操作特点是：先进先出（FIFO）；n=0时称为空队。 A1 A2 A3 A4 A5… … An 入队 出队 队头（front） 队尾（rear） 计算机软件技术基础 数据结构——栈和队列

23 一、队列的定义及运算 2、队列的基本操作 初始化队列iniqueue(Q) 将队列Q置成空
判空队列 empty(Q) 若队列Q是空，返回“真”， 否则返回“假” 入队列 enqueue(Q,x)在队列Q尾部插入元素x 出队列 dlqueue(Q,x)若队列Q不空，删除头部元素 取队头 gethead(Q,x)取队列Q头元素， 但不改变队列Q中内容 计算机软件技术基础 数据结构——栈和队列

24 rear=3 front=3 a5 a4 a3 a2 a1 rear=5 front=0 队空 队满 假溢出 循环队列 rear=3 front=5 a1 a2 a3 3.5 队列 二、顺序队列 顺序队用向量作为队的存储结构，可用一维数组Q[1:m]表示。其中m表示队的最大容量。初始状态rear=front=0，队空，入队时rear增1，出队时front增1，当front=rear时队空，当rear=m时无法再继续入队，但此时队中空间并不一定满(只有当rear-front=m时才真正满)，这种现象称为“假溢出”。 为避免假溢出的发生，我们假想把存放队列的数组形成一个头尾相接的环形，称为循环队列。 计算机软件技术基础 数据结构——栈和队列

25 二、顺序队列 1、顺序队列的类型定义 struct SeqQueue { elemtype queue[MAXSIZE+1]；
int front； int rear； }Q; queue[0]不用，实际占用MAXSIZE个单元; 队列空：队头=队尾，即 front=rear 队列满：队尾=MAX，即 rear=MAXSIZE * 注意：假满，若 front≠0时，实际还有空间 计算机软件技术基础 数据结构——栈和队列

26 二、顺序队列 解决方法： 若将整个队列前挪，至队头front=0，花费太大。常用的是：
循环队列：这种队列结构首尾相连,当尾指针 rear=MAXSIZE 时重指向1。(用rear=(rear+1)%MAXSIZE修改rear指针即可) 由于queue[0]不用，因此 当front= (rear+1)%MAXSIZE时队列为满; 当front= rear时队列为空; 不使用queue[0]就是为了能够比较方便地判断队列的空与满 计算机软件技术基础 数据结构——栈和队列

27 二、顺序队列 2、顺序队列的初始化 ⑴ 操作: 建一空队列，队头队尾均置零 ⑵ 接口： 队列指针q (q=&Q) ⑶ 算法描述： q－> front=0; q－> rear=0; ⑷ 函数实现： void iniQueue(SeqQueue &q) { q.front = 0; q.rear = 0; } 计算机软件技术基础 数据结构——栈和队列

28 二、顺序队列 3、循环队列的入队操作 ⑴ 操作:
若队列满，返回false (q->front=(q->rear+1)%MAXSIZE) 队尾指针加一 q->rear = (q->rear+1)%MAXSIZE 将数据放入队尾 q->queue[q->rear]=x 返回true ⑵ 接口： 入口参数：队列指针q，新数据元素x 出口参数: 函数值：成功true;失败false 计算机软件技术基础 数据结构——栈和队列

29 二、顺序队列 (3)算法描述 计算机软件技术基础 数据结构——栈和队列

30 二、顺序队列 (4)函数实现 int enQueue(SeqQueue &q, elemtype x) { if(q.front = (q.rear+1)%MAXSIZE ) return (false); // 队列已满，入队错误 q.rear = (q.rear+1)%MAXSIZE;//更改尾指针 q.queue[q.rear] = x; // 插入数据 return(true); } 计算机软件技术基础 数据结构——栈和队列

31 二、顺序队列 3、循环队列的出队操作 ⑴ 操作: 若队列空，返回NULL (q->front== q->rear )
队头指针加一 q->front=(q->front+1)%MAXSIZE 返回队头数据 q->queue[q->front] ⑵ 接口： 入口参数：队列指针q， 出口参数: 函数返回值：成功：数据元素;失败返回NULL 计算机软件技术基础 数据结构——栈和队列

32 二、顺序队列 (3)算法描述 计算机软件技术基础 数据结构——栈和队列

33 二、顺序队列 (4)函数实现 elemtype dlQueue(SeqQueue &q) { if(q.front == q.rear ) return NULL; // 队列为空，返回NULL q.front = (q.front+1)%MAXSIZE;// 取队头元素 return q.queue[q.front]; } 计算机软件技术基础 数据结构——栈和队列

34 3.5 队列 三、链队列 链队列是用链表作队列的存储结构，当队列的容量无法预先估计时采用。在链队列中设一个头结点，头指针front始终指向头结点，尾指针rear指向队尾元素，当rear=front表时队空。 结点动态分配，不会溢出 链队列结点定义与单链表一样 q data 指针 front rear QS data 指针 front rear QS q 计算机软件技术基础 数据结构——栈和队列

35 三、链队列 1、结点结构定义: struct LNode{ elemtype data; // 数据域
LNode *next; // 指针域 }; 链队列结构定义: struct LinkQueue { LNode *front, *rear; // 队头、队尾指针 计算机软件技术基础 数据结构——栈和队列

36 三、链队列 2、插入 int enQueue(LinkQueue &q, elemtype x){ p = new LNode; //申请结点 if(p) { p->data=x; p->next=NULL; q.rear->next=p; //插入 q.rear=p; //修改尾指针 return(TRUE); //成功 } return(FALSE); //失败 } 计算机软件技术基础 数据结构——栈和队列

37 三、链队列 3、删除 void dlQueue(LinkQueue &q, elemtype &y) { LNode *s; if (q.front==q.rear) return(NULL);//队空 s=q.front->next; //取得队头结点 y=s->data; //保存数据 q.front->next=s->next; //删除s delete s; //释放s if (q.front->next==NULL) //队已空 q.rear=q.front; } 计算机软件技术基础 数据结构——栈和队列

38 3.5 队列 四、队列的应用 任务调度 打印任务 多用户资源竞争问题 主机与外设速度不匹配问题 消息队列 排队模拟 计算机软件技术基础
数据结构——栈和队列

39 3.5 队列 五、小结 1、理解队列的概念和特点 2、理解队的假溢出现象 3、掌握循环队列判断空和满的条件 4、掌握进/出队列的算法
五、小结 1、理解队列的概念和特点 2、理解队的假溢出现象 3、掌握循环队列判断空和满的条件 4、掌握进/出队列的算法 计算机软件技术基础 数据结构——栈和队列