数据结构与算法（C++版）课件第三章 栈和队列.pptx

第3章 栈和队列学时分配：学时分配：4 4学时学时3.1 栈3.1.1 栈的定义及运算3.1.2 顺序栈及运算的算法实现3.1.3 链栈及运算的算法实现3.1.4 栈的应用3.1.5 栈与递归3.2 队列3.2.1 队列的定义及运算3.2.2 顺序队列及运算的实现3.2.3 链队列及运算的实现3.3 栈与队列的比较2【学习目标】【学习目标】l 理解栈和队列的概念、运算特点。l 掌握栈和队列的存储以及运算的实现。l 理解栈和队列在解决实际问题中的应用。l 综合运用栈或队列解决实际应用问题。【思维导图思维导图】3.1.1 3.1.1 栈的定义及运算栈的定义及运算1.1.定义：栈（stack）是运算受限的线性表，限制是运算受限的线性表，限制它的插入和删除操作仅在表的一端进行。栈是后它的插入和删除操作仅在表的一端进行。栈是后进先出的线性表（进先出的线性表（last in first outlast in first out），简称），简称 LIFOLIFO表表2.2.术语：栈顶（术语：栈顶（toptop）,栈顶元素，栈底栈顶元素，栈底（bottom),bottom),空栈空栈,进栈或入栈，出栈或退栈。进栈或入栈，出栈或退栈。3.3.栈的运算的实例栈的运算的实例3.1 栈3.栈的基本运算有五种：（1）初始化栈 initStack（s）：构造了一个空栈s。（2）判栈空empty（s）：若栈s为空栈，返回值为“真”（1），否则返回值为“假”（0）。（3）入栈push（s，x）：在栈s的顶部插入一个新元素x，x成为新的栈顶元素。（4）出栈pop（s）：删除栈s的栈顶元素。（5）读栈顶元素top（s）：栈顶元素作为结果返回，不改变栈的状态。4.栈的存储（1）采用顺序方式存储的栈称为顺序栈（sequential stack）（2）采用链接方式存储的栈称为链栈（linked stack）1.顺序栈用C语言描述如下：3.1.2 顺序栈及运算的算法实现#define MAXSIZE 1024 /*栈可能达到的最大容量*/typedef int DataType;typedef struct DataType dataMAXSIZE;int top;SeqStack;SeqStack *s;/*定义s是一个指向顺序栈的指针*/栈的操作及栈顶指针变化情况2.在顺序栈上实现五种基本运算的C函数（1）初始化栈 首先建立栈空间，然后初始化栈顶指针。eqStack *initSeqStack()SeqStack *s;s=(SeqStack*)malloc(sizeof(SeqStack);s-top=-1;return s;（2）判栈空int empty(SeqStack*s)if(s-top=-1)return 1;else return 0;（3）入栈int push(SeqStack*s,DataType x)if(s-top=MAXSIZE-1)/*栈满不能入栈*/printf(overflow);return 0;s-top+;s-datas-top=x;return 1;（4）出栈void pop(SeqStack*s)/*设栈不空*/s-top-;（5）读栈顶元素DataType top(SeqStack*s)/*设栈不空*/return(s-datas-top);链栈用C语言描述如下：3.1.3 链栈及运算的实现typedef int DataType;typedef struct Node DataType data;struct Node *next;LinkStack;LinkStack *top;/*top为栈顶指针*/【例3.1】将一个十进制正整数N转换成R进制的数。N N/8（整除）N%8（求余）1835 229 3 低 229 28 5 28 3 4 3 0 3 高3.1.4 栈的应用转换算法中的主要步骤如下：（1）当N0时，将N%r存入栈s中，然后用N/r代替N，直到N=0退出循环。（2）只要栈s不空，就读出栈顶元素输出并把栈顶元素出栈。【例3.2】算术表达式中括号匹配的检查用栈来实现括号匹配检查的原则是，对表达式从左到右扫描。（1）当遇到左括号时，左括号入栈；（2）当遇到右括号时，首先检查栈是否空，若栈空，则表明该“右括弧”多余；否则比较栈顶左括号是否与当前右括号匹配，若匹配，将栈顶左括号出栈，继续操作；否则，表明不匹配，停止操作。（3）当表达式全部扫描完毕，若栈为空，说明括号匹配，否则表明“左括弧”有多余的。u递归：函数、过程或数据结构等对象在其定义的内部直接或间接出现了对自身的引用是一种递归。u递归函数：一个函数在其定义的内部直接调用自身，这个函数就叫做直接递归函数。3.1.5 栈与递归long fact(int n)long f;if(n=0)f=1;else f=n*fact(n-1);return f;main()long m;int n=3;m=fact(n);printf(“%d!=%dn”，n，m);递归调用过程中栈及栈中数据的变化状况 u递归函数转换为非递归函数long fact2(int n)/*用栈实现非递归的阶乘运算*/SeqStack*s;long f=1;int i=n;s=initSeqStack();while(i0)push(s,i);i-;while(!empty(s)i=top(s);f=f*i;pop(s);return f;时间复杂度和空间复杂度都为O(n)递归函数的完成需要借助于一个系统栈来保存中间结果。实际上，用户也可以在算法中设置栈来模拟系统栈的作用，从而将递归函数转换为非递归函数。1.定义：只允许在表的一端进行插入，而在表的另一端进行删除，将这种线性表称为队或队列（queue）。2.术语：队尾（rear），队头（front），入队或进队，离队或出队，空队列 队尾元素，队头元素3.在队列中，元素出队的顺序必然与其进入队列的顺序是一致的，最先进入的元素最先离开，所以队列又叫先进先出的线性表，简称为FIFO（FIRST IN FIRST OUT）表。4.队列的应用队列图示a1 a2 a3 a4 a5 入队出队3.2 队列3.2.1队列的定义及运算5.在队列上进行的基本运算（1）队列初始化initQueue（q）：构造一个空队列。（2）判队空emptyQueue（q）：若q为空队则返回为1，否 则返回为0。（3）入队enQueue（q，x）：对已存在的队列q，插入一个元素x 到队尾，队发生变化。（4）出队deQueue（q，x）：删除队头元素，并通过x返回其值，队发生变化。（5）读队头元素frontQueue（q）：读队头元素，并返回其值，队不变。u采用顺序方法存储的队列称为顺序队列（sequential queue）u顺序队列的存储结构用c语言定义如下：#define MAXSIZE 1024 /*队列的最大容量*/typedef int DataType;typedef struct DataType dataMAXSIZE;/*队员的存储空间*/int rear,front;/*队头队尾指针*/SeQueue;SeQueue *sq;/*定义一个指向队列的指针变量*/3.2.2 顺序队列及运算的实现u入队、出队时头尾指针及队列中元素之间的关系 入队操作：sq-rear=sq-rear+1;sq-datasq-rear=x;/*把x写入队尾位置*/出队操作：sq-front=sq-front+1;x=sq-datasq-front;/*把出队元素值赋给x*/队空：sq-rear=sq-front 时队中元素的个数：m=（sq-rear）-（sq-front）u循环队列 解决假溢出的方法之一是将队列的数据区假想成一个头尾相接的环形结构，即 sq-data0紧接在sq-datamaxsize-1之后。在循环队列中，头尾指针的关系不变，进行入队、出队操作时，头尾指针顺时针方向移动 队空情况下还是在队满情况下均有sq-front=sq-rear，也就是说“队满”和“队空”的条件是相同的，出现这种情况显然是不允许的。解决方法有两种：一种是附设一个标志变量以区别是队空还是队满，例如可以设存储队列中元素个数的变量num，当num=0时队空，当num=maxsize时为队满。另一种方法是在循环队列中少用一个元素空间。0123图3.8 循环队列图示fronta3a4a5rearMAXSIZE-1循环队列操作指针变化情况 入队：sq-rear=（sq-rear+1）%MAXSIZE;出队：sq-front=（sq-front+1）%MAXSIZE;判断队满的条件：（sq-rear+1）%MAXSIZE=sq-front;队列中元素的个数为：M=(sq-rear-sq-front+MAXSIZE)%MAXSIZE;队空：sq-front=sq-rearu采用链接方法存储的队列称为链队列（linked queue）u采用带头结点的单链表来实现链队列，链队列中的结点类型与单链表相同。将头指针FRONT和尾指针REAR封装在一个结构体中，链队列用C语言描述如下：typedef struct Node DataType data;struct Node *next;LQNode;/*链队列结点的类型*/typedef struct LQNode *front,*rear;LQueue;/*将头尾指针封装在一起的链队列*/LQueue *q;/*定义一个指向链队列的指针*/3.2.3 链队列及运算的实现u还有一种更简单的链队列实现方法，就是用设尾指针的带头结点的单循环链表来存储队列中的元素 只设了一个尾指针r 头结点的指针，即r-next 队头元素的指针为r-next-next 队空的判定条件是r-next=r 1.具有相同的逻辑结构2.可以采用相同的存储方法3.具有不同的运算特点4.都有广泛的应用价值3.3 栈与队列的比较本章重点：（1）栈与队列的定义及特点，两种结构上基本运算的定义。（2）根据栈和队列的特点，选择栈或者队列在解决实际问题中的具体体现。（3）循环队列的设计方法，队空、队满的判断条件，入队、出队的操作方法，队列中元素个数的计算公式。