河池学院：《数据结构》课程电子教案（PPT教学课件）第3章 栈和队列 3.1 栈

第3章栈和队列 3.1栈 提纲 3.2队列 CONTENTS 作业 上机实验题 1/101

CONTENTS 提纲 1/101

3.1 栈 链 栈 栈的综合应用 顺 序 栈 栈的定义 Java中的栈容器Stack 2/101

栈（stack）是一种只能在同一端进行插入或删除操作的线性表。 表中允许进行插入、删除操作的一端称为栈顶（top），表的另一端 称为栈底（bottom）。 栈的插入操作通常称为进栈或入栈（push），栈的删除操作通常称 为退栈或出栈（pop）。 a0 a1 . an-1 栈底 栈顶 进栈 出栈 3/101

4/101

后进先出，即后进栈的元素先出栈。 每次进栈的元素都作为新栈顶元素，每次出栈的元素只能是当前 栈顶元素。 栈也称为后进先出表。 栈的主要特点： 5/101

栈抽象数据类型 = 线性结构 + 栈的基本运算 ADT Stack { 数据对象： D={ai | 0≤i≤n-1，n≥0，元素ai为E类型} 数据关系： R={r} r={ | ai，ai+1∈D， i=0，.，n-2} 基本运算： boolean empty()：判断栈是否为空，若空栈返回真；否则返回假。 void Push(E e)：进栈操作，将元素e插入到栈中作为栈顶元素。 E pop()：出栈操作，返回栈顶元素。 E peek()：取栈顶操作，返回当前的栈顶元素。 } 6/101

栈元素 基本运算 应用程序 7/101

一个栈的进栈序列是a、b、c、d、e，则栈的不可能的输出序 列是（ ）。 A.edcba B.decba C.dceab D.abcde 示例 方法2：利用判断准则 方法1：用栈模拟进行判断 判断准则：输入序列为1，2，.，n，（p1，p2，.，pn）是1， 2，.，n的一种排列，利用一个栈得到输出序列（p1，p2，.， pn）的充分必要条件是不存在这样的i、j、k满足i<j<k的同 时也满足pj<pk<pi。 d c e a b 违反了! pi pj pk 8/101

1～n共产生 n+1 1 C 2n n 种合法出栈序列。 例如，n=5 4 5 3 2 1 合法 3 1 2 5 4 不合法 1 4 2 3 5 不合法 9/101

已知一个栈的进栈序列是1，2，3，.，n，其输出序列是p1， p2，.，pn，若p1=n，则pi的值为（ ）。 A.i B.n-i C.n-i+1 D.不确定 示例 1，2，3，.，n n，. 输出序列唯一 p1=n p2=n-1 p3=n-2 . pn=1 pi+i=n+1即pi=n-i+1 10/101