文档介绍：第三章栈、队列和串
北京邮电大学
信息与通信工程学院
《数据结构与STL》
-2-
什么是栈、队列、串?
普通的线性表
1)可以存储任意类型的数据
2)可以在任意位置进行插入、删除操作。
特殊的线性表
栈: 后进先出LIFO线性表
队列:先进先出FIFO线性表
串: 字符为数据元素的线性表
《数据结构与STL》
3
第三章栈、队列和串
学****内容:
栈
队列
串
实例分析
STL中的相关模板类
《数据结构与STL》
4
栈(stack)
限定仅在表尾进行插入和删除操作的线性表
栈:
a1
a2
a3
入栈
出栈
栈底
栈顶
不含任何数据元素的栈称为空栈
栈的特性:后进先出
栈的基本操作: 入栈(进栈) 出栈(退栈)
栈的逻辑结构
《数据结构与STL》
5
假定有三个元素按a、b、c的次序依次进栈,且每个元素只允许进一次栈,则可能的出栈序列有多少种?
注意:栈只是对表插入和删除操作的位置进行了限制,并没有限定插入和删除操作进行的时间。
abc、acb、bac、bca、cba
日常生活还有哪些栈的例子?
《数据结构与STL》
6
栈的常见操作
1. 置空栈SetNull(S)
将栈S置成空栈。
2. 入栈Push (S, x)
将元素x插入到栈S的栈顶。
3. 出栈PoP(S)
删除栈S的栈顶元素。
4. 取栈顶元素GetTop (S)
返回栈S的栈顶元素,栈顶元素并不出栈。
5. 判栈空Empty(S)
判别栈S是否为空。
《数据结构与STL》
7
栈的顺序存储结构
栈的顺序存储结构——顺序栈
使用数组实现
栈空:top= -1
top
top
进栈:top加1
0 1 2 3 4 5 6 7 8
a1
a2
top
出栈:top减1
一般用数组的开始一端表示栈底,同时附设top指示栈顶元素在数组中的位置。
《数据结构与STL》
8
栈的操作示意:
《数据结构与STL》
9
顺序栈的C++类实现
const int StackSize = 1024; //定义栈的最大高度
template <class T>
class SeqStack //定义顺序栈模板类
{
public:
SeqStack(){top = -1;}//构造函数,初始化空栈
void Push(T x); //入栈操作
T Pop(); //出栈操作
T GetTop(); //查找栈顶元素
bool Empty(); //判别栈是否为空
private:
T data[StackSize];//定义数组
int top; //栈顶”指针”
};
顺序栈与顺序表的定义有何区别?
《数据结构与STL》
10
//出栈操作
template <class T>
T SeqStack<T>::Pop()
{
if (Empty()) throw "下溢";
top--;//栈顶指针下移
return data[top+1];
}
//入栈操作
template <class T>
void SeqStack<T>::Push(T x)
{
if (top >= StackSize-1) throw "上溢";
top++;//栈顶指针上移
data[top] = x;
}
//查找栈顶元素
template <class T>
T SeqStack<T>::GetTop()
{
if (Empty()) throw "下溢";
return data[top];
}