廉洁风险防控机制建设.ppt

文档介绍：第3章栈和队列
栈
栈的应用举例
栈与递归的实现
队列
1
栈
栈的抽象数据类型定义
栈(Stack)是限制在表的一端进行插入和删除运
算的线性表,通常称插入、删除的这一端为栈顶
(Top),另一端为栈底(Bottom)。当表中没有元素
时称为空栈。
假设栈S=(a1,a2,a3,…an),则a1称为栈底
元素,an为栈顶元素。栈中元素按a1,a2,
a3,…an的次序进栈,退栈的第一个元素应为栈顶元素。换句话说,栈的修改是按后进先出的原则进行的。因此,栈称为后进先出表(LIFO)。
栈的ADT定义
2
顺序栈

顺序栈:栈的顺序存储结构,用数组来实
现顺序栈。
栈底位置固定不变,栈顶位置随着进栈
和退栈操作而变化。
栈顶:top
栈底:base
3
例、一叠书或一叠盘子。
a n
a n-1
a2
a1
……
栈顶
栈底
入栈
出栈
4
通常称top为栈顶指针,base为栈底指针。
顺序栈的类型定义如下:
typedef char SElemType;
typedef struct {
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
5
A
top
base
base
top
B
A
base
top
空栈
插入元素A
插入元素B
插入元素:先插入,然后top指针增1
删除元素:top指针减1
6

(1)初始化栈
Status InitStack (SqStack &S,int maxsize) {// 构造一个最大存储容量为 maxsize 的空栈 S
= new SElemType[maxsize]; if (!) exit(OVERFLOW); // 存储分配失败 = maxsize; = ; // 空栈中元素个数为0
return OK; }
7
(2)进栈
Status Push(SqStack &S,SElemType e)
{
if (-