CH3 栈和队列.ppt

1、第三章 栈和队列,栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS。 3.1 栈 3.2 栈的应用举例 3.4 队列,3.1 栈,一、抽象数据类型栈的定义： 栈（Stack）：是限制在表的一端进行插入和删除运算的线性表。 通常称插入、删除的这一端为栈顶(Top)，另一端为栈底(Bottom)。 当表中没有元素时称为空栈。,假设栈S=(a1，a2，a3，an)，则a1称为栈底元素，an为栈顶元素。栈中元素按a1，a2，a3，an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的修改是按后进先出的原则进行的。因此，栈称为后进先出表（LIFO）。,栈的抽象数据类型定义： ADT S

2、tack 数据对象：Dai | ai ElemSet，i1，2，n，n0 数据关系：R1， ai-1， ai D，i2，n 基本操作： ADT Stack,二、栈的存储表示,二、栈的表示和实现： 栈的顺序存储表示顺序栈 栈的链式存储表示链栈,1、栈的顺序存储表示： 基本思想：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。 栈的顺序存储结构称为顺序栈。 顺序栈的实现：可用数组来实现顺序栈。 栈底：将栈底位置设置在数组的两端的任何一个端点； 栈顶：栈顶位置是随着进栈和退栈操作而变化的，故需用一个整型变量top来指示当前栈顶的位置，通常称top为栈顶指针。,顺序栈的定义： Typedef

3、 struct SElemType *base；/栈底指针，指向栈底位置 SElemType *top；/栈顶指针 int stacksize；/栈的最大容量 SqStack；,栈底指针base：指向顺序栈的栈底位置。 若baseNULL，则表明栈结构不存在。 栈顶指针top：栈初始化时指向栈底，即topbase。 非空栈中top指向栈顶元素的下一个位置。 新元素入栈时，top加1；删除栈顶元素时，top减1。,2、栈的链式存储表示： 栈的链式存储结构称为链栈，它是运算受限的单链表，即插入和删除操作仅限制在表头位置上进行。 由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。 栈

4、顶指针就是链表的头指针。,链栈的类型说明： typedef struct StackNode elemtype data； struct StackNode *next； StackNode ，*LinkStack;,三、栈操作的实现： （一）入栈操作：将新元素压入栈中，成为新的栈顶元素。 顺序栈：利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。 判栈满； 栈满，则重新分配存储空间，转步骤； 栈若未满，则新元素入栈，栈顶指针加1。,算法描述： Status Push（SqStack Push(OPTR,#); InitStack(OPND); c=getchar(); while(c

5、!=#|GetTop(OPTR)!=#) if(!In(c,OP) Push(OPND,c); c=getchar(); else switch(Precede(GetTop(OPTR),c) case: Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b); break; ,2、栈与递归的实现,函数调用的实现：调用函数和被调用函数之间的链接及信息交换通过栈来进行。 调用函数调用运行被调用函数之前： 将所有实参、返回地址等信息传递给被调用函数保存； 为被调用函数的局部变量分配存储区； 将控制转移到被调用函

6、数的入口。,2、栈与递归的实现,函数调用的实现：调用函数和被调用函数之间的链接及信息交换通过栈来进行。 被调用函数返回调用函数之前： 保存被调用函数的计算结果； 释放被调用函数的数据区； 依照被调用函数保存的返回地址将控制转移到调用函数。,2、栈与递归的实现,函数调用的实现：调用函数和被调用函数之间的链接及信息交换通过栈来进行。 当有多个函数构成嵌套调用时，按照“先调用后返回”的原则，调用函数和被调用函数之间的信息传递和控制转移必需通过栈来实现。,函数的递归调用：函数直接或通过一系列的调用语句间接调用自己的过程。 递归定义的数学函数，如阶乘函数； 递归描述的数据结构，如二叉树、广义表； 递归求

7、解的问题，如Hanoi塔问题。,例1、求阶乘的函数。,long Fact ( long n ) if ( n = = 0 ) return 1; else return （n * Fact ( n 1 )）; ,五、队列的类型定义,队列也是一种操作受限的线性表。 队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表。 队尾(rear)允许插入的一端。 队头(front)允许删除的一端。,当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,an之后，a1是队头元素，an是队尾元素。显然，退出队列的次序也只能是a1,a2,an ，也就是说队列的修改是依先进先出的原则进行的。,

8、先进入队列的成员总是先离开队列，因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。 例如：日常生活中的排队、操作系统中的作业排队,队列的抽象数据类型定义： ADT Queue 数据对象：Dai | ai ElemSet，i1，2，n，n 0 数据关系：R1， ai1 ， ai D，i2，n 约定其中a1 端为队列头， an 端为队列尾。 基本操作： InitQueue（ struct QNode *next; QNode,*QueuePtr; typedef struct QueuePtr front; /队头指针 QueuePtr rear; /队尾指针 LinkQueue;,链队列的操作：即为单链表的插入和删除操作的特殊情况，只是尚需修改尾指针或头指针。,基本操作的算法描述： Status InitQueue（LinkQueue /初始化的动态分配存储空间 int front; /头指针，若队列不空，指向队列头元素 int rear; /尾指针，若队列不空，指向队列尾元素的下一个位置 SqQueue;,循环队列的基本操作的算法描述： Status InitQueue(SqQueue ,Status EnQueue（SqQueue else if(i=1) top1+; ctop1=x; else top2- -; ctop