文档介绍：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