第7章 图 - 湖南大学软件学院.ppt

第三章栈和队列
栈的定义及基本运算
栈(Stack)是限制在表的一端进行插入和删除运算的线性表,通常称插入、删除的这一端为栈顶(Top),另一端为栈底(Bottom)。当表中没有元素时称为空栈。

假设栈S=(a0,a1,a2,…an),则a0称为栈底元素,an为栈顶元素。栈中元素按a0,a1,a2,…an的次序进栈,退栈的第一个元素应为栈顶元素。换句话说,栈的修改是按后进先出的原则进行的。因此,栈称为后进先出表(LIFO)。
a0
a1
a2
a3
an-1
· · ·
退栈(删)
进栈(插)
顺序栈
由于栈是运算受限的线性表,因此线性表的存储结构对栈也适应。
栈的顺序存储结构简称为顺序栈,它是运算受限的线性表。因此,可用数组来实现顺序栈。因为栈底位置是固定不变的,所以可以将栈底位置设置在数组的两端的任何一个端点;栈顶位置是随着进栈和退栈操作而变化的,故需用一个整型变量top
例、一叠书或一叠盘子。
a n
a n-1
a2
a1
……
栈顶
栈底
top
6 5 4 3 2 1 0
top
-1
6 5 4 3 2 1 0
顺序栈类的实现
template <class Elem> class AStack:public Stack<Elem>{
private:
int size;
int top;
Elem *listArray;
public:
AStack(int sz=DefaultListSize)
{size=sz; top=0; listArray=new Elem[size];}
~AStack() {delete [] listArray;}
void clear() { top=0;}
顺序栈类的实现
bool push(const Elem& item){
if(top==size) return false;
else{listArray[top++]=item; return true;}
}
bool pop(Elem &it){
if(top==0) return false;
else {it=listArray[--top]; return true;}
}
bool topValue(Elem &it) const{
if(top==0) return false;
else {it=listArray[top-1]; return true;}
}
顺序栈类的实现
int length() const {return top;}
};
链栈
栈的链式存储结构称为链栈,它是运算是受限的单链表,,故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。