数据结构_堆栈与队列.ppt

第四章 堆栈和队列 提纲 4.1堆栈的概念及其运算 4.2堆栈的顺序存储结构 4.3堆栈的链式存储结构 4.1堆栈的概念及其运算 堆栈的逻辑结构 堆栈：限定仅在表尾进行插入和删除操作的线性表。 空栈：不含任何数据元素的栈。 允许插入和删除的一端称为栈顶，另一端称为栈底。 4.1堆栈的概念及其运算 4.1堆栈的概念及其运算 4.1堆栈的概念及其运算 4.1堆栈的概念及其运算 4.1堆栈的概念及其运算 4.2堆栈的顺序存储结构 4.2堆栈的顺序存储结构 4.2堆栈的顺序存储结构 4.2堆栈的顺序存储结构 4.2堆栈的顺序存储结构 4.2堆栈的顺序存储结构 4.2堆栈的顺序存储结构 4.2堆栈的顺序存储结构 4.2堆栈的顺序存储结构 4.2堆栈的顺序存储结构 4.2堆栈的顺序存储结构 4.3堆栈的链式存储结构 4.3堆栈的链式存储结构 4.3堆栈的链式存储结构 时间性能：相同，都是常数时间O(1)。 空间性能： 顺序栈：有元素个数的限制和空间浪费的问题。 链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，从而产生了结构性开销。 总之，当栈的使用过程中元素个数变化较大时，用链栈是适宜的，反之，应该采用顺序栈。 * （a1, a2, ……, an） 栈顶 栈底 a b c 入栈 出栈 栈底 栈顶 插入：入栈、进栈、压栈 删除：出栈、弹栈 栈顶 栈顶 栈的示意图 栈的操作特性：后进先出 例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？ 栈底 栈顶 a b 栈顶 c 栈顶 情况1： 出栈序列：c 出栈序列：c、b 出栈序列：c、b、a 例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？ 栈底 栈顶 a b 栈顶 情况2： 出栈序列：b 栈底 a 出栈序列：b 出栈序列：b、c 出栈序列： b、 c、a c 栈顶 栈顶 注意：栈只是对表插入和删除操作的位置进行了限制，并没有限定插入和删除操作进行的时间。 情况2： 例：有三个元素按a、b、c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列有多少种？ 堆栈的操作 Push(S,x) Pop(S) Empty(S) Top(S) Create(S) 如何改造数组实现栈的顺序存储？ 0 1 2 3 4 5 6 7 8 a1 确定用数组的哪一端表示栈底。 附设指针top指示栈顶元素在数组中的位置。 top 出栈：top减1 进栈：top加1 栈空：top= -1 0 1 2 3 4 5 6 7 8 a1 top a2 top a3 top 栈满：top= MAX_SIZE 堆栈是否为空测试算法p70 进栈算法p71 退栈算法 解决方案1： 直接解决：为每个栈开辟一个数组空间。 解决方案2： 顺序栈单向延伸——使用一个数组来存储两个栈 在一个程序中需要同时使用具有相同数据类型的两个栈，如何顺序存储这两个栈？ 会出现什么问题？如何解决？ 两栈共享空间：使用一个数组来存储两个栈，让一个栈的栈底为该数组的始端，另一个栈的栈底为该数组的末端，两个栈从各自的端点向中间延伸。 栈1的底固定在下标为0的一端； 栈2的底固定在下标为MaxSize-1的一端。 top1和top2分别为栈1和栈2的栈顶指针； MaxSize为整个数组空间的大小（图中用S表示）； a1 a2 … ai top1 0 1 2 … … S-1 top2 bj … … b2 b1 栈1底 栈2底 top1= -1 什么时候栈1为空？ a1 a2 … ai top1 0 1 2 … … S-1 top2 bj … … b2 b1 top1 top1= -1 什么时候栈1为空？ a1 a2 … ai top1 0 1 2 … … S-1 top2 bj