数据结构PPT(第3章 栈和队列)

第3章栈和队列学习要点

从数据结构上看，栈和队列也是线性表，不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除操作，而队列只允许在表的一端进行插入操作、而在另一端进行删除操作，栈和队列也可以被称作为操作受限的线性表。通过本章的学习，应掌握栈和队列的逻辑结构和存储结构，以及栈和队列的基本运算以及实现算法。3.1栈什么是栈？

释义：供储存货物的建筑物。设想有一个直径不大、一端开口一端封闭的竹筒。有若干个写有编号的小球，小球的直径比竹筒的直径略小。现在把不同编号的小球放到竹筒里面，可以发现一种规律：先放进去的小球只能后拿出来，反之，后放进去的小球能够先拿出来。3.1栈1000：×××1001：×××1002：×××1003：×××1004：call20001005：×××1006：×××1007：×××1008：ENDS2000：×××2001：×××2002：×××2003：call30002004：×××2005：×××2006：RET3000：×××3001：×××3002：×××3003：×××3004：call40003005：×××3006：RET4000：×××4001：×××4002：×××4003：×××4004：×××4005：×××4006：×××4007：RET主程序子程序1子程序2子程序3(a1,a2,...,ai-1,ai

,ai+1,…,an)插入删除3.1栈

栈是限定仅能在表的一端进行插入、删除操作的线性表。能进行插入和删除的一端为栈顶（top），另一端为栈底（bottom）。

称插入操作为进栈，删除操作为出栈。进栈出栈操作只能在栈顶进行。栈顶栈底第一个进栈的元素在栈底；最后一个进栈的元素在栈顶；第一个出栈的元素为栈顶元素；最后一个出栈的元素为栈底元素。栈的特点后进先出(LIFO)出栈进栈栈的示意图an：：a2a11.初始化操作InitStack(&S)

功能：构造一个空栈S2.销毁栈操作DestroyStack(&S)

功能：销毁一个已存在的栈3.置空栈操作ClearStack(&S)

功能：将栈S置为空栈4.取栈顶元素操作GetTop(S,&e)

功能：取栈顶元素，并用e返回栈的基本操作5.进栈操作Push(&S,e)

功能：元素e进栈6.出栈操作Pop(&S,&e)

功能：栈顶元素退栈，并用e返回7.判空操作StackEmpty(S)

功能：若栈S为空，则返回True，否则返回False栈的基本操作栈的表示和实现——顺序存储#defineSTACK_INIT_SIZE100//栈存储空间的初始分配量

#defineSTACKINCREMENT10//栈存储空间的分配增量

typedef

struct{

SElemType*base;//栈空间基址

SElemType*top;//栈顶指针

intstacksize;//当前分配的栈空间大小

}SqStack;

SqStackS;//S是存放栈的结构变量栈的表示和实现说明

base称为栈底指针，始终指向栈底；当base=NULL时，表明栈结构不存在。

top为栈顶指针

top的初始值指向栈底，即top=base

空栈：当top=base时为栈空的标记当栈非空时，top的位置是指向当前栈顶元素的下一个位置

stacksize——当前栈可使用的最大容量S.stacksizeS.topS.base10099nn-1n-210anan-1a2a1约定栈顶指针指向栈顶元素的下一个位置当栈用顺序结构存储时，栈的基本操作如建空栈、进栈、出栈等如何实现？？顺序栈的图示baseAABCDEAB空栈A进栈BCDE进栈EDC出栈顺序栈的操作图示topbasetopbasebasetoptop初始化操作InitStack(SqStack&S)

参数：S是存放栈的结构变量功能：建一个空栈SS.stacksizeS.topS.base10099nn-1n-210顺序栈的基本操作初始化操作算法StatusInitStack(SqStack&S){

S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));//为顺序栈动态分配存储空间

if(!S.base)exit(OVERFLOW);//存储分配失败

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;

returnOK;

}//InitStack顺序栈的基本操作

销毁栈操作

DestroyStack(SqStack&S)

功能：销毁一个已存在的栈顺序栈的基本操作99nn-1n-210anan-1a2a1S.stacksizeS.topS.base100NULL0NULL销毁操作算法StatusDetroyStack(SqStack&S){if(!S.base)returnERROR;//若栈未建立(尚未分配栈空间)

free(S.base);//回收栈空间

S.base=S.top=NULL;

S.stacksize=0;

returnOK;

}//DetroyStack顺序栈的基本操作置空栈操作ClearStack(SqStack&S)

功能：将栈S置为空栈顺序栈的基本操作99nn-1n-210anan-1a2a1S.stacksizeS.topS.base100S.stacksizeS.topS.base99nn-1n-210anan-1a2a1100置空置空操作算法StatusClearStack(SqStack&S){if(!S.base)returnERROR;//若栈未建立(尚未分配栈空间)

S.top=S.base;

returnOK;

}//ClearStack顺序栈的基本操作取栈顶元素操作GetTop(SqStackS,SElemType&e)

功能：取栈顶元素，并用e返回顺序栈的基本操作99nn-1n-210anan-1a2a1S.stacksizeS.topS.base100ean取栈顶元素操作算法StatusGetTop(SqStackS,SElemType&e){if(S.top==S.base)returnERROR;//栈空

e=*(S.top-1);

returnOK;

}//GetTop顺序栈的基本操作

进栈操作Push(SqStack&S,ElemTypee)

功能：元素e进栈顺序栈的基本操作99nn-1n-210anan-1a2a1S.stacksizeS.topS.base100e元素进栈S.stacksizeS.topS.base99nn-1n-210anan-1a2a1100e进栈操作算法StatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){//栈满，追加存储空间

S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base)exit(OVERFLOW);//存储分配失败

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;}

*S.top++=e;//*S.top=e；S.top++;

returnOK;}//Push顺序栈的基本操作

出栈操作Pop(SqStack&S,ElemType&e)

功能：栈顶元素退栈，并用e返回顺序栈的基本操作栈顶元素进栈99nn-1n-210anan-1a2a1S.stacksizeS.topS.base100S.stacksizeS.topS.base99nn-1n-210anan-1a2a1100ean出栈操作算法StatusPop(SqStack&S,ElemType&e){if(S.top==S.base)returnERROR;//栈空

e=*--S.top;//--S.top;

e=*S.top;

returnOK;

}//Pop顺序栈的基本操作在前面学习了线性链表的插入、删除操作算法，不难写出链式栈初始化、进栈、出栈等操作的算法。DatanextS栈顶栈底an-2a1an-1an栈的表示和实现——链式存储不带头结点的单链表，其插入和删除操作仅限制在表头位置上进行。链表的头指针即栈顶指针。栈的表示和实现——链式存储插入操作：p->next=s；s=p。删除操作：q=s；s=s->next；free(q)。s栈顶栈底anan-1……a1∧1.数制转换p48算法3.12.行编辑程序p50算法3.23.表达式求值p53~p54算法3.43.2栈的应用举例

数制转换

N=(N/d)×d+N%d(d代表d进制数)

例如：(1348)10=(2504)8

，其运算过程如下：

NN/8N%8

13481684

168210

2125

202输出顺序计算顺序voidconversion(){InitStack(S);

scanf("%d",&N);while(N){Push(S,N%8);N=N/8;}while(!StackEmpty(S)){Pop(S,e);

printf("%d",e);}}//conversion3.2栈的应用举例(a1,a2,...,ai-1,ai

,ai+1,…,an)插入删除3.4队列什么是队列?

队列是限定仅能在表头进行删除，表尾进行插入的线性表，能进行插入的一端称为队尾，能进行删除的一端称为队头。称插入操作为入队，删除操作为出队。

a1

a2

a3…………an队头队尾出队列第一个入队的元素在队头最后一个入队的元素在队尾第一个出队的元素为队头元素最后一个出队的元素为队尾元素进队列队列的特点先进先出

(FIFO)

队列的示意图

队列的基本操作1.初始化操作InitQueue(&Q)

功能：构造一个空队列Q2.销毁操作DestroyQueue(&Q)

功能：销毁已存在队列Q

3.置空操作ClearQueue(&Q)

功能：将队列Q置为空队列4.判空操作QueueEmpty(Q)

功能：若队列Q为空，则返回True，否则返回False

队列的基本操作5.取队头元素操作GetHead(Q,&e)

功能：取队头元素，并用e返回6.入队操作EnQueue(&Q,e)

功能：将元素e插入Q的队尾7.出队操作DeQueue(&Q,&e)

功能：删除Q的队头元素空链队列Q.frontQ.rear∧链队列——队列的链式表示和实现∧J1J2JnQ.frontQ.rear非空链队列1.链队列表示2.链队列的类型定义

typedef

struct

QNode{//链队列结点的类型定义

QElemTypedata;

struct

QNode*next;}QNode,*QueuePtr;

typedef

struct{//链队列的表头结点的的类型定义

QueuePtrfront;//队头指针，指向链表的头结点

QueuePtrrear;//队尾指针，指向队尾结点

}LinkQueue;链队列——队列的链式表示和实现3.链队列的有关操作空队Q.frontQ.rear∧XQ.front∧Q.rearX入队YQ.front∧Q.rearY入队XYQ.front∧Q.rearX出队XY出队Q.frontQ.rear∧链队列——队列的链式表示和实现链队列初始化StatusInitQueue(LinkQueue&Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);Q.front->next=NULL;returnOK;}链队列的有关操作Q.frontQ.rear∧链队列的销毁StatusDestroyQueue(LinkQueue&Q){while(Q.front){Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;}returnOK;}链队列的有关操作链队列的插入(入队)StatusEnQueue(LinkQueue&Q,QElemTypee){p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);p->data=e; p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}链队列的有关操作链队列的删除(出队)StatusDeQueue(LinkQueue&Q,ElemType&e){if(Q.front==Q.rear)returnERROR; p=Q.front->next; e=p->data; Q.front->next=p->next; if(Q.rear==p)Q.rear=Q.front; free(p); returnOK;}链队列的有关操作

判断链队列是否为空StatusQueueEmpty(LinkQueueQ){ if(Q.front==Q.rear)returnTrue; returnFalse;}

取链队列的第一个元素结点StatusGetHead(LinkQueue

Q,QElemType&e){ if(QueueEmpty(Q))returnERROR; e=Q.front->next->data; returnOK;}链队列的有关操作

队列的顺序存贮结构#defineMAXSIZE100//最大队列长度

typedef

struct{

QElemType*base;//初始化时动态分配存储空间的基址

int

front;//队头指针，指向队头元素

intrear;//队尾指针，指向队尾元素的下一个位置}SqQueue;循环队列——队列的顺序表示和实现初始状态为front=rear=0；每插入一个元素尾指针增1，每删除一个元素，头指针增1。顺序队列的有关操作空队列Q.front012345Q.rearJ1J2J3J1,J2和J3相继入队列012345Q.frontQ.rearQ.frontJ3J1,J2相继出队列012345Q.rearJ3J4,J5,J6相继入队列012345Q.frontJ4J5J6Q.rear此时又有J7入队,该怎么办？

？进队时，将新元素按Q.rear指示位置加入，再将队尾指针增1，Q.rear=Q.rear+1。

出队时，将下标为Q.front的元素取出，再将队头指针增1，Q.front=Q.front+1。

队满时再进队将溢出出错；队空时再出队作队空处理。上图为“假溢”。有关操作具体说明什么叫“假溢出”？如何解决？在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。解决假溢出的途径———采用循环队列将顺序队列假想为一个环状的空间。队空、队满都有Q.front=Q.rear如何判断循环队列队空、队满？

？循环队列Q.frontQ.rearJ6J4J53

124

05J7Q.rear54

03

12Q.frontJ6J7J8J9J4J5队满Q.rearQ.front540312队空解决方法1.

另设一个标志位tag让删除动作使其为1，插入动作使其为0，tag=1时，导致front=rear为队空；tag=0时，导致front=rear则为队满。2.

用一个计数器记录队列中元素的总数(即队列长度)；3.

少用一个存储单元，队满条件：Q.front=Q.rear+1。队头、队尾指针加1，可用取模(余数)运算实现。队头指针进1:Q.front=(Q.front+1)%MAXSIZE;

队尾指针进1:Q.rear=(Q.rear+1)%MAXSIZE;

队列初始化：Q.front=Q.rear=0;

队空条件：Q.front==Q.rear;

队满条件：(Q.rear+1)%MAXSIZE==Q.front;

队列长度：(Q.rear-Q.front+MAXSIZE)%MAXSIZE。有关循环队列操作说明初始化操作InitQueue_Sq(SqQueue&Q)

功能：建一个空队列Q

算法：StatusInitQueue_Sq(SqQueue&Q){

//构造一个空队列Q

Q.base=(ElemType*)malloc(MAXSIZE*sizeof(ElemType));

if(!Q.base)exit(OVERFLOW);//存储分配失败

Q.front=Q.rear=0;

returnOK;}//InitQueue_Sq循环队列操作Q.frontQ.rear540312

入队操作EnQueue_Sq(SqQueue&Q,ElemTypee)

功能：将元素e插入队尾循环队列操作Q.frontQ.rear54

03

12J1J3J2eQ.frontQ.rear54

03

12J1J3J2元素e入队前元素e入队后入队操作算法StatusEnQueue_Sq(SqQueue&Q,ElemTypee)

{if((Q.rear+1)%MAXSIZE==Q.front)returnERROR;//队满

Q.base[Q.rear]=e;//将元素e插入队尾

Q.rear=(Q.rear+1)%MAXSIZE;//修改队尾指针

returnOK;

}//EnQueue_Sq循环队列操作

出队操作

DeQueue_Sq(SqQueue&Q,QElemType&e)

功能：删除队头元素，用e返回其值循环队列操作Q.frontQ.rear54

03

12J1J3J2出队操作前Q.frontQ.rear54

03

12J1J3J2出队操作后eJ1出队操作算法

StatusDeQueue_Sq(SqQueue&Q,ElemType&e)

{//删除队头元素，用e返回其值，并返回OK；否则返回ERRORif((Q.rear==Q.front)returnERROR;//队空

e=Q.