《软件技术基础》课件第4章

4.1栈4.2队列习题4第4章栈和队列4.1.1栈的定义及基本运算

栈(Stack)是限定仅在表的一端进行插入或删除操作的线性表。插入、删除的一端称为栈顶(Top)，另一端称为栈底(Bottom)。不含任何元素的空表称为空栈。

对于非空栈S=(a1,a2,…,an)，a1是栈底元素，an是栈顶元素。如图4.1所示，进栈的顺序是a1,a2,…,an，出栈的顺序正好相反。因此，栈是一种后进先出的(LastInFirstOut)的线性表。

4.1栈图4.1栈示意图栈的常用基本运算有以下六种：

(1) InitStack(&S)——栈初始化，构造一个空栈S。

(2) SetNull(S)——置空栈，将栈S清为空栈。

(3) Empty(S)——判断栈空，若栈S为空，则返回“真”值；否则返回“假”值。

(4) Push(S，e)——进栈，若栈S不满，则将数据元素e插入栈顶。

(5) Pop(S,&e)——出栈，若栈S非空，则删除栈顶数据元素，并返回该数据元素。

(6) GetTop(S)——取栈顶元素，若栈S非空，则返回栈顶数据元素。该操作完成后，栈的内容不变。4.1.2栈的顺序存储结构

栈的顺序存储结构简称为顺序栈。顺序栈采用向量来存储，并且用一个整型量Top指示当前栈顶的位置，我们不妨把Top称为栈顶指针。顺序栈的类型定义如下：

typedefstruct

{ datatypedata[maxsize];

intTop;

}SeqStack;

其中，maxsize是向量空间的长度，datatype是栈中元素的类型。设S是指向SeqStack结构体类型数据的指针，与顺序表类似，我们也可以规定下标为0的向量元素不用，那么S->data[1]是栈底元素，S->data[S->Top]是栈顶元素。当S->Top≤0表示空栈，而当S->Top=maxsize-1时，表示栈满。对于顺序栈，入栈时要先判断栈是否已满，栈满简称为“上溢”；出栈时需判断栈是否为空，栈空简称为“下溢”。图4.2说明了栈中元素和栈顶指针之间的关系。图4.2栈中元素和栈顶指针之间的关系在顺序栈上实现栈的基本运算的具体算法如下：

(1)栈的初始化(建立一个空顺序栈)。

算法4.1

建立空顺序栈。

voidInitStack(SeqStack*&S)

//构造一个空栈S

{S=(SeqStack*)malloc(sizeof(SeqStack));

S->Top=0;

}

(2)置空栈。

算法4.2

顺序栈置空。

voidSetNull(SeqStack*S)

//将栈S置为空栈

{S->Top=0;

}在同时使用两个或多个顺序栈时，为了避免某个栈发生上溢，而其余栈还有很多未用空间的情况出现，如果使这些栈共享同一向量空间，相互之间调剂余缺，则既节约了存储空间，又降低了发生上溢的概率。下面以两个顺序栈共享同一个向量空间的情况为例进行讨论。

两个栈共享一个向量空间的结构类型定义如下：

typedefstruct

{ datatypev[maxsize];

intTop1,Top2;

}SeqStack;

SeqStack*S=(SeqStack*)malloc(sizeof(SeqStack));将两个栈的栈底分别固定在向量空间的两端，栈顶向中间延伸，未用空间在向量的中部，如图4.3所示。只有当两个栈占满整个向量空间时(S->Top1+1等于S->Top2)，才会发生上溢。图4.3两个栈共享一个向量空间出栈操作的算法：

datatypepop(SeqStack*S,inti)

//i号栈的栈顶元素出栈

{datatypex;

if(i==1)if(S->Top1==-1)printf(“1号栈下溢”);

else{x=S->v[S->Top1];S->Top1--;}//1号栈出栈

elseif(S->top2==maxsize)printf(“2号栈下溢”);

else{x=S->v[S->Top2];S->Top2++;}//2号栈出栈

returnx;

}4.1.3栈的链式存储结构

栈的链式存储结构称为链栈，如图4.4所示。链栈是操作受限的单链表，即插入和删除操作都是在表头进行的。与顺序栈不同，链栈不会发生上溢。

请结合类型定义和算法自行分析为什么在链栈中没有设置头结点。图4.4链栈示意图链栈的结构类型定义如下：

typedefstructnone{

datatypedata;

structnode*next;

}StackNode;

typedefstruct{

StackNode*Top;

}LinkStack;链栈基本运算的主要算法描述如下：

(1)栈初始化。

算法4.7建立空链栈。

voidInitStack(LinkStack*&S)

//构造一个空栈S

{S=(LinkStack*)malloc(sizeof(LinkStack));

S->Top=NULL;

}

(2)置空栈。

算法4.8

链栈置空。

voidSetNull(LinkStack*S)

//使栈S置为空栈

{S->Top=NULL;

}

(3)进栈。

算法4.9链栈进栈。

voidPush(LinkStack*S,datatypee)

//使元素e进栈

{StackNode*p=(StackNode*)malloc(sizeof(StackNode));

p->data=e;

p->next=S->Top;//将新结点*p插入栈顶

S->Top=p;

}

链栈不会出现“上溢”的情况，所以在入栈操作时不需要判断栈是否已满。

【例4.1】数制转换。

将一个非负的十进制整数转换为其它进制数(二、八、十六进制)，利用栈来实现。

分析：采用除基数取余的方法。例如(1348)10=(2504)8，其运算过程如下：采用栈存放余数，入栈顺序：4、0、5、2，出栈顺序：2、5、0、4。

while(!EmptyStack(S))

{bit=Pop(S); //余数出栈

if(bit>9)printf(“%c”,bit+55);//将余数转为字符输出

elseprintf(“%c”,bit+48);

}

printf(“\n”);

}

【例4.2】算术表达式的求值。

设表达式中只有+、-、*、/、圆括号和操作数。运算符间的优先级关系如下：

(1)先乘除后加减；

(2)先括号内后括号外，即“(”与“)”优先级相同，但低于括号内的运算符，高于括号外的运算符；

(3)表达式起始、结束符“#”的优先级总是最低。

为实现运算符优先算法，需设置操作数栈和运算符栈。操作数栈OPND存放操作数或运算结果及中间结果；运算符栈OPTR存放运算符。算法的基本思想是：

(1)置操作数栈为空栈，表达式起始符“#”作为运算符栈的栈底元素；

(2)依次读入表达式中的每个字符，若是操作数，则进操作数栈，若是运算符，则与运算符栈的栈顶运算符比较优先级后作相应操作，直至整个表达式求值完毕(即运算符栈的栈顶元素和当前读入的字符均为“#”)。算法中还调用了两个函数：Precede用于判断运算符栈顶元素与当前读入的运算符的优先级关系；Operate进行二元运算aopb。4.2.1队列的定义及基本运算

队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，该端称为队尾(Rear)；在表的另一端进行删除，该端称为队头(Front)。

当队列中没有元素时，称为空队列。队列亦称做先进先出(FirstInFirstOut)的线性表，简称为FIFO表。设队列中的元素为a1,a2,…,an，则a1是队头元素，an是队尾元素。队列中的元素都是按照a1,a2,…,an的顺序依次入队和出队。图4.5是队列的示意图。4.2队列图4.5队列示意图队列的基本运算有：

(1) InitQueue(&Q)——队列初始化，构造一个空队列Q。

(2) SetNull(Q)——置空队，将队列Q清空。

(3) Length(Q)——求队列长度，返回队列中元素的个数。

(4) Empty(Q)——判空队，若队列Q为空队列，则返回“真”值；否则返回“假”值。

(5) EnQueue(Q,x)——入队，若队列Q非满，则将元素x插入Q的队尾。

(6) DeQueue(Q)——出队，若队列Q非空，则删除队头元素，返回Q的队头元素。

(7) GetFront(Q)——取队头元素，若队列Q非空，则返回Q的队头元素，Q中元素保持不变。4.2.2队列的顺序存储结构

队列的顺序存储结构称为顺序队列，采用向量存储队列中的元素。在非空队列中，队头指针front指向队头元素的前一个位置，队尾指针rear指向队尾元素的位置。如果是空队，则队头、队尾指针相等。顺序队列的结构类型定义如下：

typedefstruct{

datatypedata[maxsize];

intfront;

intrear;

}SeQueue;

SeQueue*sq=(SeQueue*)malloc(sizeof(SeQueue));

顺序队列中的出队、入队操作如图4.6所示。图4.6顺序队列的操作顺序队列中可能出现“上溢”和“下溢”现象，并且还存在“假上溢”现象，也就是说，尽管队列的向量空间未被占满，但尾指针已达到向量空间的上界而不能进行入队操作。例如在图4.6(c)、(d)的情况下，再进行入队操作，则出现“假上溢”。

采用循环队列(CircularQueue)的方法可以较好地解决“假上溢”问题，即将向量空间看做一个首尾相接的圆环，如图4.7所示。在循环队列中通过取模运算修改队尾指针和队头指针，具体描述为

sq->rear=(sq->rear+1)%maxsize;

sq->front=(sq->front+1)%maxsize;图4.7循环队列在循环队列中，入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针。由图4.8我们可以看出，在队空和队满时都有sq->front等于sq->rear的情况，无法区分空队和满队。图4.8无法区分循环队列的空队和满队通常采用少用一个元素空间的方法来解决这个问题，如图4.9所示。图4.9少用一个元素空间以区分循环队列的空队和满队判断空队和满队的条件分别是：

sq->rear==sq->front

sq->front==(sq->rear+1)%maxsize

下面我们用上述方法来实现循环队列上的基本运算。

(1)队列初始化。

算法4.11建立空循环队列。

voidInitQueue(SeQueue*&sq)

//建立空循环队列sq

{ sq=(SeQueue*)malloc(sizeof(SeQueue));

sq->front=sq->rear=0;

}

(2)置空队。

算法4.12循环队列置空。

voidSetNull(SeQueue*sq)//置队列sq为空队

{sq->front=sq->rear=0;

}

(3)求队列长度。

算法4.13求循环队列长度。

intLength(SeQueue*sq)

{return(sq->rear-sq->front+maxsize)%maxsize;

}

(4)入队。

算法4.14循环队列入队。

intEnqueue(sequeue*sq,datatypex)

//将新元素x插入队列*sq的队尾，入队成功返回1，不成功返回0

{if(sq->front==(sq->rear+1)％maxsize)

{printf(“队列上溢”);return(0);}

else{sq->rear=(sq->rear+1)％maxsize;

sq->data[sq->rear]=x;

return(1);

}

}4.2.3队列的链式存储结构

队列的链式存储结构简称为链队列，它是仅限在表头删除和表尾插入的单链表。为了便于在表尾做插入操作，需要增加一个尾指针，指向单链表中的最后一个结点。我们将链队列的头指针和尾指针封装在一起，作为一个结构体类型。下面是其类型定义：

typedefstructnode

{datatypedata;

structnode*next;

}QueueNode;//链队列的结点类型

typedefstruct

{QueueNode*front,*rear;

}LinkQueue;//头、尾指针的结构体类型为了运算方便，链队列中通常也带有头结点。图4.10给出了链队列的示意图，图中q为LinkQueue类型的指针。图4.10链队列链队列不会出现队满的情况，下面是链队列基本运算的实现方法。

(1)队列初始化。

算法4.17建立空链队列。

voidInitQueue(LinkQueue*&q)

{q=(LinkQueue*)malloc(sizeof(LinkQueue));

//产生头、尾指针结构体

q->front=q->rear=(QueueNode*)malloc(sizeof(QueueNode));

//产生头结点

q->front->next=NULL;//头结点指针域置空

}

(2)置空队。

算法4.18链队列置空。

voidSetNull(LinkQueue*q)

{q->rear=q->front;//尾指针也指向头结点

q->front->next=NULL;//头结点指针域置空

}

(3)判队空。

算法4.19链队列判空队。

intEmpty(LinkQueue*q)

{if(q->front==q->rear)return(1);

elsereturn(0);

}

(4)入队。

算法4.20链队列入队。

voidEnQueue(LinkQueue*q,datatypex)

//将新元素x加入链队列*q

{q->rear->next=(QueueNode*)malloc(sizeof(QueueNode));//新结点插入队尾

q->rear=q->rear->next;//尾指针指向新结点

q->rear->data=x;

//给新结点赋值

q->rear->next=NULL;//队尾结点的指针域置空

}

链队列不会出现“上溢”的情况，不需要判断队满。

(5)出队。

算法4.21链队列出队。

intDeQueue(LinkQueue*q,datatype&x)

//通过参数x带回该元素值，出队成功返回1，不成功返回0

{QueueNode*s;

if(Empty(q)){printf(“队列下溢”);return(0);}

else{s=q->front->next;//s指向被删除的队头结点

if(s->next==NULL){

//当前链队列的长度等于1，出队后为空队

q->front->next=NULL;q->rear=q->front;//置为空队

}

elseq->front->next=s->next;

//队列的长度大于1，修改头结点的指针域

x=s->data;

free(s);//释放被删除的结点空间

return(1);

}

}

(6)取队头元素。

算法4.22取链队列的队头元素。

intGetFront(LinkQueue*q,datatype&x)

//通过参数x带回队头元素值，取队头元素成功，返回1，不成功，返回0

{if(Empty(q)){printf(“队列下溢”);return(0);}

else{x=q->front->next->data;

return(1);

}

}

【例4.3】用带有头结点的循环链表表示队列，并且只设队尾指针rear，编写入队和出队算法。

分析：可以将rear->next->next看做队头指针。根据队列长度的不同，出队操作需考虑出队之前队列为空队、长度等于1和大于1三种不同的情况。

(1)入队算法。

voidEnQueue(QueueNode*&rear,datatypex)

{ QueueNode*p;

p=(QueueNode*)malloc(sizeof(QueueNode));

p->data=x;

p->next=rear->next;

rear->next=p;

rear=p;

}

(2)出队算法。

intDelQueue(QueueNode*&rear,datatype&x)

{QueueNode*p;

if(rear==rear->next){printf(“队列下溢”);return(0);}

else{

p=rear->next->next;x=p->data;

if(p==rear){

rear=rear->next;rear->next=rear;

}//原队列长度等于1

elserear->next->next=p->next;//原队列长度大于1

free(p);

return(1);

}

}

【例4.4】利用两个顺序栈s1、s2以及栈的基本运算实现队列的入队、出队和判断队列是否为空的运算。

分析：由于栈的特点是后进先出，为了实现先进先出的队列顺序，必须用两个栈，一个栈(s1)用于存放队列中的所有元素，另一个栈(s2)在出队时使用。入队操作时，只是将元素压入s1栈；出队操作时，先使s1栈中的所有元素出栈，并进入s2栈，这样才能达到模拟队列的效果。假设顺序栈s1、s2的向量空间长度分别为m，具体算法如下：

voidenqueue(SeStack*s1,datatypex)//入队

{

if(s1->Top==m)printf(“队列上溢!”);

elsePush(s1,x);

}

datatypedequeue(SeStack*s1)//出队

{

SeStack*s2;datatypex;

InitStack(s2);

while(!Empty(s1))Push(s2,Pop(s1));

x=Pop(s2);

while(!Empty(s2))Push(s1,Pop(s2));

}

intqueue_empty(SeStack*s1)//判队空

{

if(Empty(s1))return(1);

elsereturn(0);

}

一、名词解释

栈，顺序栈，链栈，队列，顺序队列，循环列队，链队

二、填空题

1．栈修改的原则是_________，因此，栈又称为________线性表。在栈顶进行插入运算，被称为________，在栈顶进行删除运算，被称为________。

2．对于顺序栈而言，top=0表示________，此时作退栈运算，则产生“________”；top=stack_maxsize-1表示________，此时作进栈运算，则产生“________”。习题4

3．以下运算实现在顺序栈上的进栈，请在________处用适当的语句予以填充。

5．以下运算实现循环队列的初始化，请在________处用适当句子予以填充。

voidInitCycQueue(Cycqueue*&sq)

{________________;

________________;sq->rear=0;

}

6．链队在一定范围内不会出现________________的情况。当lq->front==lq->rear时，称为________________。

7．以下运算实现在链队上取队头元素，请在_______处用适当句子予以填充。

intGetFront(LinkQ*lq,DataType*x)

{LinkQ*p;

if(lq->rear==lq->front)return(0);

else{________________;

________________=p->data;

return(1);

}

}

三、选择题

1．设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1，则栈的容量至少应该是()。

A. 2 B. 3 C. 5 D. 6

2．一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是()。

A. edcba B. decba C. dceab D. abcde

3．一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是()。

A. edcba B. decbaC. dceabD. abcde

5．向一个栈顶指针为Top的链中插入一个s所指结点时，其操作步骤为()。

A. Top->next=s

B. s->next=Top->next;Top->next