数据结构第3章栈和队列.pptx

什么是线性结构？1你见过餐馆中一叠一叠的盘子吗？如果它们是按1,2,…,n的次序往上叠的，那么使用时候的次序应是什么样的？2在日常生活中，为了维持正常的社会秩序而出现的常见现象是什么？3【课前思考】第三章栈和队列

栈和队列与线性表相比，是限定性的线性表结构。1栈的特点：栈必须按“后进先出”的规则进行操作2队列特点：必须按“先进先出”的规则进行操作。3插入删除4线性表：Insert(L,i,x)Delete(L,i)5(1≤i≤n+1)(1≤i≤n)6栈：Insert(L,n+1,x)Delete(L,n)7队列：Insert(L,n+1,x)Delete(L,1)8第三章栈和队列

栈和队列与线性表对比：第三章栈和队列从“数据结构”的角度看，它们都是线性结构即数据元素之间的关系相同。它们是完全不同的数据类型。除了它们各自的基本操作集不同外，主要区别是对插入和删除操作的“限定”。如：线性表允许在表内任一位置进行插入和删除；

栈只允许在表尾一端进行插入和删除；

队列只允许在表尾一端插入，在表头一端删除。

栈的类型定义3.1栈栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。允许插入和删除的一端称作“栈顶(top)”不允许插入和删除的另一端称作栈底(bottom)

通常称往栈顶插入元素的操作为“入栈”，称删除栈顶元素的操作为“出栈”。栈被称为是一种“后进先出”的结构，又称LIFO（LastInFirstOut的缩写）表。如下图所示的铁路调度站

栈的类型定义如下：

ADTStack{

数据对象：D＝{ai?|?ai?∈ElemSet,i=1,2,...,n,n≥0}

数据关系：R1＝{ai-1?,ai?|ai-1??,ai???∈D,i=2,...,n}

约定an端为栈顶，a1端为栈底。基本操作：

InitStack(S)

操作结果：构造一个空栈S。DestroyStack(S)

初始条件：栈S已存在。

操作结果：栈S被销毁。始条件：栈S已存在。

操作结果：若栈S为空栈，则返回TRUE，否则返回FALSE。StackEmpty(S)初始条件：栈S已存在。

操作结果：返回栈S中元素个数，即栈的长度StackLength(S)初始条件：栈S已存在。

操作结果：将S清为空栈。ClearStack(S)初始条件：栈S已存在且非空。

操作结果：用e返回S的栈顶元素。GetTop(S,e)

Push(S,e)

初始条件：栈S已存在。

操作结果：插入元素e为新的栈顶元素。Pop(S,e)

初始条件：栈S已存在且非空。

操作结果：删除S的栈顶元素，并用e返回其值。StackTraverse(S,visit())

初始条件：栈S已存在且非空，visit()为元素的访问函数。

操作结果：从栈底到栈顶依次对S的每个元素调用函数visit()，一旦visit()失败，则操作失败。}ADTStack

3.1栈栈的存储表示和操作的实现栈也有两种存储表示：顺序存储和链式存储顺序存储结构简称为顺序栈链式存储结构简称为链栈栈顶指针意为指示栈顶元素在栈中的位置，但它的值实际是栈中元素的个数，和顺序表中的length值的意义相同。

顺序栈类型的定义//结构定义：typedefstruct{

elemType*base;//存储空间基址

inttop;//栈顶指针

intstacksize;//允许的最大存储空间以元素为单位

}Stack;3.1栈3.1.2栈的存储表示和操作的实现

//基本操作接口(函数声明)：

voidInitStack(StackS，intmaxsize);

//构造一个最大存储容量为maxsize的空栈S。voidDestroyStack(StackS);

//销毁栈S，S不再存在。voidClearStack(StackS);

//将S置为空栈。boolStackEmpty(StackS);

//若栈S为空栈，则返回TRUE，否则返回FALSEintStackLength(StackS);

//返回S的元素个数，即栈的长度。

boolGetTop(StackS,ElemTypee);

//