取栈顶元素
template<class ElemType> Status LinkStack<ElemType>::Top(ElemType &e) const { if(Empty()) // 栈空 return UNDER_FLOW; else { // 栈非空,操作成功 e = top->data;// 用e返回栈顶元素 return SUCCESS; } }
4.2.2 栈的链接存储结构
•top是栈顶指针，指向链栈的栈顶结点； •top=NULL 表示栈空； •若链栈非空，则top是指向链表的第一个结点(栈顶结点)的指针。 •栈顶结点是最后一个入栈的元素，而栈底结点是最先入栈的元素。
•链栈的结点是动态分配的，不会出现栈满的现象，只有空栈和非空栈两种状
态。
栈的基本操作
初始化：初始化一个空栈。
求长度：求栈中数据元素的数目。
取栈顶元素：当栈不空时，取栈顶数据元素，并返回成功状
态；否则返回不成功状态。 入栈：在栈顶插入一个新元素item。如果能顺利插入元素， 则返回插入成功；否则返回插入失败。
出栈：当栈不空时，删除栈顶元素，并返回出栈成功；否则
顺序栈的析构函数
template<class ElemType> SqStack<ElemType>::~SqStack() { delete []elems; }
// 释放存储空间
求顺序栈的长度
template <class ElemType> int SqStack<ElemType>::Length() const { return top; }
顺序栈的定义
// 顺序栈类
template<class ElemType> class SqStack
{Hale Waihona Puke protected: // 顺序栈的数据成员:
int top;
int maxSize;
// 栈顶指针
// 栈最大容量
ElemType *elems;// 元素存储空间
public:
SqStack(int size = DEFAULT_SIZE); virtual ~SqStack(); int Length() const; bool Empty() const;
求链式栈的长度
template <class ElemType> int LinkStack<ElemType>::Length() const { int count = 0; // 计数器 Node<ElemType> *Ptr; for (Ptr = top; Ptr != NULL; Ptr = Ptr->next) count++; } return count; }
第4章 栈 和 队 列
上海大学计算机学院 沈 俊
JShen@
主要内容
4.1 4.2 4.3 4.4 4.5 4.6 4.7 栈的基本概念 栈的存储结构 栈的基本运算 栈的简单应用举例 队列的基本概念 队列的存储结构 队列的基本运算
4.1 栈的基本概念
栈（stack）是限定仅在表尾一端进行插入或删除操作的特 殊线性表。对于栈来说, 允许进行插入或删除操作的一端称为栈 顶（top）,而另一端称为栈底（bottom）。不含元素栈称为空栈， 向栈中插入一个新元素称为入栈或压栈， 从栈中删除一个元素 称为出栈或退栈。 假设有一个栈Ｓ＝（a1, a2, …, an), a1先进栈, an最后进栈。称 a1为栈底元素, an为栈顶元素, 如图3.1所示。出栈时只允许在栈 顶进行, 所以an 先出栈, a1 最后出栈。因此又称栈为后进先出
遍历链式栈
template <class ElemType> void LinkStack<ElemType>::Traverse(void (*Visit)(const ElemType &)) const { Node<ElemType> *Ptr; for (Ptr = top; Ptr != NULL; Ptr = Ptr->next) (*Visit)(Ptr->data); }
遍历顺序栈
template <class ElemType> void SqStack<ElemType>::Traverse(void (*Visit)(const ElemType &)) const { for (int Pos = top-1; Pos >= 0; Pos--) (*Visit)(elems[Pos]); }
链序栈的构造函数
template<class ElemType> LinkStack<ElemType>::LinkStack() { top = NULL; }
链序栈的析构函数
template<class ElemType> LinkStack<ElemType>::~LinkStack() { Clear(); }
出栈
template<class ElemType> Status LinkStack<ElemType>::Pop(ElemType &e) { if (Empty()) // 栈空 return UNDER_FLOW; else { // 操作成功 Node<ElemType> *old_top = top;// 旧栈顶 e = old_top->data; // 用e返回栈顶元素 top = old_top->next; // top指向新栈顶 delete old_top; // 删除旧栈顶 return SUCCESS; } }
{
判断链式栈是否为空
template<class ElemType> bool SqStack<ElemType>::Empty() const { return top = = NULL; }
清空链式栈
template<class ElemType> void SqStack<ElemType>::Clear() { Node<ElemType> *Ptr; while (top != NULL) { Ptr = top; top = top->next; delete Ptr; } }
出栈
template<class ElemType> Status SqStack<ElemType>::Pop(ElemType &e) { if (Empty()) // 栈空 return UNDER_FLOW; else { // 操作成功 e = elems[--top]; return SUCCESS; } }
// 栈顶指针
public: // 链栈的函数成员: LinkStack(); virtual ~LinkStack(); int Length() const; // 求栈长度 bool Empty() const; // 判断栈是否为空 void Clear(); // 将栈清空 void Traverse(void (*Visit)(const ElemType &)) const ; Status Push(const ElemType &e); // 入栈 Status Top(ElemType &e) const; // 取栈顶元素 Status Pop(ElemType &e); // 出栈 };
取栈顶元素
template<class ElemType> Status SqStack<ElemType>::Top(ElemType &e) const { if(Empty()) // 栈空 return UNDER_FLOW; else { // 栈非空,操作成功 e = elems[top - 1]; // 用e返回栈顶元素 return SUCCESS; } }
【例4.5】 假设一个栈S为(A,B,C)，采用链栈存储。
data next C data next B data next A 栈底
^
top
栈顶
(a) 栈的链接存储结构
data next E data next D data next C data next B data next A 栈底
^
top
栈顶
(b) 向链栈中插入两个结点D和E
data next D 栈顶
data next C
data next B
data next A
top
^
栈底
(c) 从链栈中删除栈顶结点E
图4.4 栈的链接存储结构及其操作过程
链式栈的类定义
#include "node.h" // 链栈类 template<class ElemType> class LinkStack { protected: // 链栈的数据成员: Node<ElemType> *top; // 结点类
判断顺序栈是否为空
template<class ElemType> bool SqStack<ElemType>::Empty() const { return top = = 0; }
清空顺序栈
template<class ElemType> void SqStack<ElemType>::Clear() { top = 0; }
返回出栈失败。 判断栈是否为空栈：如果栈为空，则返回值TRUE，否则返 回值FALSE。 清空栈：将栈为空栈。