文档介绍：数据结构 第3章栈和队列
什么是栈和队列??
栈和队列的基本运算
栈和队列的应用
1
数据结构
栈
栈(Stack) :是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端(尾端)进行。
a1
a2
a n-1
a n
…
栈顶
栈底
假设栈S=(a1,a2,a3,…an), 栈中元素按a1,a2,…an的次序进栈,退栈的第一个元素应为栈顶元素,即an。换句话说,栈的修改是按后进先出的原则进行的。因此,栈称为后进先出表。(LIFO)。
2
数据结构
例1:家里吃饭的碗,通常在洗干净后一个一个地落在一起存放,在使用时,若一个一个地拿,一定最先拿走最上面的那只碗,而最后拿出最下面的那只碗。
例2:在建筑工地上,使用的砖块从底往上一层一层地码放,在使用时,将从最上面一层一层地拿取。
3
数据结构
栈的抽象数据类型定义
ADT Stack{
数据对象: D={ai| ai(- ElemSet,i=1,2,...,n,n>=0}
数据关系: R1={<ai-1,ai>| ai-1,ai(- D,i=2,...,n}
基本操作:
InitStack(&S) 构造一个空栈S
DestroyStack(&S) 栈S存在则栈S被销毁
ClearStack(&S) 栈S存在则清为空栈
StackEmpty(S) 栈S存在则返回TRUE,否则FALSE
StackLength(S) 栈S存在则返回S的元素个数,即栈的长度
GetTop(S,&e) 栈S存在且非空则返回S的栈顶元素
Push(&S,e) 栈S存在则插入元素e为新的栈顶元素
Pop(&S,&e) 栈S存在且非空则删除S的栈顶元素并用e返回其值
StackTraverse(S,visit())栈S存在且非空则从栈底到栈顶依次对S的每个数据元素调用visit()一旦visit()失败,则操作失败
}ADT Stack
4
数据结构
栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素,并用起始端作为栈底。
类似于顺序表,我们可用如下的结构来顺序地定义栈。
#define STACK_INIT_SIZE 100 //存储空间的初始分配量
#define STACKINCREMENT 10 //存储空间分配增量
typedef struct{
SElemType *base; //存储空间基址
int top; //栈顶指针(栈的长度)
int stacksize; //当前分配的存储容量(以一数据元素存储长度为单位)
}SqStack;
栈的顺序表示和实现
5
数据结构
顺序栈的建立
Status InitStack_Sq(SqStack &S) {
// 构造一个空的栈S。
= (SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if (!) exit(OVERFLOW); // 存储分配失败
= 0; // 空栈长度为0
= LIST_INIT_SIZE; // 初始存储容量
return OK;
} // InitStack_Sq
此算法的时间复杂度为O (1)。
顺序栈典型操作的实现
6
数据结构
线性栈的销毁
void DestroyStack( SqStack &S ){ // 释放顺序栈S所占存储空间 if () free();
= 0;
= 0; } // DestroyStack_Sq
此算法的时间复杂度为:O (1)
线性栈的清空
void ClearStack( SqStack &S ){ // 将顺序栈S的长度置0
= 0; } // ClearStack_Sq
此算法的时间复杂度为:O (1)
7
数据结构
判断线性栈是否为空
int StackEmpty(SqStack S){
if (==0) return TRUE;
else return FALSE;
}
此算法的时间复杂度为:O (1)
求线性栈S的长度
int StackLength(SqStack S){
return ;
}
此算法的时间复杂度为:O (1)
8
数据结构
获取线性栈S中的栈顶元素的内容
int GetTop(SqStack S,SElemType *e){
if ( == 0) return ERROR;
*e=*(S.