|
|
EDA365欢迎您登录！
您需要 登录 才可以下载或查看，没有帐号？注册
x
栈是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶，相应地，表头端称为栈底。不含元素的空表称为空栈。3 e! O: { `" ?( H; I
假设栈S=（a1,…,ai-1,ai,…,an），则a1为栈底元素，an为栈顶元素。栈中元素按a1，a2，…，an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈又称为后进先出的线性表。
. W- w3 E8 J6 m* E栈的基本操作除了在栈顶进行插入或删除外，还有栈的初始化、判空及取栈顶元素等。下面给出栈的抽象数据数据类型的定义：; j2 X* C$ G, i0 }8 x) y
ADT Stack{3 c( D7 t6 i1 u2 _: g& |$ [2 K0 X
数据对象：D={ai|ai€ElemSet，i=1，2，…，n，n≥0}" H: m* J9 Q! r! Q/ X9 L( e
数据关系：R1={<ai-1,ai>|ai-1,ai€D,i=2,…,n}
" o2 j1 U/ ?% M, j约定an端为栈顶，a1端为栈底。2 I9 x. J# A2 u$ d
基本操作：! e# a7 ? q$ R2 x) }% E/ z( Y
InitStack（&s）
1 o9 `+ {1 m6 f9 ~操作结果：构造一个空栈S。
3 c, ~& \3 [" U( i6 _9 |' Y) QDestroyStack(&S)
: s9 T0 A9 h3 n. i! b) W初始条件：栈S已存在。4 e$ z- P6 l5 q6 w
操作结果：栈S被销毁。
* f& T b7 Z( Y' l; A1 I* dClearStack(&S)7 m# X/ W5 p: |; M
初始条件：栈S已存在。& t1 N( K: P5 i! ]8 H* q* ]
操作结果：栈S被清为空栈。6 \7 D1 P% \" r5 `
StackEmpty(S)
# Q1 ^6 t1 p7 |3 f初始条件：栈S已存在。7 `; m6 p0 Q. H. C+ x. R( e& D
操作结果：若栈为空栈，则返回TURE,否则FALSE。$ e. L4 |6 e w/ E# F$ G- U3 w% h
StackLength(S)
6 W/ w; u) d7 d) E3 b; ~% G# r初始条件：栈S已存在。
n8 k$ M- z0 E操作结果：返回S的元素个数，即栈的长度。+ ]* {9 g. |- e6 R
GetTop(S,&e)$ S7 q/ i) _0 k# K1 }
初始条件：栈S已存在且非空。
! z! y, E7 O8 u4 g$ h8 ^! t操作结果：用e返回S的栈顶元素。
# v$ G: ?7 }/ Z, N3 gPush(S,&e)
4 V# ]& }3 J( p' Q4 r4 z初始条件：栈S已存在。
- ~5 R2 U3 \4 j1 s4 |0 u( x. _操作结果：插入新的元素e为新的栈顶元素。; \1 `# g9 s9 X6 O# {
Pop(&S,&e)) {) ^7 r" R0 Z p
初始条件：栈S已存在且非空。
4 h/ h- T, W# f5 O; F, Z操作结果：删除S的栈顶元素，并用e返回其值。
y1 C# ^0 u# { V" ]; a" MStackTraverse(S,visit())- T9 L6 _9 i0 z: k+ R& _2 W
初始条件：栈S已存在且非空。3 \& g+ y7 Y, y$ H: R4 `+ ] c
操作结果：从栈底到栈顶依次对S的每个数据元素调用函数visit()。一旦visit()失败，则操作失效。
! w7 Z3 S j1 ~! B" S' c}ADT Stack |
|
/1 
发表于 2016-8-11 14:05
收藏
淘帖
支持！
反对！