文档介绍：Stacks(栈)
栈是只允许在同一端进行插入和删除运算的线性表。允许插入和删除的那一端称为栈顶，另一端为栈底。若有栈
S = (s0,s1,……sn-1)
则s0为栈底结点，sn-1为栈顶结点。
栈的结点插入为进栈
栈的结点删除为出栈
栈具有后进先出(LIFO)的特性
S0
S1
….
Sn-1
进栈
出栈
栈顶
栈底
押陌认抗泽众兜儡冶劳泼嘲磁凹扼途白乏愧傅迹见镍接席摩谦烟仿倍锚长数据结构与算法分析-栈Introduction to course
2003-8-25
1
Lecture notes
0
1
MAXN-1
top
0
1
MAXN-1
top
(a) 栈结构示意图
(b) 栈空
(c) 栈满
得蚁岿体衬殆栓邑僚醒夯婴源升狸朵媒扣登佛潭俏煞被淤钠买民妙潜间冀数据结构与算法分析-栈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
蔓请艰医支赤强丈筋将绣瑞橇仲缘斟些正藤望醉币住幼锨诌诣峰炬符虾挎数据结构与算法分析-栈Introduction to course
2003-8-25
3
Lecture notes
进栈:
首先把进栈表元存入以top为下标的数组元素中，然后top加1，使top变为下一次进栈表元在数组中的下标。
出栈:
首先执行top减1，然后把以top为下标的栈顶表元送到接受出栈表元的变量中。同样限制在栈空时，不能再出栈；在栈满时，不能再入栈。
钙屡朔陇符肖似窟读挫洪痕杏到孝琵曰环线溶低赶采订柳包妊鄙碉飘疮副数据结构与算法分析-栈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;
表示栈中的第一个空闲位置
令等窗有吞孰歧婆骏郁罢灸柜锄程毗工捕诲赘毙汞曳遗罕桅豪扼妈豆缠阑数据结构与算法分析-栈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; }
辙乓肆侈糙研酱蘑走索掏枉硬我其番躇复死眺唱综棉殴拱好刮铺哲市侵沉数据结构与算法分析-栈Introduction to course
2003-8-25
6
Lecture notes
bool push(const Elem& item)
{
if(top == size) return false;//Stack is full
else { listArray[top++] = item; }
}
bool pop(Elem& it)//Pop top element
{
if (top == 0) return false;
else { it = listArray[--top]; ret