文档介绍：数据结构与算法
-5
线性结构- 栈、队列
栈( Stack )
只允许在一端插入和删除的顺序表
允许插入和删除
的一端称为栈顶
(top),另一端称
为栈底(bottom)
特点
后进先出(LIFO)
template <class Type> class Stack {
public:
Stack ( int=10 ); //构造函数
void Push ( const Type & item); //进栈
Type Pop ( ); //出栈
Type GetTop ( ); //取栈顶元素
void MakeEmpty ( ); //置空栈
int IsEmpty ( ) const; //判栈空否
int IsFull ( ) const; //判栈满否
}
栈的抽象数据类型
#include <>
template <class Type> class Stack {
public:
Stack ( int=10 ); //构造函数
~Stack ( ) { delete [ ] elements; }//析构函数
void Push ( const Type & item ); //进栈
Type Pop ( ); //出栈
Type GetTop ( ); //取栈顶元素
void MakeEmpty ( ) { top=-1; } //置空栈
int IsEmpty ( ) const { return top == -1; }
栈的数组表示—顺序栈
int IsFull ( ) const
{ return top == maxSize-1; }
private:
int top; //栈顶数组指针
Type *elements; //栈数组
int maxSize; //栈最大容量
}
template <class Type> Stack<Type>::
Stack ( int s ) : top (-1), maxSize (s) {
elements = new Type[maxSize];
assert ( elements != 0 ); //断言
}
进栈示例
退栈示例
template <class Type> void Stack<Type>::
Push ( const Type & item ) {
assert ( !IsFull ( ) ); //先决条件断言
elements[++top] = item; //加入新元素
}
template <class Type> Type Stack<Type>::
Pop ( ) {
assert ( !IsEmpty ( ) ); //先决条件断言
return elements[top--]; //退出栈顶元素
}
template <class Type> Type stack<Type>::
GetTop ( ) {
assert ( !IsEmpty ( ) ); //先决条件断言
return elements[top]; //取出栈顶元素
}
双栈共享一个栈空间