数据结构第三章_栈和队列

nullnull北京联合大学信息学院 张冰峰 办公室：北院A楼 五层信息系统教研部 电 话：64900518 邮 箱：xxtbingfeng@buu.com.cn第3章栈和队列第3章栈和队列本章要点 栈和队列的基本概念和基本运算。 栈和队列存储表示和基本运算的实现方法。 栈和队列应用。 本章要求 通过本章的学习应该掌握栈和队列逻辑结构和存储结构，以及栈和队列基本运算和算法实现。能理解和运用栈和队列的实际应用。 null 从数据结构上看，栈和队列也是线性表，不过是两种特殊的线性表.被称作为操作受限的线性表。 3.1栈 3.1.1栈的概念及运算 1.栈的定义 栈（Stack)是限制仅在表的一端进行插入和删除运算的线性表，通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。栈的插入操作通常称为入栈或进栈(push)，而栈的删除操作则称为出栈或退栈(pop)。当表中没有元素时称为空栈。 null 根据上述定义可知，栈顶元素总是最后入栈的，因而是最先出栈；栈底元素总是最先入栈的，因而也是最后出栈。这种表是按照后进先出（LIFO，Last In First Out ）的原则组织数据的，因此，栈也被称为“后进先出”的线性表。a1 an 入栈 出栈 栈顶 top 栈底 bottom 图3.1 栈的示意图 ．．． a2 栈的基本运算栈的基本运算 2.栈的运算 （1）创建空栈 SeqStack *InitStack() （2）判栈空 isEmptyStack(SeqStack *S) （3）进栈 SeqStack Push(SeqStack *S ,datatype x) （4）退栈 datatype pop(SeqStack *S ) （5）取栈顶 GetTop(SeqStack *S) 与Pop(s)的不同处在于GetTop(s)不改变栈的状态。 栈是一种特殊的线性表，因此栈可采用顺序存储结构存储，也可以使用链式存储结构存储。3.1.2 栈的顺序存储结构3.1.2 栈的顺序存储结构顺序栈的类型和变量定义如下： ＃define Maxsize 100 /* 栈可能达到的容量*/ typedef int datatype /* 栈元素的数据类型*/ typedef struct { datatype stack[Maxsize]; int top; }SeqStack; /* 顺序栈的类型定义*/ SeqStack *s;null鉴于C语言中数组的下标约定是从0开始的，因而使用C语言的一维数组作为栈的顺序存储结构时，应设栈顶指针S->top=-1时为空栈，s->top= Maxsize -1为栈满。2．顺序栈的基本运算算法2．顺序栈的基本运算算法 栈是一个动态结构，而数组是一静态结构，会出现所谓的溢出问题：包括上溢（Overflow) 和下溢（Underflow)。 在进行进栈和出栈运算前要判断栈的状态。 创建空栈 SeqStack *InitStack() { SeqStack *S; S=(SeqStack *)malloc(sizeof(SeqStack)); if(!S) {printf(“空间不足”);null return NULL;} else {S->top=-1; return S;} } 2.取栈顶元素datatype GetTop(SeqStack *S) 3.入栈 SeqStack *Push(SeqStack *S,datatype x) 4.出栈 Pop(SeqStack *S) 5.判栈空 StackEmpty(SeqStack *S) 3.1.4 栈的链式存储结构3.1.4 栈的链式存储结构 栈的链式存储结构称为链栈。在一个链栈中，栈底就是链表的最后一个结点，而栈顶总是链表的第一个结点。因此，新入栈的元素即为链表新的第一个结点，只要系统还有存储空间，就不会有栈满的情况发生。一个链栈可由栈顶指针top唯一确定，当top为null时，是一个空栈。top…top…q修改栈顶指针top=p修改栈顶指针top=top->nextnull（a）A∧toptop（b）（s）top（a）含有两个元素A、B的栈；（b）插入元素C后的栈；（c）删除元素C、B后的栈栈的链式存储结构和操作实现　栈的链式存储结构和操作实现　结点结构定义 typedef struct node { datatype data; struct node *next; }LinkStack; LinkStack *top;栈的链式存储结构和操作实现栈的链式存储结构和操作实现 (1)判空栈int StackEmpty(LinkStack *top) { return (top= =NULL) } (2)取栈顶datatype GetTop(LinkStack *top) (3)入栈LinkStack *Push(LinkStack *top,datatype x) (4)出栈顶LinkStack *Pop(LinkStack *top)3.2栈的应用3.2栈的应用 栈具有后进先出的特点,凡问题求解具有后进先出的特性,求解过程必然需要用到栈。 （1） 数制转换 （2）括号匹配问题 （3）子程序调用 （4）利用栈逆置一个带头结点的单链表3.2栈的应用3.2栈的应用1.用栈实现递归函数 在各种程序设计语言中都有子程序（或称函数、过程）调用功能。而子程序也可以调用其它的子程序，甚至可以直接或间接地调用自，这调用关系就是递归。下面以求阶乘的递归方法为例，来分析计算机系统如何处理这种递归调用关系的。 求n！的递归方法的思路是： 相应的C语言函数是： float fact(int n) { float s; if (n= =0||n= =1) s=1; else s=n*fact(n-1); return (s); } 在该函数中可以理解为求n！用fact(n)来表示，则求(n-1)！就用fact(n-1)来表示。若求5!，则有3.2栈的应用3.2栈的应用 main() { printf(“5!=%f\n”,fact(5)); } 图3.5给出了递归调用执行过程。从图中可看到fact函数共被调用5次，即fact(5)、fact(4)、fact(3)、fact(2)、fact(1)。其中，fact(5)为主函数调用，其它则为在fact函数内的调用。每一次递归调用并未立即得到结果，而是进一步向深度递归调用，直到n=1或n=0时，函数fact才有结果为1，然后再一一返回计算，最终得到结果。null图3.5 递归调用过程示意图3.2栈的应用3.2栈的应用计算机系统处理上述过程时，其关键是要正确处理执行过程中的递归调用层次和返回路径，也就是要记住每一次递归调用时的返回地址。在系统中是用一个线性表动态记忆调用过程中的路径，其处理原则为： （1）在开始执行程序前，建立一个线性表，其初始状态为空。 （2）当发生调用（递归）时，将当前的调用的返回点地址插入到线性表的末尾； （3）当调用（递归）返回时，其返回地址从线性表的末尾取出。 根据以上的原则，可以给出线性表中的元素变化状态如图3.6所示（以递归调用时n值的变化为例）： 3.2栈的应用3.2栈的应用汉诺塔问题 假设有3个塔座X、Y、Z,在塔座X上插有n个直径大小各不相同、从大到小编号为1，2，…，n的圆盘。现要求将X轴上的n个圆盘移至塔座Z上并仍按同样顺序叠排。 圆盘移动时必须遵循下列规则： （1）每次只能移动一个圆盘 （2）圆盘可以插在X、Y和Z中任一塔座上 （3）任何时刻都不能将一个较大的圆盘压在 较小的圆盘之上。3.2栈的应用3.2栈的应用void Hanoi(int n,char x,char y,char z) { if(n==1) move(x,1,z) else hanoi(n-1,x,z,y); move(x,n,z); hanoi(n-1,y,x,z); } xyz3.2栈的应用3.2栈的应用Hanoi(3,a,b,c) Hanoi(2,a,c,b) Hanoi(1,a,b,c) A-C Move(a,2,b) A-B Hanoi(1,c,a,b) C-B Move(a,3,c) A-C Hanoi(2,b,a,c) Hanoi(1,b,c,a) B--A Move(b,2,c) B--C Hanoi(1,a,b,c) A--C A-C A--B C--B A--C B--A B--C A--C 3.3队列3.3队列3.3.1队列的概念及运算 队列（Queue）也是一种运算受限的线性表。它允许在表的一端进行插入，而在另一端进行删除。 允许删除的一端称为队头（Front），允许插入的一端称为队尾（Rear）。 队列的插入操作通常称为入队或进队，而队列的删除操作则称为出队或退队。当队列中无数据元素时，称为空队列。 根据上述队列定义可知，队头元素总是最先进队列的，也总是最先出队列；队尾元素总是最后进队列，因而也是最后出队列。这种表是按照先进先出（FIFO，First In First Out ）的原则组织数据的，因此，队列也被称为“先进先出”表。3.3队列3.3队列假若队列q={a1，a2，a3，…，an}，进队列的顺序为a1 ，a2，a3，…，an，则队头元素为a1，队尾元素为an。 图3.8是一个队列的示意图，通常用指针f (front)指示队头的位置，用指针r(rear)指向队尾。 a1 a2 a3 ai an front rear 图3.8 队列的示意图 … … 3.3队列3.3队列2.队列的基本操作 （1）InitQueue(Q)构造空队列 （2）QueueEmpty(Q) 判断队列空 （3）QueueLength（Q) 求队列长度 （4）GetHead（Q) 返回队头 （5）EnQueue(Q,x) 入队列 （6）DeQueue(Q) 删除队头元素 队列是一种特殊的线性表，因此队列可采用顺序存储结构存储，也可以使用链式存储结构存储。3.3.2顺序队列的数组表示3.3.2顺序队列的数组表示 队列的顺序存储结构称为顺序队列。也就是利用一组地址连续的存储单元依次存放队列中的数据元素。一般情况下，使用一维数组来作为队列的顺序存储空间，由于队列的队头和队尾位置均是变化的，因而要设置两个指针：分别指向当前队头元素和队尾元素在数组中位置。 队头指针指出实际队头元素所在的位置，队尾指针指出队尾元素所在位置的下一个位置。3.3.2顺序队列的数组表示3.3.2顺序队列的数组表示012345rearfront012345rearfront012345rearfront012345rearfront(a)空队列(b)a、b入队(c)a、b出队,c、d入队(d)假溢出循环队列循环队列空队列时再做出队操作便会产生“下溢”。队满的条件是当前队列长度等于向量空间的大小，队满时再做入队操作会产生“上溢”。 如果当前尾指针等于向量上界，即使队列不满，再做入队操作也会引起溢出。此时不能作入队操作，但当前队列并不满，这种现象叫“假溢出”。产生该现象的原因是，被删元素的空间在元素删除以后就永远使用不到。 解决这个问题有两种可行的方法： （1）采用平移元素的方法，当发生假溢出时，就把整个队列的元素平移到存储区的首部，然后再插入新元素。这种方法需移动大量的元素，因而效率是很低的。2.循环队列2.循环队列（2）将顺序队列的存储区假想为一个环状的空间，如图所示。假想paqu->q[0]接在paqu->q[MAXNUM-1]的后面。当发生假溢出时，将新元素插入到第一个位置上，这样做，虽然物理上队尾在队首之前，但逻辑上队首仍然在前。入列和出列仍按“先进先出”的原则进行，这就是循环队列。 很显然，方法二中不需要移动元素，操作效率高，空间的利用率也很高。maxsize-1 0 1 rear front null循环队列的类型定义 #define MaxSize 100 typedef struct { datatype data[MaxSize]; int front; int rear; }SeqQueue;null012345reara4a5front012345reara4a5front012345rearfronta9a8a7a6循环队列满的条件: （rear+1)%rearMaxSize= = front 循环队列空的条件： rear= =front循环队列的基本操作循环队列的基本操作（1）构造空队列 SeqQueue *InitQueue() { SeqQueue *q; q=(SeqQueue *)malloc(sizeof(SeqQueue)); q->front=q->rear=0; return q; } （2）判断队列空 int QueueEmpty(SeqQueue *q) { return (q->front = =q->rear); }null（3）入队int EnQueue(SeqQueue *q,datatype x) （4）出队datatype DeQueue(SeQueue *q) 3.3.3 队列的链式存储结构3.3.3 队列的链式存储结构队列的链式存储结构称为链队列，它是限制仅在表头删除和表尾插入的单链表。在链队列中设定两个指针（头指针和尾指针）分别指向队列的头和尾。 为了操作方便，在队头结点前附加一个头结点，且头指针指向头结点。 null头结点队头队尾。。。 ∧rearfront结点类型定义： typedef Struct Qnode { datatype data; Struct Qnode *next; }Qnode; 链队列类型定义： typedef struct { Qnode *front; Qnode *rear; }LinkQueue;∧frontrearfrontrear∧xfrontrearx∧yfrontrearx∧ynullLinkQueue *InitQueue() { LinkQueue *q; Qnode *p; q=(LinkQueue*)malloc(sizeof(LinkQueue)); p=(Qnode*)malloc(sizeof(Qnode)); p->next=NULL; q->front=q->rear=p; return q; }（1）构造一个空队列链队列的基本操作链队列的基本操作取队头元素 datatype GetHead(LinkQueue *Q) 入队 void EnQueue (LinkQueue *Q,datatype x) 出队 datatype DeQueue(LinkQueue *Q) 队列的应用队列的应用在计算机科学领域中，解决主机与外部设备之间的速度不匹配问题，解决多用户引起的资源竞争问题等，都需要利用队列来处理。 （1）打印杨辉三角形 （2）迷宫问题