|
|
EDA365欢迎您登录！
您需要 登录 才可以下载或查看，没有帐号？注册
x
栈是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶，相应地，表头端称为栈底。不含元素的空表称为空栈。
/ S6 k. N, ?5 W! L假设栈S=（a1,…,ai-1,ai,…,an），则a1为栈底元素，an为栈顶元素。栈中元素按a1，a2，…，an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出的线性表。
; ^; y! d7 {3 i T7 Y; b0 |2 ~栈的基本操作除了在栈顶进行插入或删除外，还有栈的初始化、判空及取栈顶元素等。下面给出栈的抽象数据数据类型的定义：6 y$ L: r, F5 A" {! N
ADT Stack{
1 y5 Y$ s. \) |4 L! Z9 e数据对象：D={ai|ai€ElemSet，i=1，2，…，n，n≥0}
# k2 a# T+ v, K数据关系：R1={<ai-1,ai>|ai-1,ai€D,i=2,…,n}
- a4 k2 F# J0 z- T/ a, W7 y# }* h6 T约定an端为栈顶，a1端为栈底。/ l" b; ? o X$ V$ k" D
基本操作：9 }# m4 ^. f) I8 k9 C
InitStack（&s） U4 l0 d( u& Z
操作结果：构造一个空栈S。5 S+ x) L: X2 k
DestroyStack(&S)1 s4 c" I/ o$ F2 f; O
初始条件：栈S已存在。
" }1 p% [) Q2 n# D操作结果：栈S被销毁。* j# ]1 w5 ?6 v3 Z9 U
ClearStack(&S); |" y/ h, Y* v0 U% G, _2 t
初始条件：栈S已存在。9 F2 w* l' x+ L; t% v7 Y1 N z
操作结果：栈S被清为空栈。& X6 Z, [5 U! s5 R3 S, e* C4 Y
StackEmpty(S)
" V0 X( ` T4 E7 X. ] Y) x4 y初始条件：栈S已存在。
N# U* y9 H0 K, V" C2 |操作结果：若栈为空栈，则返回TURE,否则FALSE。
% ]) X9 _* u+ Q) p& [+ l# M. LStackLength(S) F# m* M: O, }: Y9 N
初始条件：栈S已存在。" q4 [4 |7 ]1 K
操作结果：返回S的元素个数，即栈的长度。
; b/ k9 e7 o1 h6 u; Z0 T; CGetTop(S,&e)& q: r/ M- R: V: |$ h8 g
初始条件：栈S已存在且非空。
0 d: ]$ q) h: d; h操作结果：用e返回S的栈顶元素。( u# g3 w: B' [( i, P8 ]; N, v7 R
Push(S,&e)( I" b* @+ s/ L
初始条件：栈S已存在。1 `: f4 X0 F2 q8 t+ s7 B
操作结果：插入新的元素e为新的栈顶元素。# ?. W/ |$ m6 j _
Pop(&S,&e)
) X" h, N' K/ ~1 u+ w( k0 {# F. N) Q9 B初始条件：栈S已存在且非空。
5 T6 j: h; y7 ~" {3 C& w9 o/ I操作结果：删除S的栈顶元素，并用e返回其值。2 a, b K; T% S2 J E) E( l0 W
StackTraverse(S,visit())6 Q) \5 y3 D& H3 t1 w% j8 v
初始条件：栈S已存在且非空。) y6 M2 a; n1 D7 |5 ?. B a' i1 i
操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit()。一旦visit()失败，则操作失效。
7 X. {# g+ D1 ~5 j. Q}ADT Stack |
|
/1 
发表于 2016-8-11 14:05
收藏
淘帖
支持！
反对！