本章主要内容1栈的概念存储结构及其基本操作及其应用2.docx
《本章主要内容1栈的概念存储结构及其基本操作及其应用2.docx》由会员分享，可在线阅读，更多相关《本章主要内容1栈的概念存储结构及其基本操作及其应用2.docx（17页珍藏版）》请在冰点文库上搜索。
本章主要内容1栈的概念存储结构及其基本操作及其应用2
本章主要内容：
1、栈的概念、存储结构及其基本操作及其应用；2、队列的概念、存储结构及其基本操作及其应用
课时分配：
1、2各占2学时，上机2学时
重点、难点：
栈的存储结构及其基本操作、队列存储结构及其基本操作
§3.1栈
3.1.1栈的定义
栈是一种特殊的线性表。
其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。
如下所示：
结论：
后进先出（LastInFirstOut），简称为LIFO线性表。
例3－1：
家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。
例3－2：
在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。
下面我们先给出栈结构的基本操作：
（1）初始化栈InitStack（S）
（2）入栈Push（S,elem）
（3）出栈Pop（S,elem）
（4）获取栈顶元素内容GetTop（S,elem）
（5）判断栈是否为空StackEmpty（S）
3.1.2栈的顺序存储结构及其基本运算的实现
栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。
类型定义如下所示：
#defineMAXSIZE100
#defineERROR-1
typedefstruct
{/*栈类定义*/
intelements[MAXSIZE];
inttop;
}Stack;
基本操作算法：
（1）初始化栈
voidInitStack（Stack*S）
{/*初始化栈，将栈置空*/
S->top=0;
}
（2）入栈
voidPush（Stack*S,intx）
{/*将元素x压入到栈S中*/
if（!
IsFull（*S））
{/*如果尚未达到栈满，则将x压入栈S中，并使栈顶指针增1*/
S->elements[S->top]=x;
S->top++;
}
else
printf（"栈上溢！
\n"）;
}
（3）出栈
intPop（Stack*S）
{/*将栈S中的栈顶元素出栈*/
if（!
IsEmpty（*S））
{/*如果栈非空，则返回栈顶元素，并使栈顶指针减1*/
S->top--;
returnS->elements[S->top];
}
else
{
printf（"栈下溢！
\n"）;
returnERROR;
}
}
（4）获取栈顶元素内容
intGetTop（StackS）
{/*获取栈顶元素，但不改变栈顶指针*/
if（!
IsEmpty（S））
returnS.elements[S.top-1];
else
{
printf（"栈空！
\n"）;
returnERROR;
}
}
（5）判断栈S是否为空
boolIsEmpty（StackS）
{/*判断栈是否为空。
如果栈空，返回true，否则返回false*/
if（S.top==0）returntrue;
elsereturnfalse;
}
结论：
由于栈的插入和删除操作具有它的特殊性，所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题，但栈容量难以扩充的弱点仍就没有摆脱。
3.1.3栈的链式存储及其基本运算的实现
若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。
人们将用链式存储结构表示的栈称作"链栈"。
链栈通常用一个无头结点的单链表表示。
如图示：
结点类型定义：
typedefstructnode
{/*栈类定义*/
intdata;
structnode*next;
}LinkStack;
（1）初始化
voidInitLinkStack（LinkStack**top）
{/*初始化栈，将栈置空*/
*top=NULL;
}
（2）判断是否为空
boolIsEmpty（LinkStack*top）
{/*判断栈是否为空。
如果栈空，返回true，否则返回false*/
if（top==NULL）returntrue;
elsereturnfalse;
}
（3）进栈
voidPush（LinkStack**top,intx）
{/*将元素x压入到栈S中，先申请结点再将其入栈*/
LinkStack*S;
S=（LinkStack*）malloc（sizeof（LinkStack））;
S->data=x;
S->next=*top;
*top=S;
}
（4）出栈
intPop（LinkStack**top）
{/*将栈S中的栈顶元素出栈*/
LinkStack*S;
intdata;
if（!
IsEmpty（*top））
{/*如果栈非空，则返回栈顶元素，并使栈顶指针减1*/
S=*top;
*top=（*top）->next;
data=S->data;
free（S）;
returndata;
}
else
{
printf（"栈下溢！
\n"）;
returnERROR;
}
}
（5）取栈顶元素
intGetTop（LinkStack*top）
{/*获取栈顶元素，但不改变栈顶指针*/
if（!
IsEmpty（top））
returntop->data;
else
{
printf（"栈空！
\n"）;
returnERROR;
}
}
（6）清空
voidEmptyLinkStack（LinkStack**top）
{/*清空堆栈S，使其栈顶指针为0*/
LinkStack*S;
while（*top!
=NULL）
{
S=（*top）->next;
free（*top）;
*top=S;
}
}
3.1.4栈的应用举例
例3-3:
将从键盘输入的字符序列逆置输出
比如，从键盘上输入：
tsetasisihT；算法将输出：
Thisisatest
下面我们给出解决这个问题的完整算法。
typedefcharElemtype;
voidReverseRead（）
{
StackS;//定义一个栈结构S
charch;
InitStack（&S）;//初始化栈
while（（ch=getchar（））!
='\n'）//从键盘输入字符，直到输入换行符为止
Push（&S,ch）;//将输入的每个字符入栈
while（!
StackEmpty（S））{//依次退栈并输出退出的字符
Pop（&S,&ch）;
putchar（ch）;
}
putchar（'\n'）;
}
例3－4：
十进制数值转换成二进制
使用展转相除法将一个十进制数值转换成二进制数值。
即用该十进制数值除以2，并保留
其余数；重复此操作，直到该十进制数值为0为止。
最后将所有的余数反向输出就是所对应的二进制数值。
比如：
（692）10=（1010110100）2，其展转相除的过程如图所示：
下面给出解决这个问题的完整算法。
voidDecimal_Binary（）
{
STACKS;//定义栈结构S
InitStack（&S）;//初始化栈S
scanf（"%d",data）;//输入十进制正整数
while（data）{
Push（&S,data%2）;//余数入栈
data/=2;//被除数data整除以2，得到新的被除数
}
while（!
StackEmpty（S））{//依次从栈中弹出每一个余数，并输出之
Pop（&S,&data）;
printf（"%d",data）;
}
}
例3－5：
检验表达式中的括号匹配情况
假设在一个算术表达式中，可以包含三种括号：
圆括号"（"和"）"，方括号"["和"]"和花括号"{"和"}"，并且这三种括号可以按任意的次序嵌套使用。
比如，...[...{...}...[...]...]...[...]...（...）..。
现在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。
算术表达式中各种括号的使用规则为：
出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。
我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。
在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。
（1）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；
（2）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；
（3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。
下面是解决这个问题的完整算法。
typedefcharElemtype;
intCheck（）
{
STACKS;//定义栈结构S
charch;
InitStack（&S）;//初始化栈S
while（（ch=getchar（））!
='\n'）{//以字符序列的形式输入表达式
switch（ch）{
case（ch=='（'||ch=='['||ch=='{'）:
Push（&S,ch）;break;//遇左括号入栈
//在遇到右括号时，分别检测匹配情况
case（ch=='）'）:
if（StackEmpty（S））retrunFALSE;
else{Pop（&S,&ch）;
if（ch!
='（'）returnFALSE;}
break;
case（ch==']'）:
if（StackEmpty（S））retrunFALSE;
else{Pop（&S,&ch）;
if（ch!
='['）returnFALSE;}
break;
case（ch=='}'）:
if（StackEmpty（S））retrunFALSE;
else{Pop（&S,&ch）;
if（ch!
='{'）returnFALSE;}
break;
default:
break;
}
}
if（StackEmpty（S））returnTRUE;
elsereturnFALSE;
]
§3.2队列
3.2.1队列的定义
插入端和删除端都是浮动的。
通常我们将插入端称为队尾，用一个"队尾指针"指示；而删除端被称为队头，用一个"队头指针"指示。
结论：
先进先出（FirstInFirstOut），简称为FIFO线性表。
例3-6：
到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。
例3-7：
乘坐公共汽车，应该在车站排队，车来后，按顺序上车。
例3-8：
在Windows这类多任务的操作系统环境中，每个应用程序响应一系列的"消息"，像用户点击鼠标；拖动窗口这些操作都会导致向应用程序发送消息。
为此，系统将为每个应用程序创建一个队列，用来存放发送给该应用程序的所有消息，应用程序的处理过程就是不断地从队列中读取消息，并依次给予响应。
下面我们给出队列结构的基本操作：
（1）初始化队列InitQueue（Q）
（2）入队EnQueue（Q,elem）
（3）出队DeQueue（Q,elem）
（4）获取队头元素内容GetFront（Q,elem）
（5）判断队列是否为空QueueEmpty（Q）
3.2.2队列的顺序存储结构及其基本运算的实现
队列的顺序存储结构如下图所示：
0
1
2
…
n-2
n-1
a1
a2
a3
…
an-1
an
问题1：
当队列空时，对头和队尾指针都为－1，队列将变成下图所示状态：
0
1
2
…
n-2
n-1
问题2：
假溢出，即，在添加数据时，可能出现没有剩余空间而实际队列又不满的状况。
如：
0
1
2
3
4
5
6
7
…
a5
a6
a7
a8
rear
front
解决办法：
将存储队列元素的一维数组首尾相接形成一个环状，即循环队列，如下图：
rear
front
3
2
1
0
7
6
5
4
a8
a7
a6
a5
假设为队列开辟的数组单元数目为MAX_QUEUE，在C语言中，它的下标在0~MAX_QUEUE-1之间，若增加队头或队尾指针，可以利用取模运算（一个整数数值整除以另一个整数数值的余数）实现。
如下所示：
front=（front+1）%MAX_QUEUE；rear=（rear+1）%MAX_QUEUE；
当front或rear为MAXQUEUE-1时，上述两个公式计算的结果就为0。
这样，就使得指针自动由后面转到前面，形成循环的效果。
队空和队满的标志问题：
队列变为空，队头和队尾指针相等。
解决方法：
一是为队列另设一个标志，用来区分队列是"空"还是"满"；二是当数组只剩下一个单元时就认为队满，此时，队尾指针只差一步追上队头指针，即：
（rear+1）%MAX_QUEUE==front。
类型定义：
#defineMAX_QUEUE10//队列的最大数据元素数目
typedefstructqueue{//假设当数组只剩下一个单元时认为队满
Elemtypeelem[MAX_QUEUE];//存放队列中数据元素的存储单元
intfront,rear;//队头指针、队尾指针
}QUEUE;
各项基本操作算法。
（1）初始化队列Q
voidInitQueue（QUEUE*Q）
{
Q->front=-1;
Q->rear=-1;
}
（2）入队
voidEnQueue（QUEUE*Q,Elemtypeelem）
{
if（（Q->rear+1）%MAX_QUEUE==Q->front）exit（OVERFLOW）;
else{Q->rear=（Q->reasr+1）%MAX_QUEUE;
Q->elem[Q->rear]=elem;}
}
（3）出队
voidDeQueue（QUEUE*Q,Elemtype*elem）
{
if（QueueEmpty（*Q））exit（"Queueisempty."）;
else{
Q->front=（Q->front+1）%MAX_QUEUE;
*elem=Q->elem[Q->front];
}
}
（4）获取队头元素内容
voidGetFront（QUEUEQ,Elemtype*elem）
{
if（QueueEmpty（Q））exit（"Queueisempty."）;
else*elem=Q.elem[（Q.front+1）%MAX_QUEUE];
}
（5）判断队列Q是否为空
intQueueEmpty（QueueQ）
{
if（Q.front==Q.rear）returnTRUE;
elsereturnFALSE;
}
3.2.3队列的链式存储结构及其基本运算的实现
在用链式结构存储队列时，需要设置队头指针和队尾指针，以便指示队头结点和队尾结点。
结点结构定义如下：
typedefstructnode
{/*队列结点类型定义*/
intdata;
structnode*next;
}LinkQueue;
typedefstruct
{/*队列头结点类型定义*/
LinkQueue*front;/*队列的队首指针*/
LinkQueue*rear;/*队列的队尾指针*/
}Queue;
基本运算：
（1）初始化
voidInitQueue（Queue*Q）
{/*初始化队列，生成一个带哨兵的空队列*/
Q->front=（LinkQueue*）malloc（sizeof（LinkQueue））;
Q->front->next=NULL;
Q->rear=Q->front;
}
（2）判空
boolIsEmpty（QueueQ）
{/*判断队列是否为空。
如果队列为空，返回true，否则返回false*/
if（Q.front==Q.rear）returntrue;
elsereturnfalse;
}
（3）进队
voidEnQueue（Queue*Q,intx）
{/*将元素x压入到队列Q中，先申请结点再将其入队*/
Q->rear->next=（LinkQueue*）malloc（sizeof（LinkQueue））;
Q->rear=Q->rear->next;
Q->rear->data=x;
Q->rear->next=NULL;
}
（4）出队
intDeQueue（Queue*Q）
{/*将队列Q中的队首元素出队*/
LinkQueue*p;
intdata;
if（!
IsEmpty（*Q））
{/*如果队列非空，则返回队首元素*/
p=Q->front->next;
Q->front->next=p->next;
/*当将队列中的一个元素删除后，指针rear就悬浮起来了，
需要将其调整到正确的状态，即必须使其等于front*/
if（p->next==NULL）Q->rear=Q->front;
data=p->data;free（p）;
returndata;
}
}
3.2.4队列的应用举例
例3-9：
汽车加油站。
随着城市里汽车数量的急速增长，汽车加油站也渐渐多了起来。
通常汽车加油站的结构基本上是：
入口和出口为单行道，加油车道可能有若干条。
每辆车加油都要经过三段路程，第一段是在入口处排队等候进入加油车道；第二段是在加油车道排队等候加油；第三段是进入出口处排队等候离开。
实际上，这三段都是队列结构。
若用算法模拟这个过程，就需要设置加油车道数加2个队列。
例3-10：
模拟打印机缓冲区。
在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。
这时主机就要停下来等待打印机。
显然，这样会降低主机的使用效率。
为此人们设想了一种办法：
为打印机设置一个打印数据缓冲区，当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的事情，而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印数据的正确性，又提高了主机的使用效率。
由此可见，打印机缓冲区实际上就是一个队列结构。
例3-11：
CPU分时系统
在一个带有多个终端的计算机系统中，同时有多个用户需要使用CPU运行各自的应用程序，它们分别通过各自的终端向操作系统提出使用CPU的请求，操作系统通常按照每个请求在时间上的先后顺序，将它们排成一个队列，每次把CPU分配给当前队首的请求用户，即将该用户的应用程序投入运行，当该程序运行完毕或用完规定的时间片后，操作系统再将CPU分配给新的队首请求用户，这样即可以满足每个用户的请求，又可以使CPU正常工作。
升级会员 