第3章栈和队列 3.1栈 3.2队列
1 3.1 栈 3.2 队列 第3章 栈和队列
栈和队列的特点 ◆两者的逻辑结构与线性表相同,但是插入 和删除操作受到了限制; ●栈只允许在线性表的一端进行插入和删除 操作,队列则允许在一端插入另一端删除; ●栈按照“后进先出”的规则进行操作,队 列则按照“先进先出”的规则进行
2 栈和队列的特点 ◆ 两者的逻辑结构与线性表相同，但是插入 和删除操作受到了限制； ◆ 栈只允许在线性表的一端进行插入和删除 操作，队列则允许在一端插入另一端删除； ◆ 栈按照“后进先出”的规则进行操作，队 列则按照“先进先出”的规则进行
31栈 3.1.1栈的定义 3.1.2顺序存储结构及其基本运算实现 3.1.3链式存储结构及其基本运算实现 3.1.4栈的应用举例
3 3.1.1 栈的定义 3.1.2 顺序存储结构及其基本运算实现 3.1.3 链式存储结构及其基本运算实现 3.1.4 栈的应用举例 3.1 栈
3.11栈的定义 栈是一种只能在一端进行插入或删除操作的线性表。 表中允许进行插入、删除操作的一端称为栈顶。 当栈中没有数据元素时,称为空栈。 入栈 小出栈 栈顶top 栈底 bottom
4 栈是一种只能在一端进行插入或删除操作的线性表。 表中允许进行插入、删除操作的一端称为栈顶。 当栈中没有数据元素时，称为空栈。 3.1.1 栈的定义 a1 a2 a3 an … 栈顶 top 栈底 bottom 入栈 出栈
练习1 依次输入3个元素A、B、C到栈中,可 得到哪几种不同的输出? 解:共5种 (1)A,B,C(2)A,C,B (3)B,A,C(4)B,C,A (5)C,B,A
5 练 习 1 • 依次输入3个元素A、B、C到栈中，可 得到哪几种不同的输出？ • 解：共5种 (1) A,B,C (2) A,C,B (3) B,A,C (4) B,C,A (5) C,B,A
练习2 设一个栈的输入序列为A、B、C、D,则借助一个 栈所得到的输出序列不可能是 (A)A, B, C, D B)D, C, B, A (C)A, CD, B D)D,A, B,C 答案:D
6 • 设一个栈的输入序列为A、B、C、D,则借助一个 栈所得到的输出序列不可能是 。 (A) A,B,C,D (B) D,C,B,A (C) A,C,D,B (D) D,A,B,C 练 习 2 答案：D
栈的抽象数据类型 ADT Stacki 数据对象:D={a11m,n>0,a1为 ElemType类型} 数据关系:R={<a1,a21Na1;a11∈D,i1,n-1} 基本运算: Initstack(&s)∥{始化栈:构造一个空栈s DestroyStacke(&s)/销毁栈:释放栈S占用的存储空间 StackEmpty(s))/判断栈是否为空 Push(&S,e)进栈:将元素c插入到栈s中作为栈项元素 Pop(&s&e)∥出栈:从栈s中退出栈顶元素,并将其值赋给e GetTop(s,&e)/取栈顶元素:返回当前的栈顶元素,并将其值赋给e JADT Stack
7 栈的抽象数据类型 ADT Stack{ 数据对象：D={ai |1≤i≤n,n≥0，ai为ElemType类型} 数据关系：R={| ai，ai+1 D ，i=1,...,n-1} 基本运算: InitStack(&s) //初始化栈：构造一个空栈s DestroyStack(&s) //销毁栈：释放栈s占用的存储空间 StackEmpty(s) //判断栈是否为空 Push(&S,e) //进栈：将元素e插入到栈s中作为栈顶元素 Pop(&s,&e) //出栈：从栈s中退出栈顶元素，并将其值赋给e GetTop(s,&e) //取栈顶元素：返回当前的栈顶元素，并将其值赋给e }ADT Stack
Push(&s, e) 初始条件:栈S已存在 操作结果:插入e为新的栈顶元素 a1 a 2 ●●●●● a e n 8
8 a1 a2 a … … n Push(&S, e) 初始条件：栈 S 已存在 操作结果：插入e为新的栈顶元素 e
Pop(&s, &e) 初始条件:栈S存在且非空 操作结果:删除S的栈顶元素,赋值给e a1 a 2 ●●●●● n n
9 a1 a2 a … … n-1 Pop(&S,&e) 初始条件：栈 S 存在且非空 操作结果：删除S 的栈顶元素，赋值给e an
GetTop(s, &e) 初始条件:栈S已存在且非空 操作结果:返回S的栈顶元素,赋值给e 1c2 ●●●●●● n
10 a1 a2 a … … n GetTop(S,&e) 初始条件：栈 S 已存在且非空 操作结果：返回 S 的栈顶元素，赋值给e