文档介绍：上海大学计算机学院
沈俊
第4章栈和队列
******@.
主要内容
栈的基本概念
栈的存储结构
栈的基本运算
栈的简单应用举例
队列的基本概念
队列的存储结构
队列的基本运算
栈的基本概念
栈(stack)是限定仅在表尾一端进行插入或删除操作的特殊线性表。对于栈来说, 允许进行插入或删除操作的一端称为栈顶(top),而另一端称为栈底(bottom)。不含元素栈称为空栈,向栈中插入一个新元素称为入栈或压栈, 从栈中删除一个元素称为出栈或退栈。
假设有一个栈S=(a1, a2, …, an), a1先进栈, an最后进栈。称a1为栈底元素, an为栈顶元素, 。出栈时只允许在栈顶进行, 所以an先出栈, a1最后出栈。因此又称栈为后进先出(Last In First Out,LIFO)的线性表。
栈的结构示意图
【】很窄的死胡同,每次只能容许一人进出.
【】桌上的一摞书,假定每次取书只取最上面的一本,放书必须放在最上面。
死胡同示意图
栈的基本操作
初始化:初始化一个空栈。
求长度:求栈中数据元素的数目。
取栈顶元素:当栈不空时,取栈顶数据元素,并返回成功状态;否则返回不成功状态。
入栈:在栈顶插入一个新元素item。如果能顺利插入元素,则返回插入成功;否则返回插入失败。
出栈:当栈不空时,删除栈顶元素,并返回出栈成功;否则返回出栈失败。
判断栈是否为空栈:如果栈为空,则返回值TRUE,否则返回值FALSE。
清空栈:将栈为空栈。
栈的存储结构
栈的顺序存储结构
栈的链接存储结构
栈的两种存储结构的比较
多个栈共享一个数组的存储空间
栈的顺序存储结构
// 顺序栈类
template<class ElemType>
class SqStack
{
protected:
// 顺序栈的数据成员:
int top; // 栈顶指针
int maxSize; // 栈最大容量
ElemType *elems;// 元素存储空间
顺序栈的定义
public:
SqStack(int size = DEFAU