第3章栈和队列 3.1栈 提纲 3.2队列 CONTENTS 作业 上机实验题 1/101
CONTENTS 提纲 1/101
栈的定义顺序栈3.1 栈链栈Java中的栈容器stack栈的综合应用2/101
3.1 栈 链 栈 栈的综合应用 顺 序 栈 栈的定义 Java中的栈容器Stack 2/101
栈的定义3.1.1栈（stack）是一种只能在同一端进行插入或删除操作的线性表。表中允许进行插入、删除操作的一端称为栈顶（top），表的另一端称为栈底（bottom）栈的插入操作通常称为进栈或入栈（push），栈的删除操作通常称为退栈或出栈（pop）。进栈aeaan-1个个出栈栈底栈顶3/101
栈（stack）是一种只能在同一端进行插入或删除操作的线性表。 表中允许进行插入、删除操作的一端称为栈顶（top），表的另一端 称为栈底（bottom）。 栈的插入操作通常称为进栈或入栈（push），栈的删除操作通常称 为退栈或出栈（pop）。 a0 a1 . an-1 栈底 栈顶 进栈 出栈 3/101
4/101
4/101
栈的主要特点：后进先出，即后进栈的元素先出栈。每次进栈的元素都作为新栈顶元素，每次出栈的元素只能是当前栈顶元素。栈也称为后进先出表。5/101
后进先出，即后进栈的元素先出栈。 每次进栈的元素都作为新栈顶元素，每次出栈的元素只能是当前 栈顶元素。 栈也称为后进先出表。 栈的主要特点： 5/101
ADTStack(数据对象：D=[ai0≤i≤n-1，n≥0，元素ai为E类型}数据关系：R=(r]r=[ I ai, ai+iED, i=0, ."", n-2]基本运算：booleanempty（)：判断栈是否为空，若空栈返回真；否则返回假。voidPush(Ee）：进栈操作，将元素e插入到栈中作为栈顶元素。Epop()：出栈操作，返回栈顶元素。Epeek()：取栈顶操作，返回当前的栈顶元素。栈抽象数据类型=线性结构+栈的基本运算6/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
栈元素 基本运算 应用程序 7/101
一个栈的进栈序列是a、b、c、d、e，则栈的不可能的输出序列是（）。示例A.edcbaB.decbaD.abcdeC.dceab方法1：用栈模拟进行判断方法2：利用判断准则判断准则：输入序列为1，2，，n，（pi，P2，…，Pn）是1,2，…，n的一种排列，利用一个栈得到输出序列（pi，P2，…Pn）的充分必要条件是不存在这样的i、j、k满足i<j<h的同时也满足P<Pk<Pi违反了！d c e;a b个个不Pj PkPi8/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
11～n共产生种合法出栈序列。C2nn+1例如，n=5合法45321不合法31254个不合法14235个9/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，若pi=n，则p,的值为（）。A.iB.n-iD.不确定C.n-i+11,2, 3,.,nn输出序列唯一Pi=nP2=n-1P3=n-2Pi+i=n+1即p;=n-i+1Pn=110/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