《数据结构03栈和队列》由会员分享，可在线阅读，更多相关《数据结构03栈和队列（32页珍藏版）》请在金锄头文库上搜索。
1、,主要内容,教学要求,3.1.1栈的定义及其基本操作,栈：限定结点插入和删除只能在同一端进行的线性表,进栈,出栈,栈顶指针 (top),栈底指针 (bottom),栈顶元素,栈底元素,一个重要特点：,最后压入的结点最先弹出，最先压入的结点只能最后弹出,LIFO表(Last In First Out ),栈顶指针 (top),栈底指针(bottom),1.栈的定义,栈顶指针和栈底指针都等于0时，栈为空,2.栈的基本操作,3.1.2顺序栈及其操作,1.栈的顺序存储结构,顺序存储结构存储的栈称为顺序栈，用一个一维数组存储,栈顶指针不是指针类型，而是一个整数,C语言描述顺序栈,#define DT c
2、har #define M 100 typedef struct DT dataM; int top; SEQSTACK;,指示栈顶元素在顺序栈中的位置,顺序栈上的操作,创建栈,SEQSTACK INISTACK() SEQSTACK S; S.top =0; return(S); ,首先根据栈的数据类型说明一个栈S，再置栈顶指针为0,栈顶(top)=0,顺序栈上的操作,判栈空：设S是SEQSTACK类型的变量，栈底位置在向量的低端，stop=0表示空栈,栈顶指针top,指向实际栈底后的空位置，初值为0,压栈,.,B,C,D,E,F,栈满,弹栈,栈空,设数组大小为M top=0,栈空，此时出栈
3、，则下溢（underflow),注意：弹栈算法并未说明对删除了的结点的处置,设数组大小为M top=M,栈满，此时入栈，则上溢（overflow),压栈：stop是正向增加的，即进栈时需将stop加1,弹栈：退栈时需将stop 减1,顺序栈上的操作,读栈,把栈S的栈顶结点数据读出作为函数的返回值,返回值,读栈,char GETSTACK(SEQSTACK S) if (S.top=0) printf(“empty!“); return 0; else return（S.dataS.top）; ,S.dataS.top,注意：该算法并未改变栈的状态，即已读出的结点仍保存在原处不变,3.1.3链栈
4、及其操作,1.栈的链存储结构,链存储结构存储的栈称为链栈，链栈的结点由结点数据和next指针构成。,链栈的结点类型： #define DT char typedef struct snode DT data; struct snode *next; STACKNODE;,结点通过next指针链接起来,链栈的结点数据,data,next,插入和删除总是在链的头部进行，所以头指针也是栈顶指针,注意: 链栈中指针的方向,top为栈顶指针，始终指向当前栈顶元素前面的头结点,栈名、链头指针、栈顶指针,定义一个链栈 STACKNODE *top,3.1.3链栈及其操作,1.链栈上的操作,新结点,STACK
5、NODE *PUSLSTACK(STACKNODE *LS,char x) STACKNODE *q; q=(STACKNODE *)malloc(sizeof(STACKNODE); q-data=x; q-next=LS; LS =q; return(LS); ,压栈,链栈无栈满问题，空间可扩充。插入与删除仅在栈顶处执行,3.1.3链栈及其操作,弹栈,STACKNODE *POPLSTACK(STACKNODE *LS) STACKNODE *q; if(LS = NULL) printf(“Empty!“); else q=LS; LS = q-next; free(q); return
6、(LS); ,q=NULL,返回n,3.1.3链栈及其操作,求栈长度,int SIZELSTACK(STACKNODE *LS) int n=0; STACKNODE *q; for(q=LS;q!=NULL;q=q-next) n+; return(n); ,统计链栈LS中当前所含结点个数,LS,3.1.4栈结构的应用,数值转换的应用,一个简单算法是逐次除以基数 d 取余法。如10进制数到2进制数的转换（d2）。,例： (67)10=(100011)2，其运算过程如下：,N N div 2 N mod 2 67 33 1 33 16 1 16 8 0 8 4 0 4 2 0 2 1 0 1
7、0 1,商为 0 时得到的余数是 Bn 的最高位,3.1.4栈结构的应用,void DTOB(int n) SEQSTACK NS; int x=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“); ,67,1,1,1
8、,0,33,16,8,4,0,2,0,1,0,0,Push(S, N%2),1000011,数值转换的应用,3.1.4栈结构的应用,计算算术表达式的应用这是栈应用的典型例子,无括号算术表达式求值（中缀表达式直接求值 ） (1)规定优先级表； (2) 设置两个栈：DNS(运算数栈)和OPS(运算符栈)； (3) 自左向右扫描，遇操作符则与OPS栈顶优先级比较： 当前操作符OPS栈顶则进OPS栈； 当前操作符 OPS栈顶，DNS栈顶、次顶和OPS栈顶，退栈形成运算， 运算结果进DNS栈。,例：实现5+4*78/2#的运算过程时栈区变化情况,5 + 4 7 8 / 2 #,#,5,+,4,7,28,
9、8,33,/,2,4,29,3.2队列,3.2.1 队列的定义及其基本操作,队列的定义,限定在表的一端插入、另一端删除。,队列：线性表 (queue),先进先出 (FIFO结构)。,队尾,队头,2.队列的基本操作,3.2.2顺序队列及其操作,1.队列的顺序存储结构,顺序存储结构存储的队列称为顺序队列，用一个一维数组存储,#define DT char #define M 100 typedef struct DT dataM； int front，rear； SEQUEUE;,C语言描述顺序栈,队头、队尾指针不是指针类型，而是数组元素下标,队头指针始终指向队头结点的前一个结点位置,队尾指针总是
10、指向队尾结点位置,队头、队尾指针初始值为0,顺序队列上的操作,头尾 指针,初始化时的初始值均应置为 0。,入队，尾指针增 1,出队，头指针增 1,头尾指针相等，队列为空 队尾指针=M，队列满 M为队列当前容量,a,b,c,设两个指针front,rear,约定： rear指示队尾元素； front指示队头元素前一位置 初值front = rear = 0,空队列条件：front=rear 入队列：sq+rear=x; 出队列：x=sq+front;,存在问题 设数组维数为M，则： 当front=0,rear=M时，再有元素入队发生溢出真溢出 当front 0,rear=M时，再有元素入队发生溢出
11、假溢出,front,“假溢出”队列的存储空间未满，却发生了溢出,解决“假溢出”的问题有两种可行的方法：,(1) 平移元素：把元素平移到队列的首部。 效率低,(2) 将新元素插入到第一个位置上，构成循环队列，入队和出队仍按“先进先出”的原则进行。 操作效率、空间利用率高,d,e,f,3.2.3循环队列及其操作,循环队列是把顺序队列的头尾相接形成一个圆环；逻辑上把1号结点作为M号结点的后继结点处理,基本思想：把队列设想成环形，让LQ0接在LQM-1之后，若rear+1=M,则令rear=0; 实现：利用“模”运算 入队： rear=(rear+1)%M; LQrear=x; 出队： front=(
12、front+1)%M; x=LQfront;,初始状态,队空： front=rear,队满、队空判定条件,队满： front=rear,仅凭 front = rear 不能判定队列是空还是满,解决方案： 1.另外设一个标志以区别队空、队满 2.少用一个元素空间： 队空：front=rear 队满：(rear+1)%M=front 循环队列初始条件： 队头指针 = 队尾指针 = 0 循环队列满条件： MOD（队尾指针+1,M） = 队头指针 循环队列空条件： 队头指针 = 队尾指针 队头指针推进计算： 队头指针 = MOD（队头指针+1，M） 队尾指针推进计算： 队尾指针 MOD（队尾指针+1，
13、M）,循环队列上的操作,插入,（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）
14、；,OUTCQUEUE(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，队列的链存储结构,data,next,链队列的结点类型： #define DT char； typedef struct qnode DT data； struct qnode *next； LINKNODE；,为了操作方便，也给链队列添加一个头结点,typedef st
15、ruct LINKNODE *front，*rear ； LINKQUEUE；,定义一个链队列,一个链队列由一个头指针和一个尾指针唯一确定,把结点链接起来形成一个单链表,链式队列在进队时无队满问题，但有队空问题,空队列的判定条件是：头指针和尾指针都指向头结点,队空的条件 fornt= =NULL? front-next= =NULL?,空链队列,生成空链队列： 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链队列上的操作,rear,front,x,y,p,p,插入,INLQUEUE *(LINKQUEUE * LQ,DT x) LINKNODE *p; p=(LINKNODE *) malloc(sizeof(LINKNODE); p-data=x; p-
