第三章栈和队列
第三章 栈和队列
第一节栈 311栈的类型定义 栈( Stack)是限定只能在表的一端进行插入和 删除操作的线性表。 在表中,允许插入和删除的一端称作“栈顶 (top)”, 不允许插入和删除的另一端称作"栈底 (bottom) 入栈 出栈 栈元素 栈顶元素
第一节 栈 3.1.1 栈的类型定义 • 栈（Stack）是限定只能在表的一端进行插入和 删除操作的线性表。 • 在表中，允许插入和删除的一端称作“栈顶 (top)”， • 不允许插入和删除的另一端称作"栈底 (bottom)"
栈必须按“后进先出”的规则进行操作 栈只允许在表尾一端进行插入和删除 ·通常称往栈顶插入元素的操作为“入栈” 称删除栈顶元素的操作为“出栈”。 因为后入栈的元素先于先入栈的元素出栈, 故被称为是一种后进先出"的结构,因此 又称LFo( Last in first out)表
• 栈必须按“后进先出”的规则进行操作 • 栈只允许在表尾一端进行插入和删除 • 通常称往栈顶插入元素的操作为“入栈” • 称删除栈顶元素的操作为“出栈”。 • 因为后入栈的元素先于先入栈的元素出栈， 故被称为是一种"后进先出"的结构，因此 又称LIFO（Last In First Out）表
类型定义 ADT Stack i 数据对象:D={aa1∈ Elem Set,i=12,,n,n20} 数据关系:R1={<aa1斗a1a1∈D,=2,,n} 约定a端为栈顶,a1端为栈底。 基本操作: Initstack(&s) 操作结果:构造一个空栈S。 Destroy Stack&s 初始条件:栈S已存在。 操作结果:栈S被销毁
类型定义 • ADT Stack { 数据对象：D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{ < ai-1 , ai >| ai-1 , ai ∈D, i=2,...,n } 约定an端为栈顶， a1端为栈底。 基本操作： InitStack(&S) 操作结果：构造一个空栈 S。 DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁
ClearStack(&s) 初始条件:栈S已存在。 操作结果:将S清为空栈。 StackEmpty(s) 初始条件:栈S已存在。 操作结果:若栈S为空栈,则返回TRUE, 否则返回 FALSE。 StackLength(s) 初始条件:栈S已存在。 操作结果:返回栈S中元素个数,即栈 的长度。 GetTop(s, &e) 初始条件:栈S已存在且非空 操作结果:用e返回S的栈顶元素
• ClearStack(&S) 初始条件：栈 S 已存在。 操作结果：将 S 清为空栈。 • StackEmpty(S) 初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈，则返回TRUE， 否则返回FALSE。 • StackLength(S) 初始条件：栈 S 已存在。 操作结果：返回栈 S 中元素个数，即栈 的长度。 • GetTop(S, &e) 初始条件：栈 S 已存在且非空。 操作结果：用 e 返回S的栈顶元素