《栈和队列》PPT课件.ppt

数据结构（C+版）第2版 清华大学出版社 第 3 章 栈和队列 本章的基本内容是： 两种特殊的线性表栈和队列 从数据结构角度看，栈和队列是操作受限的线 性表，他们的逻辑结构相同。 从抽象数据类型角度看，栈和队列是两种重要 的抽象数据类型。 数据结构（C+版）第2版 清华大学出版社 3.1 栈 栈的逻辑结构 （a1, a2, , an） p栈：限定仅在表的一端进行插入和删除操作的线性表 。 p允许插入和删除的一端称为栈顶，另一端称为栈底。 p空栈：不含任何数据元素的栈。 栈顶栈底 数据结构（C+版）第2版 清华大学出版社 a1 a2 a3 入栈 出栈 栈底 栈顶 插入：入栈、进栈、压栈 删除：出栈、弹栈 栈顶 栈顶 3.1 栈 栈的逻辑结构 数据结构（C+版）第2版 清华大学出版社 栈的操作特性：后进先出 a1 a2 a3 入栈 出栈 栈底 栈顶 插入：入栈、进栈、压栈 删除：出栈、弹栈 栈顶 3.1 栈 栈的逻辑结构 数据结构（C+版）第2版 清华大学出版社 例：有三个元素按a、b、c的次序依次进栈，且每个 元素只允许进一次栈，则可能的出栈序列有多少种？ 栈底 栈顶 a b 栈顶 c 栈顶 情况1： 栈的逻辑结构 3.1 栈 数据结构（C+版）第2版 清华大学出版社 栈底 栈顶 a b 栈顶 c 栈顶 出栈序列：c 出栈序列：c、b 出栈序列：c、b、a 例：有三个元素按a、b、c的次序依次进栈，且每个 元素只允许进一次栈，则可能的出栈序列有多少种？ 栈的逻辑结构 情况1： 3.1 栈 数据结构（C+版）第2版 清华大学出版社 栈底 栈顶 a b 栈顶 出栈序列：b 情况2： 例：有三个元素按a、b、c的次序依次进栈，且每个 元素只允许进一次栈，则可能的出栈序列有多少种？ 栈的逻辑结构 3.1 栈 数据结构（C+版）第2版 清华大学出版社 栈底 a 出栈序列：b 出栈序列：b、c 出栈序列： b、 c、a c 栈顶 栈顶 例：有三个元素按a、b、c的次序依次进栈，且每个 元素只允许进一次栈，则可能的出栈序列有多少种？ 栈的逻辑结构 情况2： 3.1 栈 数据结构（C+版）第2版 清华大学出版社 出栈序列： b、 a、c 注意：栈只是对表插入和删除操作的位置进行了限 制，并没有限定插入和删除操作进行的时间。 例：有三个元素按a、b、c的次序依次进栈，且每个 元素只允许进一次栈，则可能的出栈序列有多少种？ 栈的逻辑结构 情况3： 3.1 栈 出栈序列： a、 b、c 情况4： 出栈序列： a、 c、b 情况5： 数据结构（C+版）第2版 清华大学出版社 栈的抽象数据类型定义 ADT Stack Data 栈中元素具有相同类型及后进先出特性， 相邻元素具有前驱和后继关系 Operation InitStack 前置条件：栈不存在 输入：无 功能：栈的初始化 输出：无 后置条件：构造一个空栈 3.1 栈 数据结构（C+版）第2版 清华大学出版社 DestroyStack 前置条件：栈已存在 输入：无 功能：销毁栈 输出：无 后置条件：释放栈所占用的存储空间 Push 前置条件：栈已存在 输入：元素值x 功能：在栈顶插入一个元素x 输出：如果插入不成功，抛出异常 后置条件：如果插入成功，栈顶增加了一个元素 栈的抽象数据类型定义 3.1 栈 数据结构（C+版）第2版 清华大学出版社 Pop 前置条件：栈已存在 输入：无 功能：删除栈顶元素 输出：如果删除成功，返回被删元素值，否则，抛出异常 后置条件：如果删除成功，栈减少了一个元素 GetTop 前置条件：栈已存在 输入：无 功能：读取当前的栈顶元素 输出：若栈不空，返回当前的栈顶元素值 后置条件：栈不变 栈的抽象数据类型定义 3.1 栈 数据结构（C+版）第2版 清华大学出版社 Empty 前置条件：栈已存在 输入：无 功能：判断栈是否为空 输出：如果栈为空，返回1，否则，返回0 后置条件：栈不变 endADT 栈的抽象数据类型定义 3.1 栈 数据结构（C+版）第2版 清华大学出版社 栈的顺序存储结构及实现 顺序栈栈的顺序存储结构 如何改造数组实现栈的顺序存储？ 0 1 2 3 4 5 6 7 8 a1 确定用数组的哪一端表示栈底。 附设指针top指示栈顶元素在数组中的位置。 top 3.1 栈 数据结构（C+版）第2版 清华大学出版社 出栈：top减1 进栈：top加1栈空：top= -1 0 1 2 3 4 5 6 7 8 a1 top a2 top a3 top 栈满：top= MAX_SIZE-1 栈的顺序存储结构及实现 3.1 栈 数据结构（C+版）第2版 清华大学出版社 顺序栈类的声明 const int StackSize=100; template class seqStack public: seqStack ( ) ; seqStack ( ); void Push ( DataType x ); DataType Pop ( ); DataType GetTop ( ); bool Empty ( ); private: DataType dataStackSize; int top; 3.1 栈 数据结构（C+版）第2版 清华大学出版社 顺序栈的实现入栈 template void seqStack :Push ( DataType x) if (top = StackSize -1) throw “溢出”; top+; datatop = x; 操作接口： void Push( DataType x ); 时间复杂度？ data+top = x 3.1 栈 数据结构（C+版）第2版 清华大学出版社 顺序栈的实现出栈 template DataType seqStack : Pop ( ) if (top = -1) throw “溢出”; x = datatop-; return x; 操作接口： DataType Pop( ); 时间复杂度？ 3.1 栈 数据结构（C+版）第2版 清华大学出版社 两栈共享空间 解决方案1： 直接解决：为每个栈开辟一个数组空间。 解决方案2： 顺序栈单向延伸使用一个数组来存储两个栈 在一个程序中需要同时使用具有相同数据类型的 两个栈，如何顺序存储这两个栈？ 会出现什么问题？如何解决？ 3.1 栈 数据结构（C+版）第2版 清华大学出版社 两栈共享空间：使用一个数组来存储两个栈，让一个 栈的栈底为该数组的始端，另一个栈的栈底为该数组 的末端，两个栈从各自的端点向中间延伸。 两栈共享空间 3.1 栈 数据结构（C+版）第2版 清华大学出版社 栈1的底固定在下标为0的一端； 栈2的底固定在下标为StackSize-1的一端。 top1和top2分别为栈1和栈2的栈顶指针； Stack_Size为整个数组空间的大小（图中用S表示）； a1 a2 ai top1 0 1 2 S-1 两栈共享空间 top2 bj b2 b1 栈1底 栈2底 3.1 栈 数据结构（C+版）第2版 清华大学出版社 top1= -1 什么时候栈1为空？ a1 a2 ai top1 0 1 2 S-1 两栈共享空间 top2 bj b2 b1 top1 3.1 栈 数据结构（C+版）第2版 清华大学出版社 top1= -1 什么时候栈1为空？ a1 a2 ai top1 0 1 2 S-1 两栈共享空间 top2 bj b2 b1 什么时候栈2为空？ top2 top2= Stack_Size 3.1 栈 数据结构（C+版）第2版 清华大学出版社 top1= -1 什么时候栈1为空？ a1 a2 ai top1 0 1 2 S-1 两栈共享空间 top2 bj b2 b1 什么时候栈2为空？ top2= Stack_Size 什么时候栈满？top2= top1+1 3.1 栈 数据结构（C+版）第2版 清华大学出版社 const int StackSize=100; template class BothStack public: BothStack( ); BothStack( ); void Push(int i, DataType x); DataType Pop(int i); DataType GetTop(int i); bool Empty(int i); private: DataType dataStackSize; int top1, top2; ; 两栈共享空间类的声明 3.1 栈 数据结构（C+版）第2版 清华大学出版社 1. 如果栈满，则抛出上溢异常； 2. 判断是插在栈1还是栈2； 2.1 若在栈1插入，则 2.1.1 top1加1; 2.1.2 在top1处填入x； 2.2 若在栈2插入，则 2.2.1 top2减1; 2.2.2 在top2处填入x； 两栈共享空间的实现插入 操作接口：void Push(int i, DataType x) ; 3.1 栈 数据结构（C+版）第2版 清华大学出版社 1. 若是在栈1删除，则 1.1 若栈1为空栈，抛出下溢异常； 1.2 删除并返回栈1的栈顶元素； 2. 若是在栈2删除，则 2.1 若栈2为空栈，抛出下溢异常； 2.2 删除并返回栈2的栈顶元素； 两栈共享空间的实现删除 操作接口：DataType Pop(int i) ; 3.1 栈 数据结构（C+版）第2版 清华大学出版社 栈的链接存储结构及实现 链栈：栈的链接存储结构 first a1a2an ai 链栈需要加头结点吗？ 如何改造链表实现栈的链接存储？ 将哪一端作为栈顶？ 将链头作为栈顶，方便操作 。 链栈不需要附设头结点 。 3.1 栈 数据结构（C+版）第2版 清华大学出版社 栈的链接存储结构及实现 栈顶 栈底 链栈：栈的链接存储结构 top an an-1 a1 first a1a2an ai 两种示意图在内存中对 应同一种状态，启示？ top a1an-1an 栈顶栈底 3.1 栈 数据结构（C+版）第2版 清华大学出版社 链 栈 的 类 声 明 template class LinkStack public: LinkStack( ); LinkStack( ); void Push(DataType x); DataType Pop( ); DataType GetTop( ); bool Empty( ); private: Node *top; 3.1 栈 数据结构（C+版）第2版 清华大学出版社 template void LinkStack :Push(DataType x) s = new Node; s-data = x; s-next = top; top = s; topan an-1 a1 链栈的实现插入 x stop 操作接口： void Push(DataType x); 为什么没有判断栈满？ 3.1 栈 数据结构（C+版）第2版 清华大学出版社 template DataType LinkStack :Pop( ) if (top = NULL) throw “下溢“; x = top-data; p = top; top = top-next; delete p; return x; 链栈的实现删除 操作接口： DataType Pop( ); topan an-1 a1 top p top+可以吗？ 3.1 栈 数据结构（C+版）第2版 清华大学出版社 顺序栈和链栈的比较 时间性能：相同，都是常数时间O(1)。 空间性能： 顺序栈：有元素个数的限制和空间浪费的问题。 链栈：没有栈满的问题，只有当内存没有可用空 间时才会出现栈满，但是每个元素都需要一个指针 域，从而产生了结构性开销。 总之，当栈的使用过程中元素个数变化较大时，用 链栈是适宜的，反之，应该采用顺序栈。 3.1 栈 数据结构（C+版）第2版 清华大学出版社 栈的应用举例数制转换 十进制转其它进制（2，8，16） 十进制整数转换成其它进制的整数采用的方法是： 除n取余，逆排 如：(23)10 = (10111)2 23 11 21 2 5 1 2 2 1 2 1 0 2 0 1 数据结构（C+版）第2版 清华大学出版社 SeqStack stack; int a = 23, b = 2; while(a != 0) stack.Push(a%b); a = a / b; while(stack.IsEmpty() = 0) coutfront a3a4 front a5 rear a6 出队 3.2 队列 数据结构（C+版）第2版 清华大学出版社 循 环 队 列 类 的 声 明 const int QueueSize=100; template class CirQueue public: CirQueue( )； CirQueue( )； void EnQueue(DataType x); DataType DeQueue( ); DataType GetQueue( ); bool Empty( )； private: DataType dataQueueSize; int front, rear; ; 3.2 队列 数据结构（C+版）第2版 清华大学出版社 template void CirQueue :EnQueue(DataType x) if (rear+1) % QueueSize = front) throw “上溢“; rear =(rear+1) % QueueSize; datarear = x; 循环队列的实现入队 0 1 2 3 4 入队出队 a3a4 rearfront a5 rear 3.2 队列 数据结构（C+版）第2版 清华大学出版社 0 1 2 3 4 入队 a4a5a6 出队 template DataType CirQueue :DeQueue( ) if (rear = front) throw “下溢“; front = (front + 1) % QueueSize; return datafront; 循环队列的实现出队 frontrearfront a3 3.2 队列 数据结构（C+版）第2版 清华大学出版社 template DataType CirQueue :GetQueue( ) if (rear = front) throw “下溢“; i = (front + 1) % QueueSize; return datai; 循环队列的实现读队头元素 0 1 2 3 4 入队 a4a5a6 出队 frontrear a3 i 3.2 队列 数据结构（C+版）第2版 清华大学出版社 队列的链接存储结构及实现 链队列：队列的链接存储结构 队头指针即为链表的头指针 first a1a2 an 如何改造单链表实现队列的链接存储？ rear front 3.2 队列 数据结构（C+版）第2版 清华大学出版社 队列的链接存储结构及实现 非空链队列 front a1a2 an rear 空链队列 front rear 3.2 队列 数据结构（C+版）第2版 清华大学出版社 链 队 列 类 的 声 明 template class LinkQueue public: LinkQueue( ); LinkQueue( ); void EnQueue(DataType x); DataType DeQueue( ); DataType GetQueue( )； bool Empty( )； private: Node *front, *rear; ; 3.2 队列 数据结构（C+版）第2版 清华大学出版社 操作接口： LinkQueue( ); 算法描述： template LinkQueue :LinkQueue( ) front = new Node; front-next = NULL; rear = front; 链队列的实现构造函数 front rear 3.2 队列 数据结构（C+版）第2版 清华大学出版社 x s 链队列的实现入队 操作接口： void EnQueue(DataType x); front a1an rear rear front x s rearrear 算法描述： s-next=NULL; rear-next=s; rear=s; 如何没有头结点会怎样？ 3.2 队列 数据结构（C+版）第2版 清华大学出版社 x s 链队列的实现入队 操作接口： void EnQueue(DataType x); front a2an rear rear 算法描述： s-next=NULL; rear-next=s; rear=s; 如何没有头结点会怎样？ a1 3.2 队列 数据结构（C+版）第2版 清华大学出版社 链队列的实现入队 操作接口： void EnQueue(DataType x); front=rear=NULL x s rear 算法描述： s-next=NULL; rear=s; front=s; 如何没有头结点会怎样？ front 算法描述： s-next=NULL; rear-next=s; rear=s; 3.2 队列 数据结构（C+版）第2版 清华大学出版社 链队列的实现入队 template void LinkQueue :EnQueue(DataType x) s = new Node; s-data = x; s-next = NULL; rear-next = s; rear = s; 3.2 队列 数据结构（C+版）第2版 清华大学出版社 链队列的实现出队 front a1a2 an rear p 算法描述： p=front-next; front-next=p-next; 3.2 队列 数据结构（C+版）第2版 清华大学出版社 链队列的实现出队 front a1a2 an rear p 考虑边界情况：队列中只有一个元素？ front a1 p rear rear 算法描述： if (p-next = NULL) rear = front; 如何判断边界情况？ 3.2 队列 数据结构（C+版）第2版 清华大学出版社 template DataType LinkQueue :DeQueue( ) if (rear = front) throw “下溢“; p = front-next; x = p-data; front-next = p-next; if (p-next = NULL) rear = front; delete p; return x; 链队列的实现出队 3.2 队列 数据结构（C+版）第2版 清华大学出版社 循环队列和链队列的比较 时间性能: 循环队列和链队列的基本操作都需要常数时间O (1)。 空间性能: 循环队列：必须预先确定一个固定的长度，所以有 存储元素个数的限制和空间浪费的问题。 链队列：没有队列满的问题，只有当内存没有可用 空间时才会出现队列满，但是每个元素都需要一个 指针域，从而产生了结构性开销。 3.2 队列 数据结构（C+版）第2版 清华大学出版社 本章总结 特殊线性表 栈 队 列 栈的定义 操作特性 ADT定义 队列定义 操作特性 ADT定义 顺 序 栈 链 栈 循 环 队 列 链 队 列 逻辑结构存储结构逻辑结构存储结构 比 较 比较 比较 基本操作的实现 时间性能 基本操作的实现 时间性能 数据结构（C+版）第2版 清华大学出版社 栈的应用：表达式求解 一个表达式由操作数（亦称运算对象）、操 作符（亦称运算符）和分界符组成。 算术表达式有三种表示： u中缀(infix)表示 ，如 A+B ； u前缀(prefix)表示 ，如 +AB ； u后缀(postfix)表示 ，如 AB+ ； 数据结构（C+版）第2版 清华大学出版社 中缀表达式 a * b + ( c d/e ) *f 后缀表达式 a b * c de/ - f *+ 前缀表达式 + *ab *-c/def 表达式事例 结论： 1）操作数之间的相对次序不变；2）运算符的相对次序不同；3）后缀表达式的运算规则为： 运算符在式中出现的顺序恰为 表达式的运算顺序； 每个运算符和在它们之前且 紧靠它的两个操作数构成一个最 小的表达式 4）前缀表达式的运算规则为： 连续出现的两个操作数和在它们 之前且紧靠它们的运算符构成一个 最小的表达式 数据结构（C+版）第2版 清华大学出版社 1.后缀表达式（逆波兰式）求值 n从左向右顺序地扫描表达式，并用一个栈暂 存扫描到的操作数或计算结果。 n在后缀表达式的计算顺序中已隐含了加括号 的优先次序，括号在后缀表达式中不出现。 计算例 a b * c de/ - f * + t1 t3 t4 t2 t5 数据结构（C+版）第2版 清华大学出版社 后缀表达式用什么来存储? 字符栈、字符数组、字符串 其实这三者本质上都是一样的，都可以实现 数据结构（C+版）第2版 清华大学出版社 a b * c d e / - f * + T1 = T2= T3 = T4= T5= T1 T2 T3 T4 操作数或中间结果栈S T5 数据结构（C+版）第2版 清华大学出版社 1. 初始化栈S； 2. 从左到右依次扫描表达式的每个字符，执行下述 操作； 2.1 若当前字符是运算对象，则入栈S，处理下 个字符 2.2 若当前字符是运算符，则从栈S出栈两个运 算对象，执行运算并将结果入栈S，处理下一个字符； 3