循环队列3章小结资料.pptVIP

第三章 栈和队列 从数据结构上看，栈和队列也是线性表，不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除操作，而队列只允许在表的一端进行插入操作、而在另一端进行删除操作。因而，栈和队列也可以被称作为操作受限的线性表。通过本章的学习，大家应能掌握栈和队列的逻辑结构和存储结构，以及栈和队列的基本运算以及实现算法。 【知识点】　栈、队列 3.0 课前思考 3.1 栈 3.2 栈的应用 3.3 队列 3.4 队列的应用 3.5 小结 2.6 练习 3.0 课前思考 你见过餐馆中一叠一叠的盘子吗？如果它们是按1,2,…,n 的次序往上叠的，那么使用时候的次序应是什么样的？ 3.1 栈 一、栈的定义（见书P44） 栈（Stack）是限定只能在表的一端进行插入和删除操作的线性表。 在表中，允许插入和删除的一端称作栈顶(top)，不允许插入和删除的另一端称作栈底(bottom) ，当栈中无数据元素时，称为空栈。 往栈顶插入元素的操作为入栈或进栈 (push) ，称删除栈顶元素的操作为出栈或退栈(pop) 。因为后入栈的元素先于先入栈的元素出栈，故被称为是一种后进先出的结构，因此又称LIFO（Last In First Out的缩写）表。 栈的抽象数据类型定义：ADT Stack {　数据对象：D＝{ai|ai∈ElemSet,i=1,2,...,n, n≥0 }　数据关系：R1＝{ ai-1 , ai |,ai∈D, i=2,...,n }　　　 约定an端为栈顶， a1端为栈底。　基本操作：　　InitStack(S)　　　操作结果：构造一个空栈 S。　　DestroyStack(S)　　　初始条件：栈 S 已存在。　　　操作结果：栈 S 被销毁。 ClearStack(S)　　　初始条件：栈 S 已存在。　　　操作结果：将 S 清为空栈。　　StackEmpty(S)　　　初始条件：栈 S 已存在。　　　操作结果：若栈 S 为空栈，则返回TRUE，否则返回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 已存在且非空，visit( )为元素的访问函数。　　　操作结果：从栈底到栈顶依次对S的每个元素调用函数visit( )，一旦visit( )失败，则操作失败。}ADT Stack 二、栈的存储表示和操作的实现和线性表类似，栈也有两种存储表示。 其顺序存储结构简称为顺序栈。 由链式存储结构得到的栈称为链栈。 1、顺序栈利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针top指示栈顶元素在顺序栈中的位置 。 顺序栈数据结构可表示为： typedef struct{ 　　SElemType *bottom; //栈底指针　　SElemType *top; 　　 //栈顶指针 　　int stacksize; 　// 栈的当前可使用的最大空间容量，以元素为单位} Stack; 注： 若bottom为null，则表明栈结构不存在。 若top= bottom表示空栈。 每插入新的栈顶元素时，指针top增1，删除栈顶元素时， top减1。 因此，非空栈中的栈顶指针始终在栈顶元素的下一个位置上，如下图所示。 顺序栈的模块说明（主要算法） #define STACK_INIT_SIZE 100; //存储空间初始分配量#define STACKINCREMENT 10; //存储空间分配增量typedef struct {　　SElemType *base; //栈底指针，构造之前和销毁之后均 为null值。　　SElemType *top; 　　　　 //栈顶指针　　int stacksize; 　//允许的最大存储空间以元素为单位。　}Stack; Status InitStack(Stack S){//构造一个空栈SS.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof (ElemType));if (!S.base) exit(overflow); //存储分配失败