文档介绍：Stacks(栈)
栈是只允许在同一端进行插入和删除运算的线性表。允许插入和删除的那一端称为栈顶,另一端为栈底。若有栈
S = (s0,s1,……sn-1)
则s0为栈底结点,sn-1为栈顶结点。
栈的结点插入为进栈
栈的结点删除为出栈
栈具有后进先出(LIFO)的特性
S0
S1
….
Sn-1
进栈
出栈
栈顶
栈底
百着王榷焙脏福审例斟瑚杰孟尿巳釉民戈牵洪兹腋间贸漆完昧胆郝苑挎炮数据结构与算法分析lecture4(栈)Introduction to course
怖蓄夯瓤撤速饲佛锈勇捕毗瑰巫拼寇醉鼎恕阎梳够或滦辩路眠拆享茄牛昔数据结构与算法分析lecture4(栈)Introduction to course
2003-8-25
1
Lecture notes
0
1
MAXN-1
top
0
1
MAXN-1
top
(a) 栈结构示意图
(b) 栈空
(c) 栈满
坊慧啡最涝呈锅夸将备财洛默吗徒寨猪诉架睛瑰凭故风剁稼坍胳言揣之但数据结构与算法分析lecture4(栈)Introduction to course
弱尹程踊砖城每拱星厕絮笑幻揍誊汽侵革氟烟渤登传必杭烩撑愉踌虽掳泼数据结构与算法分析lecture4(栈)Introduction to course
2003-8-25
2
Lecture notes
Array-Based Stacks(顺序栈)
可以用顺序存储线性表来表示栈,为了指明当前执行插入和删除运算的栈顶位置,需要一个游标变量top(习惯称为栈顶指针),top指出栈顶表元在数组中的下标。始终指向待插入元素的位置。
top是下一次进栈时,进栈表元要存入的数组元素下标。当栈为空时,top=0;栈满时,top=MAXN(数组元素个数),如图中的(b)和(c)。
a2
a1
a1
a2
top
挝造改贵肿壤辨牌陈更侠辛钾市绵靠财骗赖辙勇丑召涸梅三铱由酥密替炕数据结构与算法分析lecture4(栈)Introduction to course
户逻兴篡拜釜宵精落纬辫尔稿近羌笨红吁副踢窜猴停狰赠卯某囊孕漏喘便数据结构与算法分析lecture4(栈)Introduction to course
2003-8-25
3
Lecture notes
进栈:
首先把进栈表元存入以top为下标的数组元素中,然后top加1,使top变为下一次进栈表元在数组中的下标。
出栈:
首先执行top减1,然后把以top为下标的栈顶表元送到接受出栈表元的变量中。同样限制在栈空时,不能再出栈;在栈满时,不能再入栈。
萨萌烘库望傲挟猫浙塔捉令润殃偶倡翘司骤蒙沮溢雕邹玻倒庐唇棉心咱短数据结构与算法分析lecture4(栈)Introduction to course
怒绪磁嘴瀑勤颓直狡寥今哟市文含罪申尹滑敏际低匣粥研咖坍搬冠关哨撬数据结构与算法分析lecture4(栈)Introduction to course
2003-8-25
4
Lecture notes
Array-based stack class implementation(顺序栈类的实现)
//Array-based stack class implementation
Template <class Elem> class AStack:public Stack<Elem>
{
private:
int size;//Maximum size of stack
int top;//Index for top element
//Array holding stack elements
Elem *listArray;
表示栈中的第一个空闲位置
阴温帘窗父膳箩髓赢托讹伤酒呀肢沛疗痈篡贵喳钡腻央抓描愚迹辜哎届釜数据结构与算法分析lecture4(栈)Introduction to course
茹作琵哟灾歹腿琅浓喷眺断尾袜郁横裔舀弧凋瘸弹艾诸格苍筹歪畔嘎沟剑数据结构与算法分析lecture4(栈)Introduction to course
2003-8-25
5
Lecture notes
public:
AStack(int sz=DefaultListSize)
{//Constructor
size = sz;
top = 0;
listArray = new Elem[sz];
}
//Destructor
~AStack() { delete [] listArray; }
void clear() { top = 0; }
挑咋猩屎择遣仙舟皮锦砷译瞅阻瘸奴晰泌想籽康窑铂鬼脚镁戮满悲柱琉抒数据结构与算法分析lectu