第 3章 栈和队列本章主要介绍以下内容：
栈的概念、存储结构及其基本操作
队列的概念、存储结构及其基本操作
栈与队列的应用举例退出
3.1 栈
3.2 队列
3.1 栈
3.1.1 栈的定义栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示：
进行插入和删除的一端是浮动端，通常被称为 栈顶,并用一个“栈顶指针”指示；而另一端是固定端，
通常被称为 栈底 。我们经常将栈用下图 3-1的形式描述：
a1,a2,a3,...,an 插入和删除端
a
n
...
a
2
a
1
栈顶 t o p
图 3-1
结论,后进先出 （ Last In First Out），简称为
LIFO线性表。
举例 1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。
举例 2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。
下面我们先给出栈结构的基本操作：
（ 1）初始化栈 InitStack(S)
（ 2）入栈 Push(S,item)
（ 3）出栈 Pop(S,item)
（ 4）获取栈顶元素内容 GetTop(S,item)
（ 5）判断栈是否为空 StackEmpty(S)
3.1.2 栈的顺序存储栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。
类型定义如下所示：
#define MAX_STACK 10
//栈的最大数据元素数目
typedef struct stack{
StackEntry item[MAX_STACK];
//存放栈中数据元素的存储单元
int top; //栈顶指针
}STACK;
基本操作算法：
1,初始化栈 S
void InItStack(STACK *S)
{ s->top=-1; }
2,入栈
void Push(STACK *S,StackEntry item)
{
if (S->top==MAX_STACK-1) exit(“Stack is full”);
else S->item[++S->top]=item;
}
图 3-2
M A X _ S T A C K -1
...
1
0
t o p = - 1
3,出栈
void Pop(STACK *S,StackEntry *item)
{
if (StackEmpty(*S)) exit(“Stack is empty”);
else *item=S->item[S->top--];
}
4,获取栈顶元素内容
void GetTop(STACK S,StackEntry *item)
{
if (StackEmpty(S)) exit(“Stack is empty”);
else *item=S.item[S.top];
}
5,判断栈 S是否为空
int StackEmpty(STACK S)
{
if (S.top==-1) return TRUE;
else FALSE;
}
结论：由于栈的插入和删除操作具有它的特殊性，
所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题，但栈容量难以扩充的弱点仍就没有摆脱。
3.1.3 栈的链式存储若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。如图 3-3所示。
由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。
^
top
图 3-3
栈的链式存储结构在 C语言中可用下列类型定义实现：
type struct node { //链栈的结点结构
StackEntry item; //栈的数据元素类型
struct node *next; //指向后继结点的指针
}NODE;
typedef struct stack{
NODE *top;
}STACK;
下面我们将给出链栈各项基本操作的算法。
1,初始化栈 S
void InitStack(STACK *S)
{
S->top=NULL;
}
2,入栈
void Push(STACK *S,StackEntry item)
{
p=(NODE*)malloc(sizeof(NODE));
if (!p) exit(OVERFLOW);
else { p->item=item;
p->next=S->top;
S->top=p;
}
}
3,出栈
void Pop(STACK*S,StackEntry *item)
{
if (StackEmpty(*S)) exit(“Stack is empty”);
else {
*item=S->top->item;
p=S->top;
S->top=p->next; free(p);
}
}
4,获取栈顶元素内容
void GetTop(STACK S,StackEntry *item)
{
if (StackEmpty(S)) exit(“Stack is empty”);
else *item=S.top->item;
}
5,判断栈 S是否空
int StackEmpty(STACK S)
{
if (S.top==NULL) return TRUE;
else FALSE;
}
3.1.4 栈的应用举例
【 举例 1】 将从键盘输入的字符序列逆置输出比如，从键盘上输入,tset a si sihT；算法将输出：
This is a test
下面我们给出解决这个问题的完整算法。
typedef char StackEntry;
void ReverseRead( )
{
STACK S; //定义一个栈结构 S
char ch;
InitStack(&S); //初始化栈
while ((ch=getchar())!=?\n?)
//从键盘输入字符，直到输入换行符为止
Push(&S,ch);
//将输入的每个字符入栈
while (!StackEmpty(S)) {
//依次退栈并输出退出的字符
Pop(&S,&ch);
putchar(ch);
}
putchar(?\n?);
}
【 举例 2】 十进制数值转换成二进制使用展转相除法将一个十进制数值转换成二进制数值。即用该十进制数值除以 2，并保留其余数；重复此操作，直到该十进制数值为 0为止。最后将所有的余数反向输出就是所对应的二进制数值。
比如,(692)10 = (1010110100)2，其展转相除的过程如图 3-4所示：
图 3-4
除数 被除数 余数
2
6 9 2
2 346 0
2 173 0
2 86 1
2 43 0
2 21 1
2 10 1
2 5 0
2 2 1
2 1 0
0 1
下面给出解决这个问题的完整算法。
void Decimal _ Binary ( )
{
STACK S; //定义栈结构 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】 检验表达式中的括号匹配情况假设在一个算术表达式中，可以包含三种括号：
圆括号“（”和“）”，方括号,[”和,]”和花括号
,{”和,}”，并且这三种括号可以按任意的次序嵌套使用。比如,...[...{...}...[...]...]...[...]...(...)..。现在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。
算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。
（ 1）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；
（ 2）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；
（ 3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。
下面是解决这个问题的完整算法。
typedef char StackEntry;
int Check( )
{
STACK S; //定义栈结构 S
char ch;
InitStack(&S); //初始化栈 S
while ((ch=getchar())!=?\n?){
//以字符序列的形式输入表达式
switch (ch) {
case (ch==?(?||ch==?[?||ch==?{?):
Push(&S,ch);break; //遇左括号入栈
//在遇到右括号时,分别检测匹配情况
case (ch==?)?),if (StackEmpty(S)) retrun
FALSE;
else {Pop(&S,&ch);
if (ch!=?(?) return FALSE; }
break;
case (ch==?]?),if (StackEmpty(S)) retrun FALSE;
else {Pop(&S,&ch);
if (ch!=?[?) return FALSE; }
break;
case (ch==?}?),if (StackEmpty(S)) retrun
FALSE;
else {Pop(&S,&ch);
if (ch!=?{?) return FALSE; }
break;
default:break;
}
}
if (StackEmpty(S)) return TRUE;
else return FALSE;
}
3.2 队列
3.2.1 队列的定义队列特殊性在于限定插入在线性表的一端进行，
删除在线性表的另外一端进行。如图 3-5所示：
a 1 a 2 a 3,.,a i,.,a n-
1
a n
插入端 删除端图 3-5
插入端和删除端都是浮动的。通常我们将插入端称为 队尾,用一个“队尾指针”指示；而删除端被称为 队头,用一个“队头指针”指示。
结论,先进先出 （ First In First Out），简称为
FIFO线性表。
举例 1：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。
举例 2：乘坐公共汽车，应该在车站排队，车来后，
按顺序上车。
举例 3：在 Windows这类多任务的操作系统环境中，
每个应用程序响应一系列的“消息”，像用户点击鼠标；拖动窗口这些操作都会导致向应用程序发送消息。
为此，系统将为每个应用程序创建一个队列，用来存放发送给该应用程序的所有消息，应用程序的处理过程就是不断地从队列中读取消息，并依次给予响应。
下面我们给出队列结构的基本操作：
（ 1）初始化队列 InitQueue(Q)
（ 2）入队 EnQueue(Q,item)
（ 3）出队 DeQueue(Q,item)
（ 4）获取队头元素内容 GetFront(Q,item)
（ 5）判断队列是否为空 QueueEmpty(Q)
3.2.2 队列的顺序存储队列的顺序存储结构如下图 3-6所示：
0 1 2 n - 2 n - 1
a 1 a 2 a 3,.,a n - 1 a n
f r o n t r e a r
图 3-6
问题 1：当队空时，队头和队尾指针都为 -1，队列将处于下图 3-7所示的状态：
0 1 2,.,n - 2 n - 1
f r o n t = - 1
r e a r = - 1
图 3-7
此时若进行入队操作，就需要让队头和队尾指针都增 1，再将新数据元素放入该位置。也就是说，这样设置队头、队尾指针位置，在进行入队操作时，空队与非空队状态所需要执行的操作不完全一样。
解决方法：在算法中，需要对这两种情况加以区分，
这势必增加了算法的复杂性。因此，人们设想了一种解决方法，即让队头指针指向队列真正队头元素的前一个位置，如下图 3-8所示。
0 1 2 n - 2 n - 1
a
1
a
2
a
3
..,a
n - 1
a
n
f r o n t r e a r
图 3-8
问题 2：由于顺序存储结构的存储空间属于静态分配，所以，在添加数据元素时，可能会出现没有剩余单元的情况。对于队列来说，这一点又有它的特殊性。
下面我们讨论一下下图 3-10所示的队列。
0 1 2 3 4 5 6 7
a
5
a
6
a
7
a
8
fro nt re a r
图 3-10
“假溢出”现象。
解决方法：将存储队列元素的一维数组首尾相接，
形成一个环状。如图 3-11所示。我们将这种形式表示的队列称之为 循环队列 。
a8a7
a6
a5
76
5
4
3 2
1
0
rear
front
图 3-11
假设为队列开辟的数组单元数目为 MAX_QUEUE，
在 C语言中，它的下标在 0~MAX_QUEUE-1之间，若增加队头或队尾指针，可以利用取模运算（一个整数数值整除以另一个整数数值的余数）实现。如下所示：
front=(front+1)%MAX_QUEUE；
rear=(rear+1)%MAX_QUEUE；
当 front或 rear为 MAXQUEUE-1时，上述两个公式计算的结果就为 0。这样，就使得指针自动由后面转到前面，形成循环的效果。
队空和队满的标志问题：
队列变为空，队头和队尾指针相等。
a7 a8
76
5
4
3 2
1
0
rear
front 76
5
4
3 2
1
0
rear
front
(a) (b)
图 3-12
队列变为满，队头和队尾指针也相等。
rear front
a6
a5
a4 a3
a1
a2
76
5
4
3 2
1
0 a6
a5
a4 a3
a1
a2
a8a7
76
5
4
3 2
1
0
rear
front
(a) (b)
图 3-13
解决方法：一是为队列另设一个标志，用来区分队列是“空”还是“满”；二是当数组只剩下一个单元时就认为队满，此时，队尾指针只差一步追上队头指针，即,(rear+1)%MAX_QUEUE==front。
类型定义：
#define MAX_QUEUE 10
//队列的最大数据元素数目
typedef struct queue{
//假设当数组只剩下一个单元时认为队满
QueueEntry item[MAX_QUEUE];
//存放队列中数据元素的存储单元
int front,rear; //队头指针、队尾指针
}QUEUE;
各项基本操作算法。
（ 1）初始化队列 Q
void InitQueue(QUEUE *Q)
{
Q->front=-1;
Q->rear=-1;
}
（ 2）入队
void EnQueue(QUEUE *Q,QueueEntry item)
{
if ((Q->rear+1)%MAX_QUEUE==Q->front)
exit(OVERFLOW);
else { Q->rear=(Q->rear+1)%MAX_QUEUE;
Q->item[Q->rear]=item; }
}
（ 3）出队
void DeQueue(QUEUE*Q,QueueEntry *item)
{
if (QueueEmpty(*Q)) exit(“Queue is empty.”);
else {
Q->front=(Q->front+1)%MAX_QUEUE;
*item=Q->item[Q->front];
}
}
（ 4）获取队头元素内容
void GetFront(QUEUE Q,QueueEntry *item)
{
if (QueueEmpty(Q)) exit(“Queue is empty.”);
else *item=Q.item[(Q.front+1)%MAX_QUEUE];
}
（ 5）判断队列 Q是否为空
int QueueEmpty(Queue Q)
{
if (Q.front==Q.rear) return TRUE;
else return FALSE;
}
3.2.3 队列的链式存储在用链式存储结构表示队列时，需要设置队头指针和队尾指针，以便指示队头结点和队尾结点。
^front
rear
图 3-14
入队需要执行下面三条语句：
s->next=NULL; rear->next=s;rear=s;
下面是在 C语言中，实现队列链式存储结构的类型定义：
type struct node { //链式队列的结点结构
QueueEntry Entry; //队列的数据元素类型
struct node *next; //指向后继结点的指针
}NODE;
typedef struct queue{ //链式队列
NODE *front; //队头指针
NODE *rear; //队尾指针
}QUEUE;
下面我们给出链式队列的基本操作算法。
（ 1）初始化队列 Q
void InitQueue(QUEUE *Q)
{
Q->front=(NODE*)malloc(sizeof(NODE));
if (Q->front==NULL) exit(ERROR);
Q->rear= Q->front;
}
（ 2）入队
void EnQueue(QUEUE *Q,QueueEntry item)
{
s=(NODE*)malloc(sizeof(NODE));
if (!s) exit(ERROR);
s->item=item;
s->next=NULL;
Q->rear->next=s;
Q->rear=s;
}
（ 3）出队
void DeQueue(QUEUE *Q,QueueEntry *item)
{
if (QueueEmpty(*Q)) exit(ERROR);
else {
*item=Q->front->next->item;
s=Q->front->next;
Q->front->next=s->next;
free(s);
}
}
（ 4）获取队头元素内容
void GetFront(QUEUE Q,QueueEntry *item)
{
if (QueueEmpty(Q)) exit(ERROR);
else *item=Q->front->next->item;
}
（ 5）判断队列 Q是否为空
int QueueEmpty(QUEUE Q)
{
if (Q->front==Q->rear) return TRUE；
else return FALSE;
}
4．队列的应用举例
【 举例 1】 汽车加油站。
随着城市里汽车数量的急速增长，汽车加油站也渐渐多了起来。通常汽车加油站的结构基本上是：入口和出口为单行道，加油车道可能有若干条。每辆车加油都要经过三段路程，第一段是在入口处排队等候进入加油车道；第二段是在加油车道排队等候加油；
第三段是进入出口处排队等候离开。实际上，这三段都是队列结构。若用算法模拟这个过程，就需要设置加油车道数加 2个队列。
【 举例 2】 模拟打印机缓冲区。
在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这样会降低主机的使用效率。
为此人们设想了一种办法：为打印机设置一个打印数据缓冲区，当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的事情，而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印数据的正确性，又提高了主机的使用效率。由此可见，打印机缓冲区实际上就是一个队列结构。
【 举例 3】 CPU分时系统在一个带有多个终端的计算机系统中，同时有多个用户需要使用 CPU运行各自的应用程序，它们分别通过各自的终端向操作系统提出使用 CPU的请求，操作系统通常按照每个请求在时间上的先后顺序，将它们排成一个队列，每次把 CPU分配给当前队首的请求用户，即将该用户的应用程序投入运行，当该程序运行完毕或用完规定的时间片后，操作系统再将 CPU分配给新的队首请求用户，这样即可以满足每个用户的请求，又可以使 CPU正常工作。
栈的概念、存储结构及其基本操作
队列的概念、存储结构及其基本操作
栈与队列的应用举例退出
3.1 栈
3.2 队列
3.1 栈
3.1.1 栈的定义栈是一种特殊的线性表。其特殊性在于限定插入和删除数据元素的操作只能在线性表的一端进行。如下所示：
进行插入和删除的一端是浮动端，通常被称为 栈顶,并用一个“栈顶指针”指示；而另一端是固定端，
通常被称为 栈底 。我们经常将栈用下图 3-1的形式描述：
a1,a2,a3,...,an 插入和删除端
a
n
...
a
2
a
1
栈顶 t o p
图 3-1
结论,后进先出 （ Last In First Out），简称为
LIFO线性表。
举例 1：家里吃饭的碗，通常在洗干净后一个一个地落在一起存放，在使用时，若一个一个地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。
举例 2：在建筑工地上，使用的砖块从底往上一层一层地码放，在使用时，将从最上面一层一层地拿取。
下面我们先给出栈结构的基本操作：
（ 1）初始化栈 InitStack(S)
（ 2）入栈 Push(S,item)
（ 3）出栈 Pop(S,item)
（ 4）获取栈顶元素内容 GetTop(S,item)
（ 5）判断栈是否为空 StackEmpty(S)
3.1.2 栈的顺序存储栈的顺序存储结构是用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。
类型定义如下所示：
#define MAX_STACK 10
//栈的最大数据元素数目
typedef struct stack{
StackEntry item[MAX_STACK];
//存放栈中数据元素的存储单元
int top; //栈顶指针
}STACK;
基本操作算法：
1,初始化栈 S
void InItStack(STACK *S)
{ s->top=-1; }
2,入栈
void Push(STACK *S,StackEntry item)
{
if (S->top==MAX_STACK-1) exit(“Stack is full”);
else S->item[++S->top]=item;
}
图 3-2
M A X _ S T A C K -1
...
1
0
t o p = - 1
3,出栈
void Pop(STACK *S,StackEntry *item)
{
if (StackEmpty(*S)) exit(“Stack is empty”);
else *item=S->item[S->top--];
}
4,获取栈顶元素内容
void GetTop(STACK S,StackEntry *item)
{
if (StackEmpty(S)) exit(“Stack is empty”);
else *item=S.item[S.top];
}
5,判断栈 S是否为空
int StackEmpty(STACK S)
{
if (S.top==-1) return TRUE;
else FALSE;
}
结论：由于栈的插入和删除操作具有它的特殊性，
所以用顺序存储结构表示的栈并不存在插入删除数据元素时需要移动的问题，但栈容量难以扩充的弱点仍就没有摆脱。
3.1.3 栈的链式存储若是栈中元素的数目变化范围较大或不清楚栈元素的数目，就应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称作“链栈”。链栈通常用一个无头结点的单链表表示。如图 3-3所示。
由于栈的插入删除操作只能在一端进行，而对于单链表来说，在首端插入删除结点要比尾端相对地容易一些，所以，我们将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。
^
top
图 3-3
栈的链式存储结构在 C语言中可用下列类型定义实现：
type struct node { //链栈的结点结构
StackEntry item; //栈的数据元素类型
struct node *next; //指向后继结点的指针
}NODE;
typedef struct stack{
NODE *top;
}STACK;
下面我们将给出链栈各项基本操作的算法。
1,初始化栈 S
void InitStack(STACK *S)
{
S->top=NULL;
}
2,入栈
void Push(STACK *S,StackEntry item)
{
p=(NODE*)malloc(sizeof(NODE));
if (!p) exit(OVERFLOW);
else { p->item=item;
p->next=S->top;
S->top=p;
}
}
3,出栈
void Pop(STACK*S,StackEntry *item)
{
if (StackEmpty(*S)) exit(“Stack is empty”);
else {
*item=S->top->item;
p=S->top;
S->top=p->next; free(p);
}
}
4,获取栈顶元素内容
void GetTop(STACK S,StackEntry *item)
{
if (StackEmpty(S)) exit(“Stack is empty”);
else *item=S.top->item;
}
5,判断栈 S是否空
int StackEmpty(STACK S)
{
if (S.top==NULL) return TRUE;
else FALSE;
}
3.1.4 栈的应用举例
【 举例 1】 将从键盘输入的字符序列逆置输出比如，从键盘上输入,tset a si sihT；算法将输出：
This is a test
下面我们给出解决这个问题的完整算法。
typedef char StackEntry;
void ReverseRead( )
{
STACK S; //定义一个栈结构 S
char ch;
InitStack(&S); //初始化栈
while ((ch=getchar())!=?\n?)
//从键盘输入字符，直到输入换行符为止
Push(&S,ch);
//将输入的每个字符入栈
while (!StackEmpty(S)) {
//依次退栈并输出退出的字符
Pop(&S,&ch);
putchar(ch);
}
putchar(?\n?);
}
【 举例 2】 十进制数值转换成二进制使用展转相除法将一个十进制数值转换成二进制数值。即用该十进制数值除以 2，并保留其余数；重复此操作，直到该十进制数值为 0为止。最后将所有的余数反向输出就是所对应的二进制数值。
比如,(692)10 = (1010110100)2，其展转相除的过程如图 3-4所示：
图 3-4
除数 被除数 余数
2
6 9 2
2 346 0
2 173 0
2 86 1
2 43 0
2 21 1
2 10 1
2 5 0
2 2 1
2 1 0
0 1
下面给出解决这个问题的完整算法。
void Decimal _ Binary ( )
{
STACK S; //定义栈结构 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】 检验表达式中的括号匹配情况假设在一个算术表达式中，可以包含三种括号：
圆括号“（”和“）”，方括号,[”和,]”和花括号
,{”和,}”，并且这三种括号可以按任意的次序嵌套使用。比如,...[...{...}...[...]...]...[...]...(...)..。现在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的合法性。
算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。在检验过程中，若遇到以下几种情况之一，就可以得出括号不匹配的结论。
（ 1）当遇到某一个右括号时，栈已空，说明到目前为止，右括号多于左括号；
（ 2）从栈中弹出的左括号与当前检验的右括号类型不同，说明出现了括号交叉情况；
（ 3）算术表达式输入完毕，但栈中还有没有匹配的左括号，说明左括号多于右括号。
下面是解决这个问题的完整算法。
typedef char StackEntry;
int Check( )
{
STACK S; //定义栈结构 S
char ch;
InitStack(&S); //初始化栈 S
while ((ch=getchar())!=?\n?){
//以字符序列的形式输入表达式
switch (ch) {
case (ch==?(?||ch==?[?||ch==?{?):
Push(&S,ch);break; //遇左括号入栈
//在遇到右括号时,分别检测匹配情况
case (ch==?)?),if (StackEmpty(S)) retrun
FALSE;
else {Pop(&S,&ch);
if (ch!=?(?) return FALSE; }
break;
case (ch==?]?),if (StackEmpty(S)) retrun FALSE;
else {Pop(&S,&ch);
if (ch!=?[?) return FALSE; }
break;
case (ch==?}?),if (StackEmpty(S)) retrun
FALSE;
else {Pop(&S,&ch);
if (ch!=?{?) return FALSE; }
break;
default:break;
}
}
if (StackEmpty(S)) return TRUE;
else return FALSE;
}
3.2 队列
3.2.1 队列的定义队列特殊性在于限定插入在线性表的一端进行，
删除在线性表的另外一端进行。如图 3-5所示：
a 1 a 2 a 3,.,a i,.,a n-
1
a n
插入端 删除端图 3-5
插入端和删除端都是浮动的。通常我们将插入端称为 队尾,用一个“队尾指针”指示；而删除端被称为 队头,用一个“队头指针”指示。
结论,先进先出 （ First In First Out），简称为
FIFO线性表。
举例 1：到医院看病，首先需要到挂号处挂号，然后，按号码顺序救诊。
举例 2：乘坐公共汽车，应该在车站排队，车来后，
按顺序上车。
举例 3：在 Windows这类多任务的操作系统环境中，
每个应用程序响应一系列的“消息”，像用户点击鼠标；拖动窗口这些操作都会导致向应用程序发送消息。
为此，系统将为每个应用程序创建一个队列，用来存放发送给该应用程序的所有消息，应用程序的处理过程就是不断地从队列中读取消息，并依次给予响应。
下面我们给出队列结构的基本操作：
（ 1）初始化队列 InitQueue(Q)
（ 2）入队 EnQueue(Q,item)
（ 3）出队 DeQueue(Q,item)
（ 4）获取队头元素内容 GetFront(Q,item)
（ 5）判断队列是否为空 QueueEmpty(Q)
3.2.2 队列的顺序存储队列的顺序存储结构如下图 3-6所示：
0 1 2 n - 2 n - 1
a 1 a 2 a 3,.,a n - 1 a n
f r o n t r e a r
图 3-6
问题 1：当队空时，队头和队尾指针都为 -1，队列将处于下图 3-7所示的状态：
0 1 2,.,n - 2 n - 1
f r o n t = - 1
r e a r = - 1
图 3-7
此时若进行入队操作，就需要让队头和队尾指针都增 1，再将新数据元素放入该位置。也就是说，这样设置队头、队尾指针位置，在进行入队操作时，空队与非空队状态所需要执行的操作不完全一样。
解决方法：在算法中，需要对这两种情况加以区分，
这势必增加了算法的复杂性。因此，人们设想了一种解决方法，即让队头指针指向队列真正队头元素的前一个位置，如下图 3-8所示。
0 1 2 n - 2 n - 1
a
1
a
2
a
3
..,a
n - 1
a
n
f r o n t r e a r
图 3-8
问题 2：由于顺序存储结构的存储空间属于静态分配，所以，在添加数据元素时，可能会出现没有剩余单元的情况。对于队列来说，这一点又有它的特殊性。
下面我们讨论一下下图 3-10所示的队列。
0 1 2 3 4 5 6 7
a
5
a
6
a
7
a
8
fro nt re a r
图 3-10
“假溢出”现象。
解决方法：将存储队列元素的一维数组首尾相接，
形成一个环状。如图 3-11所示。我们将这种形式表示的队列称之为 循环队列 。
a8a7
a6
a5
76
5
4
3 2
1
0
rear
front
图 3-11
假设为队列开辟的数组单元数目为 MAX_QUEUE，
在 C语言中，它的下标在 0~MAX_QUEUE-1之间，若增加队头或队尾指针，可以利用取模运算（一个整数数值整除以另一个整数数值的余数）实现。如下所示：
front=(front+1)%MAX_QUEUE；
rear=(rear+1)%MAX_QUEUE；
当 front或 rear为 MAXQUEUE-1时，上述两个公式计算的结果就为 0。这样，就使得指针自动由后面转到前面，形成循环的效果。
队空和队满的标志问题：
队列变为空，队头和队尾指针相等。
a7 a8
76
5
4
3 2
1
0
rear
front 76
5
4
3 2
1
0
rear
front
(a) (b)
图 3-12
队列变为满，队头和队尾指针也相等。
rear front
a6
a5
a4 a3
a1
a2
76
5
4
3 2
1
0 a6
a5
a4 a3
a1
a2
a8a7
76
5
4
3 2
1
0
rear
front
(a) (b)
图 3-13
解决方法：一是为队列另设一个标志，用来区分队列是“空”还是“满”；二是当数组只剩下一个单元时就认为队满，此时，队尾指针只差一步追上队头指针，即,(rear+1)%MAX_QUEUE==front。
类型定义：
#define MAX_QUEUE 10
//队列的最大数据元素数目
typedef struct queue{
//假设当数组只剩下一个单元时认为队满
QueueEntry item[MAX_QUEUE];
//存放队列中数据元素的存储单元
int front,rear; //队头指针、队尾指针
}QUEUE;
各项基本操作算法。
（ 1）初始化队列 Q
void InitQueue(QUEUE *Q)
{
Q->front=-1;
Q->rear=-1;
}
（ 2）入队
void EnQueue(QUEUE *Q,QueueEntry item)
{
if ((Q->rear+1)%MAX_QUEUE==Q->front)
exit(OVERFLOW);
else { Q->rear=(Q->rear+1)%MAX_QUEUE;
Q->item[Q->rear]=item; }
}
（ 3）出队
void DeQueue(QUEUE*Q,QueueEntry *item)
{
if (QueueEmpty(*Q)) exit(“Queue is empty.”);
else {
Q->front=(Q->front+1)%MAX_QUEUE;
*item=Q->item[Q->front];
}
}
（ 4）获取队头元素内容
void GetFront(QUEUE Q,QueueEntry *item)
{
if (QueueEmpty(Q)) exit(“Queue is empty.”);
else *item=Q.item[(Q.front+1)%MAX_QUEUE];
}
（ 5）判断队列 Q是否为空
int QueueEmpty(Queue Q)
{
if (Q.front==Q.rear) return TRUE;
else return FALSE;
}
3.2.3 队列的链式存储在用链式存储结构表示队列时，需要设置队头指针和队尾指针，以便指示队头结点和队尾结点。
^front
rear
图 3-14
入队需要执行下面三条语句：
s->next=NULL; rear->next=s;rear=s;
下面是在 C语言中，实现队列链式存储结构的类型定义：
type struct node { //链式队列的结点结构
QueueEntry Entry; //队列的数据元素类型
struct node *next; //指向后继结点的指针
}NODE;
typedef struct queue{ //链式队列
NODE *front; //队头指针
NODE *rear; //队尾指针
}QUEUE;
下面我们给出链式队列的基本操作算法。
（ 1）初始化队列 Q
void InitQueue(QUEUE *Q)
{
Q->front=(NODE*)malloc(sizeof(NODE));
if (Q->front==NULL) exit(ERROR);
Q->rear= Q->front;
}
（ 2）入队
void EnQueue(QUEUE *Q,QueueEntry item)
{
s=(NODE*)malloc(sizeof(NODE));
if (!s) exit(ERROR);
s->item=item;
s->next=NULL;
Q->rear->next=s;
Q->rear=s;
}
（ 3）出队
void DeQueue(QUEUE *Q,QueueEntry *item)
{
if (QueueEmpty(*Q)) exit(ERROR);
else {
*item=Q->front->next->item;
s=Q->front->next;
Q->front->next=s->next;
free(s);
}
}
（ 4）获取队头元素内容
void GetFront(QUEUE Q,QueueEntry *item)
{
if (QueueEmpty(Q)) exit(ERROR);
else *item=Q->front->next->item;
}
（ 5）判断队列 Q是否为空
int QueueEmpty(QUEUE Q)
{
if (Q->front==Q->rear) return TRUE；
else return FALSE;
}
4．队列的应用举例
【 举例 1】 汽车加油站。
随着城市里汽车数量的急速增长，汽车加油站也渐渐多了起来。通常汽车加油站的结构基本上是：入口和出口为单行道，加油车道可能有若干条。每辆车加油都要经过三段路程，第一段是在入口处排队等候进入加油车道；第二段是在加油车道排队等候加油；
第三段是进入出口处排队等候离开。实际上，这三段都是队列结构。若用算法模拟这个过程，就需要设置加油车道数加 2个队列。
【 举例 2】 模拟打印机缓冲区。
在主机将数据输出到打印机时，会出现主机速度与打印机的打印速度不匹配的问题。这时主机就要停下来等待打印机。显然，这样会降低主机的使用效率。
为此人们设想了一种办法：为打印机设置一个打印数据缓冲区，当主机需要打印数据时，先将数据依次写入这个缓冲区，写满后主机转去做其他的事情，而打印机就从缓冲区中按照先进先出的原则依次读取数据并打印，这样做即保证了打印数据的正确性，又提高了主机的使用效率。由此可见，打印机缓冲区实际上就是一个队列结构。
【 举例 3】 CPU分时系统在一个带有多个终端的计算机系统中，同时有多个用户需要使用 CPU运行各自的应用程序，它们分别通过各自的终端向操作系统提出使用 CPU的请求，操作系统通常按照每个请求在时间上的先后顺序，将它们排成一个队列，每次把 CPU分配给当前队首的请求用户，即将该用户的应用程序投入运行，当该程序运行完毕或用完规定的时间片后，操作系统再将 CPU分配给新的队首请求用户，这样即可以满足每个用户的请求，又可以使 CPU正常工作。
