文档介绍：栈
栈的应用举例 数制转换 迷宫求解 表达式求值
* 栈和递归的实现
队列 链队列-- 队列的链式表示与实现 循环队列-- 队列的顺序表示与实现
第三章栈和队列
栈(stack): 先进后出( FILO)的线性表。
或后进先出( LIFO)的线性表。
或仅在表尾进行插入和删除操作的线性表。
栈顶(top): 线性表的表尾端,即可操作端。
栈底(bottom): 线性表的表头。
栈 抽象数据类型栈的定义
栈底
栈顶
......
a1
a2
a3
an-1
an
入栈(push)
出栈(pop)
例、一叠书或一叠盘子。
a n
a n-1
a2
a1
……
栈顶
栈底
栈的抽象数据类型
ADT Stack {
数据对象:D = {ai | ai属于Elemset,
(i=1,2,…,n, n≥0)}
数据关系:R1 = {<ai-1,ai>|ai-1,ai属于D,(i=2,3,…,n)} 约定an为栈顶, a1为栈底。
基本操作:
InitStack(&S); DestroyStack(&S);
ClearStack(&S); StackEmpty(S);
StackLength(S) ; GetTop(S, &e);
Push(&S, e); Pop(&S, &e);
StackTraverse(S, visit ( ))
}ADT Stack
栈的基本操作(之一)
InitStack(&S)
操作结果:构造一个空的栈S。
DestroyStack(&S)
初始条件: 栈S已经存在。
操作结果: 销毁栈S。
ClearStack(&S)
初始条件: 栈S已经存在。
操作结果: 将栈S重置为空栈。
栈的基本操作(之二)
StackEmpty(S)
初始条件: 栈S已经存在。
操作结果: 若栈S为空栈,则返回TURE;否则返回FALSE。
StackLength(S)
初始条件: 栈S已经存在。
操作结果: 返回栈S中的数据元素个数。
GetTop(S, &e)
初始条件: 栈S已经存在且非空。
操作结果: 用e返回栈S中栈顶元素的值。
栈的基本操作(之三)
Push(&S, e) /*入栈操作*/
初始条件: 栈S已经存在。
操作结果: 插入元素e为新的栈顶元素。
Pop(&S, &e) /*出栈操作*/
初始条件: 栈S已经存在且非空。
操作结果: 删除S的栈顶元素并用e返回其值。
StackTraverse(S, visit ())
初始条件: 栈S已经存在且非空。
操作结果: 从栈底到栈顶依次对S的每个元素调用函数visit ()。一旦visit ()失败,则操作失败。
栈的顺序表示与实现--- (顺序栈)
typedef struct{
SElemType *base;
/* 在栈构造之前和销毁之后,base的值为NULL*/
SElemType *top; /* 栈顶指针*/
int stacksize; /* 当前已分配的存储空间,以元素为单位*/
}SqStack;
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define OVERFLOW -1
#define ERROR 0
顺序栈示意图
*base
*top
stacksize
......
a1
...
ai
an
*base
*top
stacksize
初始空栈
*top = *base;
stacksize = STACK_INIT_SIZE
顺序栈
顺序栈的操作实现举例 InitStack /* 构造一个空的栈S*/
Status InitStack(SqStack &s)
{ =( SElemType *)malloc
(STACK_INIT_SIZE * sizeof(SElemType));
if(!) exit(OVERFLOW);
= ;
= STACK_INIT_SIZE;
return OK;
} /* InitStack */