文档介绍：1、栈 2、队列 3、优先队列 4、栈和队列的应用
第三章栈和队列
栈的定义
限定只能在表尾端进行插入和删除的线性表。
栈顶:表尾端被称之为栈顶。
栈底:和表尾相对应的另一端,称之为栈底。
时间有序表:LIFO 特征的线性结构。
A
B
初态
A
B出栈
A
B
C
C进栈
栈的 ADT (Abstract Data Type)
template <class ElemType>
class AbsStack {
public:
AbsStack ( ) { } // 默认构造函数
virtual ~ AbsStack ( ) { } // 析构函数
virtual int IsEmpty ( ) const = 0; // 判栈空吗?
virtual int IsFull ( ) const = 0; // 判栈满吗?
virtual void MakeEmpty( ) = 0; //将栈清空。
virtual void Push ( const ElemType & X ) = 0; //新结点进栈。
virtual void Pop ( ) = 0; // 栈顶结点出栈。
virtual const ElemType & Top( ) const = 0; // 取栈顶结点数据值。
private:
AbsStack( const AbsStack & ) { } // 冻结复制另一堆栈的构造函数。
};
顺序表示的堆栈
top
空栈
top == -1 是栈空标志
stacksize = = 4
top
A
top
A
B
A
B
C
top
top
A
B
C
D
注意: 因为 top == -1是栈空标志,所以 top 指针指示真正的栈顶元素的下 标地址。
栈满时的处理方法:
1、报错。返回操作系统。
2、分配更大的空间,作为栈的存储空间。将原栈的内容移入新栈。
3
1
2
0
顺序表示的堆栈的实现
static const int InitStackSize = 10;
template <class ElemType> class Stack: public AbsStack<ElemType> {
private:
ElemType * Array; // 存放结点的数组名。
int top; // top - 栈顶指针。
int MaxSize; // 栈内能够存放结点的最大个数,即栈的容量。
void DoubleArray( int Max ); // 更新数组的容量。
public:
Stack ( ); // 构造函数, 初始时构造大小为InitStackSize的栈。
~Stack ( ) { delete [ ] Array; }; // 析构函数,释放占用的连续空间。
void MakeEmpty ( ) { top = -1; }; // 将栈清空。
int IsEmpty ( ) const { return top = = -1; }; //栈空为True,否则为False。
int IsFull ( ) const { return top = = MaxSize-1; }; //栈满为True,否则为False。
const ElemType & Top( ) const ; // 读取栈顶结点。
void Push ( const ElemType & X ); // 将X的值进栈。
void Pop ( ); // 栈顶结点出栈。
const Stack & operator = ( const Stack & R );
};
顺序表示的堆栈的实现
template<class ElemType>
Stack<ElemType> :: Stack( ) : top( -1), MaxSize(InitStackSize) {
//构造函数, 空间大小为MaxSize
Array = new ElemType[MaxSize];
}
template <class ElemType> const ElemType & Stack<ElemType> :: Top( ) const {
// 对非空栈,读取栈顶结点并返回结点的值。
Exception( IsEmpty( ), ”Underflow:Satck is Empty!”);
return Array[top];
}
template <class ElemType> void Stack<ElemType>::Push ( const ElemType & X ) {