Chapter03_栈和队列_数据结构(C语言版)_严蔚敏_配套ppt课件.pdf

第三章 栈和队列 栈和队列是两种常用的数据类型 栈和队列是限定插入和删除只能在表的 “端点”进行的线性表。 线性表 栈 队列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1≤i≤n+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1≤i≤n 3.1 栈的类型定义 3.2 栈类型的实现 3.3 栈的应用举例 3.4 队列的类型定义 3.5 队列类型的实现 3.1 栈的类型定义 一、栈的定义 限定仅在表尾进行插入或删除操作的线性表。 其中允许进行插入和删除的一端（表尾）称为栈 顶； 另一端（表头）称为栈底。 当表中没有元素时，称为空栈。 假设栈 S=(a1,a2,…,an) 栈底元素 栈顶元素 退栈 进栈 进栈次序： a1, a2 , …, an 栈顶 an 退栈次序： an, an-1 ,…, a2, a1 a2 栈是按照“后进先出”原则处理数据 栈底 a1 元素的，栈也称为“后进先出”表， 简称LIFO表。 二、栈的抽象数据类型的类型定义 ADT Stack { 数据对象： D ＝{ a | a ∈ElemSet, i=1,2,...,n, n ≥0 } i i 数据关系： R1 ＝{ a , a | a , a ∈D, i=2,...,n } i-1 i i-1 i 约定an 端为栈顶，a1 端为栈底。 基本操作： } ADT Stack InitStack(S) DestroyStack(S) StackLength(S) StackEmpty(s) GetTop(S, e) ClearStack(S) Push(S, e) Pop(S, e) StackTravers(S, visit()) InitStack(S) 初始化操作 操作结果：构造一个空栈 S。 DestroyStack(S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。 StackEmpty(S) 判定S是否为空栈 初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈，则返回TRUE ， 否则 FALSE。 StackLength(S) 求栈的长度 初始条件：栈 S 已存在。 操作结果：返回 S 的元素个数，即栈的长度。 GetTop(S, e) 取栈顶元素 初始条件：栈 S 已存在且非空。 操作结果：用 e 返回 S 的栈顶元素。 a a