数据结构-03栈和队列

1、数据结构数据结构 1. 第三章 栈栈和队队列主要内容主要内容栈的定义及其基本操作栈的定义及其基本操作1顺序栈及链栈的实现顺序栈及链栈的实现2队列的定义及其基本操作队列的定义及其基本操作3循环队列及链队列的实现循环队列及链队列的实现4栈和队列的应用栈和队列的应用5教学要求教学要求教学重点教学难点难点目标和要求1.理解栈的定义、特征及其所定义的基本操作2. 掌握在两种存储结构上对栈的基本操作的实现3.理解队列的定义、特征及其所定义的基本操作4. 掌握在两种存储结构上对队列的基本操作的实现1.栈的定义及逻辑特点2. 顺序栈和链栈的存储结构及操作实现3.入栈、出栈等操作在顺序栈和链栈上的操作4. 队列

2、栈的定义及逻辑特点5. 顺序队列、循环队列和链队列的存储结构及操作实现6.入队,出队等操作在循环队列和链队列上的操作1.顺序栈的溢出判断条件2.栈的应用3.循环队列的队空、队满判断条件4.循环队列上的插入、删除操作3.1.1栈的定义及其基本操作栈的定义及其基本操作栈：限定结点插入和删除只能在同一端进行的线性表栈：限定结点插入和删除只能在同一端进行的线性表 anan-1.a2a1进栈进栈 出栈出栈 栈顶指针栈顶指针(top) 栈底指针栈底指针(bottom) 栈底元素栈底元素 一个重要特点：最后压入的结点最先弹出，最先压入的结点只能最后弹出LIFO表表(Last In First Out )栈顶

3、指针栈顶指针 (top) 栈底指针栈底指针(bottom)空栈空栈1.1.栈的定义栈的定义栈顶指针和栈底指针都等于0时，栈为空1u 创建栈创建栈2u 判栈空判栈空3u 压栈压栈4u 弹栈弹栈5u 读栈读栈6u 置栈空置栈空7u 求栈长度求栈长度2.2.栈的基本操作栈的基本操作3.1.2顺序栈及其操作顺序栈及其操作1.1.栈的顺序存储结构栈的顺序存储结构顺序存储结构存储的栈称为顺序栈，用一个一维数组存储 栈顶指针不是指针类型，而是一个整数C语言描述顺序栈语言描述顺序栈 #define DT char #define M 100 typedef struct DT dataM; int top;

4、SEQSTACK;指示栈顶元素在顺序栈中的位置顺序栈上的操作顺序栈上的操作创建栈创建栈SEQSTACK INISTACK() SEQSTACK S;S.top =0;return(S);首先根据栈的数据类型说明一个栈S，再置栈顶指针为0栈顶栈顶(top)=0顺序栈上的操作顺序栈上的操作判栈空：判栈空：设S是SEQSTACK类型的变量，栈底位置在向量的低端，stop=0表示空栈top=0M1栈空栈空栈顶指针top,指向实际栈底后的空位置，初值为0topM1压压栈栈.BCDEFtoptoptoptoptop栈满234M1ABCD弹弹栈栈toptoptoptoptop栈空设数组大小为Mtop=0,栈

5、空，此时出栈，则下溢（underflow)注意注意：弹栈算法并未说明对删除了的结点的处置设数组大小为Mtop=M,栈满，此时入栈，则上溢（overflow)压栈：压栈：stop是正向增加的，即进栈时需将stop加1弹栈：弹栈：退栈时需将stop 减1顺序栈上的操作顺序栈上的操作读栈读栈把栈S的栈顶结点数据读出作为函数的返回值12340ABCDEtop返回值读栈读栈char GETSTACK(SEQSTACK S) if (S.top=0) printf(empty!); return 0; else return（S.dataS.top）;S.dataS.top注意：该算法并未改变栈的状态，即

6、已读出的结点仍保存在原处不变3.1.3链栈及其操作链栈及其操作1.1.栈的链存储结构栈的链存储结构链存储结构存储的栈称为链栈，链栈的结点由结点数据和next指针构成。链栈的结点类型： #define DT char typedef struct snode DT data; struct snode *next; STACKNODE;结点通过next指针链接起来链栈的结点数据结点数据结点数据指针指针datanext插入和删除总是在链的插入和删除总是在链的头部头部进行，所以头指针也是栈顶指针进行，所以头指针也是栈顶指针注意注意: : 链栈链栈中指针的方向中指针的方向top为栈顶指针，始终指向当前

7、栈顶元素前面的头结点栈名、链头指针、栈顶指针定义一个链栈 STACKNODE *top 栈顶结点栈顶结点top 栈底结点栈底结点DCBA.非空栈底非空栈底top非空栈底非空栈底3.1.3链栈及其操作链栈及其操作1.1.链栈上的操作链栈上的操作LS 栈顶结点栈顶结点栈底结点栈底结点.Xq新结点新结点LS STACKNODE *PUSLSTACK(STACKNODE *LS,char x)STACKNODE *q;q=(STACKNODE *)malloc(sizeof(STACKNODE); q-data=x; q-next=LS;LS =q;return(LS);压栈压栈链栈无栈满问题，空间可

8、扩充。插入与删除仅在栈顶处执行3.1.3链栈及其操作链栈及其操作弹栈弹栈栈顶结点栈顶结点栈底结点栈底结点.LS pSTACKNODE *POPLSTACK(STACKNODE *LS)STACKNODE *q;if(LS = NULL)printf(Empty!); else q=LS; LS = q-next; free(q);return(LS);LSq=NULL,返回返回n3.1.3链栈及其操作链栈及其操作求栈长度求栈长度int SIZELSTACK(STACKNODE *LS)int n=0; STACKNODE *q;for(q=LS;q!=NULL;q=q-next) n+;ret

9、urn(n); 统计链栈LS中当前所含结点个数 栈顶结点栈顶结点栈底结点栈底结点.LS qn=1qn=2qn=3qn=?3.1.4栈结构的应用栈结构的应用数值转换的应用数值转换的应用一个简单算法是逐次除以基数 d 取余法。如10进制数到2进制数的转换（d2）。例：例： (67)10=(100011)2，其运算过程如下，其运算过程如下： 输 出 顺 序 NN div 2N mod 267331331611680840420210101计 算 顺 序 商为 0 时得到的余数是 Bn 的最高位3.1.4栈结构的应用栈结构的应用topvoid DTOB(int n)SEQSTACK NS;int x=

10、0;NS = INISTACK();if(n=0)NS = PUSSTACK(NS,0);while(n)NS = PUSSTACK(NS,n%2); n=(n-n%2)/2;printf(Conversed to Binary number = );while(!EMPSTACK(NS) x=GETSTACK(NS); NS=POPSTACK(NS);printf(%d ,x);printf(n);67111033top16top8top40top20top10top0Push(S, N%2) 1000011数值转换的应用数值转换的应用3.1.4栈结构的应用栈结构的应用计算算术表达式的应用计

11、算算术表达式的应用这是栈应用的典型例子无括号算术表达式求值（中缀表达式直接求值 ）(1)规定优先级表；(2) 设置两个栈：DNS(运算数栈)和OPS(运算符栈)；(3) 自左向右扫描，遇操作符则与OPS栈顶优先级比较：当前操作符OPS栈顶则进OPS栈；当前操作符 OPS栈顶，DNS栈顶、次顶和OPS栈顶，退栈形成运算， 运算结果进DNS栈。例：例：实现实现5+4*78/2#的运算过程时栈区变化情况的运算过程时栈区变化情况5 + 4 7 8 / 2 #5+47288操作数或结果操作数或结果 33/2429运算符运算符3.2队列队列3.2.1 3.2.1 队列的定义及其基本操作队列的定义及其基本操

12、作队列的定义队列的定义限定在表的一端插入、另一端删除。限定在表的一端插入、另一端删除。 线性表线性表 先进先出先进先出 (FIFO(FIFO结构结构) )。 队头队头 下图是队列的示意图： a1a2an 出队方向 入队方向队头指针队头指针 队尾指针队尾指针 删除端删除端插入端插入端1u 建立队列建立队列2u 判队空判队空3u 插入结点插入结点4u 删除结点删除结点5u 读队头结点读队头结点6u 队列置空队列置空7u 求队列长度求队列长度2.2.队列的基本操作队列的基本操作3.2.2顺序队列及其操作顺序队列及其操作1.1.队列的顺序存储结构队列的顺序存储结构顺序存储结构存储的队列称为顺序队列，用

13、一个一维数组存储 #define DT char#define M 100typedef struct DT dataM； int front，rear； SEQUEUE;C语言描述顺序栈语言描述顺序栈 队头、队尾指针不是指针类型，而是数组元素下标队头指针始终指向队队头结点的前一个结点头结点的前一个结点位置位置队尾指针总是指向队队尾结点位置尾结点位置队头、队尾指队头、队尾指针初始值为针初始值为0顺序队列上的操作顺序队列上的操作头尾头尾 指针指针 初始化时的初始值均应置为初始化时的初始值均应置为 0 0。 入队，尾指针增入队，尾指针增 1 1 出队，头指针增出队，头指针增 1 1 front=

14、0rear= 0234561队空队空234561fronta,b,c插入插入abcrearrear234561a,b,c入队入队abcfront设两个指针设两个指针front,rear,约定：约定：rear指示队尾元素；指示队尾元素；front指示队头元素前一位置指示队头元素前一位置初值初值front = rear = 0空队列条件：空队列条件：front=rear入队列：入队列：sq+rear=x;出队列：出队列：x=sq+front;rearrearfrontrear234561a,b,c删除删除abcfrontfrontfront存在问题存在问题设数组维数为M，则：当front=0,re

15、ar=M时，再有元素入队发生溢出真溢出当front 0,rear=M时，再有元素入队发生溢出假溢出rear234561真溢出真溢出abcfrontrear234561假溢出假溢出abcfront“”队列的存储空间未满，却发生了溢出队列的存储空间未满，却发生了溢出解决解决“假溢出假溢出”的问题有两种可行的方法：的问题有两种可行的方法： (1) 平移元素：把元素平移到队列的首部。 效率低效率低 (2) 将新元素插入到第一个位置上，构成循环队列，入队和出队仍按“先进先出”的原则进行。 操作效率、空间利用率高操作效率、空间利用率高def3.2.3循环队列及其操作循环队列及其操作循环队列是把顺序队列的头

16、尾相接形成一个圆环；逻辑上把1号结点作为M号结点的后继结点处理 基本思想基本思想：把队列设想成环形，让LQ0接在LQM-1之后，若rear+1=M,则令rear=0;实现实现：利用“模”运算入队入队： rear=(rear+1)%M; LQrear=x;出队出队： front=(front+1)%M; x=LQfront;初始状态frontrearB BA A C C0 01 12 23 34 45 5ABCABC出队出队frontrear0 01 12 23 34 45 5DEFDEF入队入队frontE EB BA A F F C CD D0 01 12 23 34 45 5rear队满、

17、队空判定条件队满、队空判定条件仅凭 front = rear 不能判定队列是空还是满 解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间： 队空：front=rear 队满：(rear+1)%M=front循环队列初始条件： 队头指针队头指针 = 队尾指针队尾指针 = 0循环队列满条件： MOD（队尾指针（队尾指针+1,M） = 队头指针队头指针循环队列空条件： 队头指针队头指针 = 队尾指针队尾指针队头指针推进计算： 队头指针队头指针 = MOD（队头指针（队头指针+1，M）队尾指针推进计算： 队尾指针队尾指针 MOD（队尾指针（队尾指针+1，M）循环队列上的操作循环队列上的操

18、作插入插入（1）检查队列是否已满，若队满，则进行溢出错误处理；（2）将队尾指针后移一个位置（即加1），指向下一单元；（3）将新元素赋给存入以rear值为下标的数组元素中 ；SEQUEUE INCQUEUE(SEQUEUE CQ,DT x) if(CQ.rear+1)%M = CQ.front) printf(CQ is full!); elseCQ.rear=(CQ.rear+1)%M; CQ.dataCQ.rear=x; return（CQ）;循环队列上的操作循环队列上的操作删除删除（1）检查队列是否为空，若队空，则进行下溢错误处理；（2）将队首指针后移一个位置（即加1）；OUTCQUEUE

19、(SeQueue CQ) if(CQ.front=CQ.rear) printf(CQ is empty!); else CQ.front=(CQ.front+1)%M; return（CQ）; 3.2.4链队列及其操作链队列及其操作链存储结构存储的队列称为链队列，链栈的结点由结点数据和next指针构成。1，队列的链存储结构，队列的链存储结构 结点数据结点数据指针指针datanext链队列的结点类型： #define DT char； typedef struct qnode DT data； struct qnode *next； LINKNODE； 头结点头结点队尾结点队尾结点ABC.非空

20、链队非空链队队首结点队首结点队首指针队首指针队尾指针队尾指针为了操作方便，也给链队列添加一个头结点为了操作方便，也给链队列添加一个头结点typedef struct LINKNODE *front，*rear ； LINKQUEUE；定义一个链队列定义一个链队列一个链队列由一个头指针和一个尾指针唯一确定把结点链接起来形成一个单链表 链式队列在进队时无队满问题，但有队空问题空队列的判定条件是：头指针和尾指针都指向头结点空队列的判定条件是：头指针和尾指针都指向头结点 队首指针队首指针队尾指针队尾指针头结点头结点队队空的空的条条件件fornt= =NULL?front-next= =NULL? 空链

21、队列空链队列 队首指针队首指针 队尾指针队尾指针生成空链队列：生成空链队列：LINKQUEUE *INILQUEUE(LINKQUEUE * LQ) LQ-front=(LINKNODE *) malloc(sizeof(LINKNODE); LQ-front-data=#; LQ-front-next=NULL; LQ-rear=LQ-front; return(LQ);#3.2.4链队列及其操作链队列及其操作2链队列上的操作链队列上的操作 rearfrontxyp p 插入插入 INLQUEUE *(LINKQUEUE * LQ,DT x) LINKNODE *p; p=(LINKNODE *) malloc(sizeof(LINKNODE); p-data=x; p-next=NULL; LQ-rear-next=p; LQ-rear=p;return(LQ);3.2.4链队列及其操作链队列及其操作2链队列上