栈和队列.ppt

文档介绍：第四章栈和队列
栈和队列都是操作受限的线性表,应用十分广泛。
栈(Stack)
定义:栈是限制插入和删除操作只能在某一端进行的线性表,并按先进后出( F I L O )或后进先出(LIFO)的原则进行操作
入栈顺序:
e0 e1 e2 … en-2 en-1
出栈顺序:
en-1 en-2 … e2 e1 e0
栈可以对序列实现求逆
en-1
e0
e1
en-2
…
进栈(Push) 出栈(Pop)
栈顶 top
栈底
11/10/2017
1
栈的基本操作: (参见P104)
(1)栈初始化 Stack ( int = 10 );//构造函数
(2)进栈 Push void Push( const Type & item );
(3)出栈 Pop Type Pop( );
(4)判栈空 IsEmpty int IsEmpty( ) { return top==-1;}
(5)读取栈顶元素 GetTop Type GetTop ( );
(6)置空栈 MakeEmpty void MakeEmpty( ) { top=-1;}
(7)判栈满 IsFull int IsFull( ) const { return top==maxSize;}
栈的封闭性及其抽象数据类型:
在一个栈中,出入口处称为栈顶,栈内最深处称为栈底。除了栈顶元素外,其他元素不会被改变,因而栈的封闭性非常好,使用起来非常安全。另外,在下面的栈的类定义中,体现了栈的抽象数据类型,在此定义中,所有栈的成员函数都是共有的,其他类的成员函数都可以使用这些函数,但是,栈的存储表示和成员函数的实现对其他类的成员来说都是隐蔽的。
11/10/2017
2
顺序栈--在顺序存储结构上实现的栈
# include < > //C++断言功能
template <class Type > class Stack //顺序栈的类定义
{ public:
Stack ( int=10 );//栈初始化,建立一个空栈,缺省大小为10
~Stack ( ) { delete [ ] elements ; }
void Push ( const Type & item ); //将数据元素 item 入栈
Type Pop ( ) ; //将栈顶元素出栈
Type GetTop ( ) ; //读取栈顶元素
void MakeEmpty ( ) { top=-1;} //置空栈,top=-1表示栈为空
int IsEmpty ( ) const { return top==-1;} //判栈空
int IsFull ( ) const { return top==maxSize-1;} //判栈满
private: //top=maxSize-1表示栈已满
int top;//栈顶指针(栈顶元素下标)
Type * elements;//存储顺序栈的数组
int maxSize;//顺序栈的最大容量
}
11/10/2017
3
顺序栈的基本操作(算法)
(1)顺序栈初始化算法(构造函数)
template <class Type> Stack<Type>::Stack(int s):top(-1),maxSize(s)
//建立一个最大尺寸为 s 的空栈,若分配不成功则错误处理
{
element=new Type[maxSize];//创建顺序栈空间(数组)
assert( elements != 0);
//断言语句:若条件成立,则继续;否则出错处理并终止执行
}
(2)顺序栈入栈算法
template <class Type> void Stack<Type>::Push(const Type & item)
//若栈不满,则将元素 item 插入到栈顶,否则出错处理
{
assert( ! IsFull());//断言:栈不满则继续执行
elements[++top]=item;//栈顶指针先加 1 ,然后按此地址进栈
}
11/10/2017
4
(3)顺序栈出栈算法
template <class Type> Type Stack<Type>::Pop()
//若栈不空,则返回栈顶元素,并使栈顶指针退 1 ;否则出错处理
{
assert( ! IsEmpty());//断言:若栈不空,则继续执行
return elements[top--];//返回栈顶元素,并使栈顶指针退 1
}
(4)读取顺序栈栈顶元素算法
Template <class Type> Type Stack<Type>::GetTop()
//若栈不空,则返回