数据结构 栈和队列教程.ppt

第3章 栈和队列 ;3.1.1 栈的定义 3.1.2 栈的顺序存储结构及其基本运算的实现 3.1.3 栈的链式存储结构及其基本运算的实现 3.1.4 栈的应用; 栈是一种只能在一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶。 栈顶的当前位置是动态的，由一个称为栈顶指针的位置指示器指示。表的另一端称为栈底。 当栈中没有数据元素时，称为空栈。 栈的插入操作通常称为压栈或进栈，栈的删除操作通常称为退栈或出栈。 栈的主要特点是“后进先出”。也称为后进先出表。;a1;后进先出;【例3.3】设一个栈的输入序列为A,B,C,D，则借助一个栈所得到的输出序列不可能是 。 (A) A,B,C,D (B) D,C,B,A (C) A,C,D,B (D) D,A,B,C ;抽象数据类型栈的定义：《教材P65》;3.1.2 栈的顺序存储结构及其基本运算的实现 假设栈的元素个数最大不超过正整数MaxSize，所有元素都具有同一数据类型ElemType，则可用下列方式来定义顺序栈类型SqStack: typedef struct{ ElemType data[MaxSize]； int top； //栈顶指针 } SqStack；; 栈空条件：top==-1 栈满条件：top==MaxSize-1 进栈操作：top++; 再将元素放在top处 退栈操作：从top处取出元素，再将top--;;在顺序栈中实现栈的基本运算算法:;【例3.4】编写一个算法利用顺序栈判断一个字符串是否是对称串。所谓对称串是指从左向右读和从右向左读的序列相同。;;在链栈中的基本运算算法:;【例3.5】编写一个算法判断输入的表达式中的括号是否正确配对。（假设只含有左、右圆括号）;3.1.4 栈的应用;1. 表达式求值;中缀表达式 a + b * ( c - d ) - e / f;假设用exp字符数组存储算术表达式，其对应后缀表达式存放在字符数组postexp中。在将算术表达式转换成后缀表达式的过程中用一个字符数组op作为运算符栈。具体步骤如下: ;a + b ? c ? d / e ? f `\0`;表达式“(56-20)/(4+2)”转换成后缀表达式的过程：;后缀表达式求值;【问题描述】给定一个M×N的迷宫图，求一条从指定入口到出口的路径。;3.2 队列 ; 队列（Queue）简称队，它也是一种运算受限的线性表，其限制为仅允许在表的一端进行插入，在另一端进行删除。把进行插入的一端称做队尾（rear），进行删除的一端称做队首（front）。 向队列中插入新元素称为进队或入队，新元素进队后就成为新的队尾元素；从队列中删除元素称为出队或离队，元素出队后，其后继元素就成为队首元素。 ;队列的基本运算：; 3.2.2 队列的顺序存储结构及其基本运算的实现;1.基于顺序存储的队列的基本运算;基于顺序存储队列的基本运算;;环形队列首尾相连，当队首指针front满足 front==MaxSize-1后，再前进一个位置就自动到0，可以利用求余运算（%）来实现。 队首指针进1：front=(front+1)％MaxSize 队尾指针进1：rear=(rear+1)％MaxSize 指针初始化： front=rear=0 队满条件: (q-rear+1) % MaxSize==q-front 队空条件: q-rear==q-front; 已知front、rear，求count： 　　　 已知front、count，求rear： 　　　 已知rear、count，求front： 　　　;解: 已知队头指针front和队列中元素个数count。;3.2.3 队列的链式存储结构及其基本运算的实现;链队的入队和出队操作示意图;链队存储中的基本运算算法;【例3.8】 采用一个不带头节点只有一个尾节点指针rear的循环单链表存储队列，设计队列的初始化、进队和出队算法。;3.2.4 队列的应用;3.2.5 双端队列; 输出受限的双端队列（即一个端点允许插入和删除，另一个端点只允许插入的双端队列）;本章小结 本章基本学习要点如下: (1) 理解栈和队列的特性以及它们之间的差异，知道在何时使用哪种数据结构。 (2) 重点掌握在顺序栈和链栈上实现栈的基本运算算法，注意栈满和栈空的条件。 (3) 重点掌握在顺序队（环形队）和链队上实现队列的基本运算算法，注意队满和队空的条件。 (4) 灵活运用栈和队列两种数据结构解决一些综合应用问题。