文档介绍：The Abstract Data Type
Derived Classes and Inheritance
Formula-Based Representation
Linked Representation
Applications
Chapter5 堆栈(Stacks)
8/4/2017
1
堆栈的实现
堆栈的应用
本章重点
8/4/2017
2
定义堆栈是一个线性表,其插入(也称为添加)和删除操作都在表的同一端进行。
允许插入和删除的一端被称为栈顶(top),另一端被称为栈底(bot tom)。
堆栈是一个后进先出(last-in-first-out, LIFO)的数据结构。
堆栈(Stacks)
8/4/2017
3
堆栈
8/4/2017
4
堆栈ADT
8/4/2017
5
公式化描述(Formula-Based Representation)
效率、改进
链接描述(Linked) Representation
效率比较
堆栈
8/4/2017
6
堆栈数据对象是更通用的线性表对象的限制版本。(插入和删除操作仅能在表的同一端进行)
例如,如果把表的左端定义为栈底,右端定义为栈顶,那么堆栈的添加操作等价于在表的右端进行插入操作,删除操作等价于在表的右端进行删除操作。
继承
8/4/2017
7
template<class T>
class Stack :: private LinearList <T>{ // LIFO 对象
public:
Stack(int MaxStackSize = 10):LinearList<T>(MaxStackSize){ }
bool IsEmpty() const
{return LinearList<T>::IsEmpty();}
bool IsFull() const
{return (Length() == GetMaxSize());}
T Top() const
{if (IsEmpty()) throw OutOfBounds();
T x; Find(Length(), x); return x;}
Stack<T>& Add(const T& x)
{Insert(Length(), x); return *this;}
Stack<T>& Delete(T& x)
{LinearList<T> :: Delete (Length(), x);
return *this;}
} ;
公式化描述的堆栈类(派生)
8/4/2017
8
template<class T>
class Stack{ // LIFO 对象
public:
Stack(int MaxStackSize = 10);
~Stack () {delete [] stack;}
bool IsEmpty() const {return top == -1;}
bool IsFull() const {return top == MaxTo p ; }
T Top() const;
Stack<T>& Add(const T& x);
Stack<T>& Delete(T& x);
private :
int top; // 栈顶
int MaxTop; // 最大的栈顶值
T *stack; // 堆栈元素数组
} ;
自定义Stack
8/4/2017
9
template<class T>
Stack<T>::Stack(int MaxStackSize)
{ MaxTop = MaxStackSize - 1;
stack = new T[MaxStackSize];
top = -1;
}
Stack 类构造函数
8/4/2017
10