文档介绍：第3章 堆栈和队列
主讲：梁宝兰
教学要求
三种特殊的线性表——栈、队列、优先队列
掌握栈、队列、优先队列的相关概念；
掌握栈、队列、优先队列的顺序存储与链式存储结构
掌握栈和队列的应用，了解优先队列的应用
2
生活中 Push(const Data& x); //压栈
Data Pop(void); //弹出栈
Data GetTop(void); //取栈顶元素
bool IsFull(void); //判断栈是否为满
bool IsEmpty(void); //判断栈是否为空
};
顺序堆栈类
17
//顺序栈的实现
SeqStack:: SeqStack (int max) //构造函数
{ s = new Data [max];
MaxSize = max;
top = 0; //指向栈中最后一个元素后一个元素
}
顺序堆栈类
18
顺序堆栈类
//顺序栈的实现
bool SeqStack IsEmpty() //判断是否空
{
return top ==0;
}
bool SeqStack ::IsFull() //判断是否满
{
return top == MaxSize ;
}
19
顺序堆栈类
//顺序栈的实现
Data SeqStack :: GetTop() const //取栈顶元素
{
if(top==0)
{ cout<<“栈为空”<<endl;
exit(0);
}
return s[top-1];
}
20
顺序堆栈类
//顺序栈的实现
void SeqStack ::Push(const Data& x)
{
if (top == MaxSize) //判断栈是否已满
{ cout<<“栈已满"<<endl;
exit(0);
}
s[top] = x; //在新的栈顶位置放入要压栈的元素
top++; //top指示上一个存储单元
}
21
顺序堆栈类
//顺序栈的实现
Data SeqStack ::Pop(void)
{ Data temp;
if (top = = 0) //判断栈是否为空
{ cout<<“栈已空!!!"<<endl;
exit(0);
}
top- -; //调整栈顶指示器指向下一个存储单元
temp = s[top]; //将栈顶元素保存在temp中
return temp; //返回原来栈顶元素
}
22
回文判断（程序示例）
算法思想：将一个串s的字符依次压入栈中，然后逐步将栈中元素弹出栈，并将出栈元素放入一个新串t中。如果s和t相等，则s是一个回文串。
顺序栈应用
源程序
23
链式堆栈类
链栈：栈的链接存储结构
first
a1
a2
an
∧
ai
如何改造链表实现栈的链接存储？
将哪一端作为栈顶？（线性表的头还是尾？）
链栈需要加头结点吗？
top
栈底
24
定义结点类
class StackNode
{ friend class LinkStack;
private:
Data data;
StackNode * next;
public:
StackNode() { next = NULL; }
StackNode(const Data& x)
{ data = x;
next = NULL;
}
};
链式堆栈类
25
定义结点类
class LinkStack {
private:
StackNode * top;
int size；
public:
LinkStack(); //构造函数
~LinkStack(); //析构函数
void Push(const Data& x); //压栈函数
Data Pop(); //出栈函数
Data GetTop(); //取栈顶元素
bool IsEmpty(); //判断链栈是否为