数据结构.ppt

第三章栈队列通常称,栈和队列是限定插入和删除只能在表的“端点”进行的线性表。线性表栈队列 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 章栈和队列 栈定义: 作为一种限定性线性表,是将线性表的插入和删除运算限制为仅在表的一端进行。通常将表中允许进行插入、删除操作的一端称为栈顶 (Top) ,表的另一端被称为栈底 (Bottom) 。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈。栈的删除操作称为出栈或退栈。特点:后进先出( LIFO ) 进栈出栈示意图 a 1… a 2a n栈底栈顶 ADT Stack {数据对象: D = { a i | a i ∈ ElemSet, i=1,2,...,n, n ≥0 } 数据关系: R1 = { <a i-1, a i >| a i-1, a i∈ D, i=2,...,n } 约定 a n端为栈顶, a 1 端为栈底。基本操作: } ADT Stack InitStack( & S) DestroyStack( & S) ClearStack( & S) StackEmpty(s) StackLength(S) GetTop(S, & e) Push( & S, e) Pop( & S, & e) StackTravers(S, visit()) InitStack( & S) 操作结果:构造一个空栈 S。 DestroyStack( & S) 初始条件:栈 S 已存在。操作结果:栈 S 被销毁。 StackEmpty(S) 初始条件:栈 S 已存在。操作结果:若栈 S 为空栈, 则返回 TRUE ,否则 FALE 。 StackLength(S) 初始条件:栈 S 已存在。操作结果:返回 S 的元素个数, 即栈的长度。 GetTop(S, & e) 初始条件:栈 S 已存在且非空。操作结果:用 e 返回 S 的栈顶元素。 a 1a 2a n…… ClearStack( & S) 初始条件:栈 S 已存在。操作结果:将 S 清为空栈。