数据结构-栈和队列

数据结构第3章栈和队列

从数据结构上看，栈和队列也是线性表，不过是两种特殊的线性表。栈只允许在表的一端进行插入或删除操作，而队列只允许在表的一端进行插入操作、而在另一端进行删除操作。堆栈和队列在各种类型的软件系统中应用广泛。堆栈技术被广泛应用于编译软件和程序设计中，在操作系统和事务管理中广泛应用了队列技术。通过本章的学习，读者应能掌握栈和队列的逻辑结构和存储结构，以及栈和队列的基本运算以及实现算法。3.1栈3.2队列3.1栈

1、栈(Stack)的定义：

栈是一种特殊的线性表，限定仅在表的一端进行插入或删除操作的线性表。栈的插入操作通常称为入栈或进栈(push)，而栈的删除操作则称为出栈或退栈(pop)。当栈中无数据元素时，称为空栈。特点:

（1）只允许在一端插入和删除的顺序表（2）允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)

（3）后进先出(LIFO，lastinfirstout)第3章栈和队列

2、栈的存储结构：（1）顺序存储结构两种存储结构:

（2）链式存储结构

顺序栈：利用数组存放自栈底到栈顶的数据元素，附设指针top指示栈顶元素在顺序栈中的位置。

#defineMAXNUM<最大元素数>//栈的最大数据元素数目

typedefstruct{Elemtypestack[MAXNUM];//存放栈中数据元素的存储单元

inttop;//栈顶指针

}sqstack;

鉴于C语言中数组的下标约定是从0开始的，因而使用C语言的一维数组作为栈时，应设栈顶指针top=-1时为空栈。一般有：

s->top=s->base是为空栈。基本操作算法：（1）初始化栈操作

intinitStack(sqstack*s){/*创建一个空栈由指针S指出*/s=(sqstack*)malloc(sizeof(sqstack));if(s==NULL)

{returnFALSE；}else{s->top=s->base;returnTRUE;}}（2）进栈操作

intpush(sqstack*s,Elemtypex){/*将元素x插入到栈s中，作为s的新栈顶*/if(s->top>=MAXNUM-1)returnFALSE;/*栈满*/

s->stack[s->top]=x;s->top++;returnTRUE;}（3）出栈操作

intpop(sqstack*s){/*若栈s不为空，则删除栈顶元素*/if(s->top<0)returnNULL;/*栈空*/

s->top--;x=s->stack[s->top];returnx;}（4）取栈顶元素操作

intgettop(sqstack*s){/*若栈s不为空，则返回栈顶元素*/if(s->top<0)returnNULL;/*栈空*/

return(s->stack[--s->top]);}

注：取栈顶元素与出栈不同之处在于出栈操作改变栈顶指针top的位置，而取栈顶元素操作不改变栈的栈顶指针。（5）判断空操作

intEmpty(sqstack*s){//栈s为空时，返回为TRUE；

//非空时，返回为FALSE

if(s->top<0)returnTRUE;

returnFALSE;}

链式栈：若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。datanexttop栈顶栈底链栈示意图

typestructnode{//链栈的结点结构

ELEMTPdata;//栈的数据元素类型

structnode*next;//指向后继结点的指针

}SNode;基本操作算法：（1）建立一个空栈

StatusInitLStack(Linkstack&S){

S=NULL;

returnok;

}//InitLStack

（2）取栈顶元素

StatusGettopLStack(Linkstack&S,SElemType&e){

//若栈不为空，则用e返回S的栈顶元素，

//并返回OK,否则返回ERROR.

if(S==NULL)returnERROR;

e=S->data;

return(OK);

}//GettopLStack（3）入栈操作

voidPush(LinkStack*s，ELEMTPx){s=(LinkStack*)malloc(sizeof(LinkStack));s->data=x;s->next=top；top=s;

returntop;}（4）出栈操作

voidPop(LinkStack*s,ELEMTP*x){if(s==NULL)returnNULL;/*空栈*/else{

p=top;*x=p->data;top=p->next;free(p);

}returntop;}

例：十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：N=(Ndivd)×d+Nmodd(其中：div为整除运算，mod为求余运算）

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队列

1、队列（Queue）的定义：

队列是一种特殊的线性表，限定插入在线性表的一端进行，删除在线性表的另外一端进行。特点:

（1）只允许在一端插入，在另外一端删除的顺序表（2）允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)

（3）后进先出(FIFO，FirstinFirstOut)frontreara0

a1

a2

an-1

2、队列的存储结构：（1）顺序存储结构两种存储结构:

（2）链式存储结构

顺序队列：利用一组地址连续的存储单元依次将数据元素存放到队列中。附设一个为指向队头元素位置的指针front，另一个为指向队尾的元素位置的指针rear。

（1）进队时：队尾指针先进一rear=rear+1，再将新元素按rear指示位置加入。（2）出队时：队头指针先进一front=front+1，再将下标为front的元素取出。插入端和删除端都是浮动的。通常我们将插入端称为队尾，用“rear”指示；而删除端被称为队头，用“front”指示。frontrear空队列frontrearA进队AfrontrearB进队ABfrontrearC,D进队ABCDfrontrearA退队BCDfrontrearB退队CDfrontrearE,F,G进队CDEFGCDEFGfrontrearH进队,溢出

用C语言定义的顺序存储结构的队列如下：

#defineMAXNUM<最大元素数>//队列的最大数据元素数目

typedefstruct{ElemtypeQueue[MAXNUM];//存放队列中数据元素的存储单元

intrear,front;//队头队尾指针

}SeqQueue;SeqQueue*sq;Sq=newSeqQueue;

为了算法设计的方便，在此我们约定：初始化队列时，空队列时令front=rear=-1，当插入新的数据元素时，尾指示器rear加1，而当队头元素出队列时，队头指示器front加1。另外还约定，在非空队列中，头指示器front总是指向队列中实际队头元素的前面一个位置，而尾指示器rear总是指向队尾元素。基本操作算法：（1）初始化队列

intinitQueue(sqqueue*q){/*创建一个空队列由指针q指出*/q=(sqqueue*)malloc(sizeof(sqqueue))if(q==NULL)returnFALSE;

q->front=q->rear=0;returnTRUE;}（2）入队列操作

intappend(sqqueue*q,Elemtypex){/*将元素x插入到队列q中，作为q的新队尾*/if(q->rear>=MAXNUM-1)returnFALSE;/*队列满*/

q->rear++;q->queue[q->rear]=x;returnTRUE;}（3）出队列操作

Elemtypedelete(sqqueue*q){/*若队列q不为空，则返回队头元素*/Elemtypex;if(q->rear==q->front)returnNULL;/*队列空*/

x=q->queue[++q->front];returnx;}（4）取队头元素操作

ElemtypegetHead(sqqueue*q){/*若队列q不为空，则返回队头元素*/if(q->rear==q->front)returnNULL;/*队列空*/return(q->queue[s->front+1]);}（5）判队列非空操作

intEmpty(sqqueue*q){//队列q为空时，返回TRUE；

//否则返回FALSE

if(q->rear==q->front)returnTRUE;returnFALSE;}（6）求队列长度操作

intlength(sqqueue*q){/*返回队列q的元素个数*/

return(q->rear-q->front);}队满时再进队—>溢出队空时再出队—>队空

解决办法：将队列元素数组首尾相接，形成循环队列。在循环队列中，每插入一个新元素时，就把队尾指针沿顺时针方向移动一个位置。即：

q->rear=q->rear+1;if(q->rear==MAXNUM)q->rear=0;

在循环队列中，每删除一个元素时，就把队头指针沿顺时针方向移动一个位置。即：

q->front=q->front+1;if(q->front==MAXNUM)q->front=0;01234567front01234567front01234567frontrearAABCrearrear空队列A进队B,C进队0123456701234567A退队B退队01234567D,E,F,G,H进队frontBCrearAfrontBCrearfrontCrearDEFGH

假设为队列开辟的数组单元数目为MAX_QUEUE，在C语言中，它的下标在0~MAX_QUEUE-1之间，若增加队头或队尾指针，可以利用取模运算实现。如下：front=(front+1)%MAX_QUEUE；rear=(rear+1)%MAX_QUEUE；当front或rear为MAX_QUEUE-1时，上述两个公式计算的结果就为0。这样，就使得指针自动由后面转到前面，形成循环的效果。队空和队满的标志问题：队列变为空，队头和队尾指针相等。（1）初始化操作

StatusInitQueue(SqQueue*Q){//构造一个空队列Q

Q=(QElemType)malloc(MAXQSIZE*sizeof(QElemType))；

if(!Q)exit(OVERFLOW)；//存储分配失败

Q.front=Q.rear=0；

returnOK；

}（2）入队列操作

intEnQueue(SqQueue&Q，QElemTypee){//插入元素e为Q的新的队尾元素

if((Q.rear+1)％MAXQSIZE==Q.front)returnERROR；//队列满

Q.base[Q.rear]=e；

Q.rear=(Q.rear+1)％MAXQSIZE；

return1；

}（3）出队列操作

StatusDeQueue(SqQueue&Q，QElemType&e){//若队列不空，则删除Q的队头元素，

//用e返回其值，并返回1，否则返回ERRORif(Q.Front==Q.rear)returnERROR；

e=Q.base[Q.front]；

Q.front=(Q.front+1)％MAXQSIZE；

returnOK；

}（4）求循环队列长度

IntQueueLength(SqQueueQ){//返回Q的元素个数，即队列的长度

return(Q.rear–Q.front+MAXSIZE)%MAXQSIZE；

}

链式队列：用链表表示的队列。

（1）一个链队列需要两个指针，分别指示队头和队尾的指针——头指针和尾指针。

（2）给链队列添加一个头结点。空的链队列的判决条件为头指针和尾指针均指向头结点。frontrear（1）初始化操作

StatusInitQueue(LinkQ