4 栈和队列.ppt

文档介绍：第四章栈和队列
栈
表达式求值
队列
优先队列
只允许在一端插入和删除的线性表
允许插入和删除
的一端称为栈顶
(top),另一端称
为栈底(bottom)
特点
后进先出(LIFO)
栈( Stack )
退栈
进栈
a0
an-1
an-2

top
bottom
template <class Type> class Stack {
public:
Stack ( int = 10 ); //构造函数
void Push ( Type& item); //进栈
Type Pop ( ); //出栈
Type GetTop ( ); //取栈顶元素
void MakeEmpty ( ); //置空栈
int IsEmpty ( ) const; //判栈空否
int IsFull ( ) const; //判栈满否
}
栈的抽象数据类型
#include <>
template <class Type> class Stack {
private:
int top; //栈顶指针
Type *elements; //栈元素数组
int maxSize; //栈最大容量
public:
Stack ( int = 10 ); //构造函数
~Stack ( ) { delete [ ] elements; }
void Push ( Type & item ); //进栈
栈的数组表示—顺序栈
Type Pop ( ); //出栈
Type GetTop ( ); //取栈顶
void MakeEmpty ( ) { top = -1; } //置空栈
int IsEmpty ( ) const { return top == -1; }
int IsFull ( ) const
{ return top == maxSize-1; }
}
template <class Type> Stack<Type> ::
Stack ( int s ) : top (-1), maxSize (s) {
elements = new Type[maxSize];
assert ( elements != NULL ); //断言
}
top
空栈
top
top
top
top
top
a 进栈
b 进栈
a
a
b
a
b
c
d
e
e 进栈
a
b
c
d
e
f 进栈溢出
a
b
d
e
e 退栈
c
top
c 退栈
b 退栈
a
b
a
a 退栈
空栈
top
a
b
d
d 退栈
c
top
a
b
c
top
top
template <class Type> void Stack<Type> ::
Push ( Type & item ) {
assert ( !IsFull ( ) ); //先决条件断言
elements[++top] = item; //加入新元素
}
template <class Type> int stack<Type> ::
Pop ( ) {
if ( IsEmpty ( ) ) return 0; //栈空不退栈
top--; return 1; //退出栈顶元素
}
template <class Type> Type stack<Type>::
GetTop ( ) {
assert ( !IsEmpty ( ) ); //先决条件断言
return elements[top]; //取出栈顶元素
}
双栈共享一个栈空间
b[0] t[0] t[1] b[1]
0 maxSize-1
V
栈的链接表示—链式栈
链式栈无栈满问题,空间可扩充
插入与删除仅在栈顶处执行
链式栈的栈顶在链头
适合于多栈操作
top