3.2 队列
3.2.1 队列的概念
队列是另一种特殊的线性表，它的特殊性体现在队列只允许在表尾插入数据元素，在表头删除数据元素，所以队列也是一种操作受限的特殊的线性表，它具有先进先出（first-in first-out，FIFO）或后进后出（last-in last-out，LILO）的特性。
允许进行插入的一端被称为队尾（rear），允许进行删除的一端被称为队首（队头）（front）。假设队列中的数据元素序列为{a1，a2，a3，…，an}，则其中a1为队首（队头）元素，an为队尾元素，n为队列中数据元素的个数，当n=0时，称为空队列。队列的插入操作通常称为入队操作，而删除操作通常称为出队操作，如图3-12所示。
图3-12 队列及其操作
C0 3-2-1
队列在现实生活中处处可见，例如：人在食堂排队买饭、人在车站排队上车等。这些排队都满足一个规则，就是按先后次序，后来的只能到队伍的最后排队，先来的先处理再离开，不能插队。在生产建设中也有队列的应用，例如：生产计划的调度就是根据一个任务队列进行的。队列也经常应用于计算机领域中，例如：操作系统中存在各种队列，有资源等待队列、作业队列等。
3.2.2 队列的抽象数据类型描述
队列也是由n（n≥0）个具有相同类型的数据元素所构成的有限序列。队列的基本操作与栈类似。队列的抽象数据类型描述如下：
ADT Queue{
数据对象：D={ai|ai∈QElemType，1≤i≤n，n≥0，QElemType是约定的队列中数据元素类型，使
用时用户需根据具体情况进行自定义}
数据关系：R={＜ai，ai+1＞|ai，ai+1∈D，1≤i≤n-1，并约定其中a1为队首元素，an为队尾元素}
基本操作：
InitQueue（&Q）：初始化操作，创建一个空队列Q。
DestroyQueue（&Q）：销毁操作，释放一个已经存在的队列Q的存储空间。
ClearQueue（&Q）：清空操作，将一个已经存在的队列Q置为空队列。
QueueEmpty（Q）：判空操作，判断队列Q是否为空。若为空，则函数返回TRUE；否则，函数返回
FALSE。
QueueLength（Q）：求队列的长度操作，求队列Q中数据元素的个数并返回其值。
GetHead（Q，&e）：取队首元素操作，读取队首元素，并用e返回其值。
EnQueue（&Q，e）：入队操作，将数据元素e插入队列Q中，并使其成为新的队尾元素。
DeQueue（&Q，&e）：出队操作，删除队首元素并用e返回其值。
DisplayStack（Q）：输出操作，输出队列Q中各个数据元素的值。
}ADT Queue
同栈一样，队列也可用顺序和链式两种存储结构表示。顺序存储的队列称为顺序队列，链式存储的队列称为链队列。
3.2.3 顺序队列及其基本操作的实现
1．顺序队列的存储结构描述
与顺序栈类似，在队列的顺序存储结构中，需要分配一块地址连续的存储区域来依次存放队列中从队首到队尾的所有元素。这样也可以使用一维数组来表示，假设数组的首地址为base，最大容量为MAXQSIZE。由于队列的入队操作只能在当前队列的队尾进行，而出队操作只能在当前队列的队首进行，所以为了操作方便需加上变量front和rear来分别指示队首和队尾元素在数组中的位置。它们的位置可以说明为指针类型，也可以说明为整型。当说明为指针类型时，则意味着它们指示队首元素和队尾元素在数组中的存储单元地址；当说明为整型时，则意味着它们分别指示队首元素和队尾元素在数组中的下标。现假定front和rear为整型变量且在非空队列中，front指示队首元素的存储位置，rear指示队尾元素的下一个存储位置，则在初始化空队列时，front和rear的初始值都为0。顺序队列的动态存储结构描述如下：
#define MAXQSIZE 1 00 //队列可能的最大长度
typedef struct {
QElemType *base； //队列存储空间基地址
int front； //指示队首元素存储单元的位置（队首指针）
int rear； //指示队尾元素的下一存储单元的位置（队尾指针）
}SqQueue；
其中，SqQueue为顺序队列的类型名。根据上述描述，对于非空队列Q=（39，17，30，65，35，54）初始状态的顺序存储结构可用图3-13表示。
图3-13 顺序队列Q初始状态的存储结构
特别说明：
对于已知如图3-13所示的顺序队列Q，其存储空间基地址的直接访问形式为Q.base；队首指针的直接访问形式为Q.front，它的值即为队首元素在数组中存储单元的下标；队尾指针的直接访问形式为Q.rear，它的值即为队尾元素在数组中下一存储单元的下标；队首元素的直接访问形式为Q.base[Q.front]；队尾元素的直接访问形式为Q.base[Q.rear-1]。
图3-14是一个在容量MAXQSIZE=6的顺序队列Q上进行入队、出队操作后的动态示意。
图3-14 顺序队列的入队、出队操作的动态示意
图3-14中描述了一个从空队列开始，先后经过A，B，C入队，A，B出队，E，F，G入队操作后，队列的顺序存储结构状态。
初始化队列时，令Q.front=Q.rear=0；入队时，直接将新的数据元素存入Q.rear所指的存储单元中，然后将Q.rear值加1；出队时，直接取出Q.front所指的存储单元中数据元素的值，然后将Q.front值加1。
再仔细观察图3-14（d），若此时还需将数据元素H入队，H应该存放于Q.rear=6指示的位置处，顺序队列则会因数组下标越界而引起“溢出”，但此时顺序队列的首部还空出了两个数据元素的存储空间。因此，这时的“溢出”并不是由于数组空间不够而产生的溢出。这种因顺序队列的多次入队和出队操作后出现有存储空间，但不能进行入队操作的溢出现象称为“假溢出”。
要解决“假溢出”问题，最好的办法就是把顺序队列所使用的存储空间看成是一个逻辑上首尾相连的循环队列。当Q.rear或Q.front到达MAXQSIZE-1后，再加1就自动到0。这种转换可利用C语言中对整型数据求模（或取余）运算来实现，即令Q.rear=（Q.rear+1）% MAXQSIZE。显然，当Q.rear=MAXQSIZE-1时，Q.rear加1再与MAXQSIZE求模运算后，Q.rear的值就为0。这样，就可有效避免出现顺序队列数组的头部有空的存储空间，而队尾却因数组下标越界而引起的假溢出现象。
2．循环顺序队列基本操作的实现
1）循环顺序队列的初始化操作
循环顺序队列的初始化操作InitQueue（&Q）的基本要求是创建一个空的循环顺序队列。仍然假设MAXQSIZE=6，循环顺序队列的初始化状态如图3-15（a）所示，此时有Q.front=Q.rear=0。要完成此操作的主要步骤可归纳如下：
图3-15 循环顺序队列Q的四种状态
①分配预定义大小的数组空间。用于存放队列中各数据元素的数组空间通过函数malloc进行分配，空间的大小仍遵守“足够应用”的原则。在此是通过符号常量MQXQSIZE表示，其值根据队列可能的最大长度值进行预先设定。
② 如果空间分配成功，则置队首和队尾指针值为0。
说明：如果假定队首指针指示队首元素的位置，而队尾指针指示队尾元素的位置，则队列初始化时应置队首指针值为0，而队尾指针值为-1。
【算法3-13】循环顺序队列的初始化操作算法
C0 3-2-2
Status InitQueue（SqQueue&Q）
//创建一个空的循环顺序队列Q
{ Q.base=（QElemType*）malloc（MAXQSIZE*sizeof（QElemType））；
if（!Q.base）exit（OVERFLOW）； //如果空间分配失败
Q.front=Q.rear=0；
return OK；
} //算法3-13 结束
如图3-15（a）所示的队列，当A，B，C，D，E，F分别入队后，循环顺序队列为满，如图3-15（b）所示，此时有条件Q.front==Q.rear为真；当A，B，C，D，E出队，而G，H又入队后，循环顺序队列的状态如图3-15（c）所示，此时Q.front=5，Q.rear=2；再将F，G，H出队后，循环顺序队列为空，如图3-15（d）所示，此时也有条件Q.front==Q.rear为真。为此，在循环顺序队列中就引发出一个新的问题：无法区分队空和队满的状态，这是因为循环顺序队列的队空和队满时都具备条件Q.front==Q.rear为真。
解决循环顺序队列的队空和队满的判断问题通常可采用如下3种方法：
（1）少用一个存储单元。
当队列顺序存储空间的容量为MAXQSIZE时，只允许最多存放MAXQSIZE-1个数据元素。如图3-16所示为这种情况下的队空和队满的两种状态。此时：
图3-16 少用一个存储单元时循环顺序队列Q的两种状态
队空的判断条件为Q.front==Q.rear；
队满的判断条件为Q.front==（Q.rear+1）% MAXQSIZE。
（2）设置一个标志变量。
如果希望循环队列中的空间都得到利用，可以在程序设计过程中引进一个标志变量flag，其初始值置为0。每当入队操作成功后就置flag=1；每当出队操作成功后就置flag=0。此时：
队空的判断条件为Q.front==Q.rear && flag==0；
队满的判断条件为Q.front==Q.rear && flag==1。
（3）设置一个计数器。
如果希望循环队列中的空间都得到利用，也可以在程序设计过程中引进一个计数变量num，其初始值置为0。每当入队操作成功后就将计数变量num的值加1；每当出队操作成功后就将计数变量num的值减1。此时：
队空的判断条件为Q.front==Q.rear&& num==0或num==0；
队满的判断条件为Q.front==Q.rear && num!=0或num==MAXQSIZE。
下面假定在采用第二种方法区分队空和队满判断条件的前提下，给出循环顺序队列的入队、出队和求长度操作的实现方法及其算法描述。其中，标志变量flag说明为全局整型变量，并置初值为0。
2）循环顺序队列的入队操作
入队操作EnQueue（&Q，e）的基本要求是将新的数据元素e插入循环顺序队列Q的尾部，使其成为新的队尾元素。实现此操作的主要步骤归纳如下：
① 判断循环顺序队列是否为满，若满，则报告队列状态后结束算法，否则转②。
② 先将新的数据元素e存入Q.rear所指示的数组存储位置中，使其成为新的队尾元素，再将Q.rear值循环加1，使Q.rear始终指向队尾元素的下一个存储位置。实现这一步骤的操作语句为
Q.base[Q.rear]=e； //将e存入Q.rear所指的数组存储单元中
Q.rear=（Q.rear+1）% MAXQSIZE；//Q.rear值循环加 1
C0 3-2-3
【算法3-14】循环顺序队列的入队操作算法
Status EnQueue（SqQueue&Q，QElemType e） //设置一个标志变量的方法
//在循环顺序队列Q中插入新的元素e，使其成为新的队尾元素
{ if（Q.front==Q.rear&&flag==1） //当前队满
{ printf（"The Queue is OVERFLOW!\n"）；
return ERROR；
}
Q.base[Q.rear]=e； //e入队
Q.rear=（Q.rear+1）%MAXQSIZE； //队尾指针下移一位
flag=1； //标志变量置为入队状态
return OK；
}//算法3-14 结束
3）循环顺序队列的出队操作
出队操作DeQueue（&Q，&e）的基本要求是将队首元素从循环顺序队列Q中移去，并用e返回被移去的队首元素的值。实现此操作的主要步骤归纳如下：
① 判断循环顺序队列是否为空，若为空，则报告队列状态后结束操作，否则转②。
② 先读取Q.front所指示的队首元素的值并用e保存，再将Q.fornt值循环加1，使其指向新的队首元素。实现这一步骤的操作语句为
e=Q.base[Q.front]； //取出队首元素并用e保存
Q.front=（Q.front+1）%MAXQSIZE； //队首指针下移一位
【算法3-15】循环顺序队列的出队操作算法
C0 3-2-4
Status DeQueue（SqQueue&Q，QElemType&e） //设置一个标志变量的方法
//删除循环顺序队列Q中的队首元素，并用e返回其值
{
if（Q.front==Q.rear&&flag==0） //当前队空
{ printf（"The Queue is NULL!\n"）；
return ERROR；
}
e=Q.base[Q.front]； //用e返队首元素
Q.front=（Q.front+1）%MAXQSIZE； //队首指针下移一位
flag=0； //标志变量置为出队状态
return OK；
}//算法3-15 结束
思考：请分别写出采用第一种和第三种方法区分队空和队满条件时，循环顺序队列的入队和出队操作算法。
4）循环顺序队列求长度操作
由图3-15（b）可知，当队列为满时，队列的长度就是MAXQSIZE；而在一般情况下，队列的长度可以根据队列的队尾指针和队首指针值计算而得。
【算法3-16】循环顺序队列求长度操作算法
int QueueLength（SqQueue Q）//设置一个标志变量的方法
//返回循环顺序队列中数据元素的个数
{ if（Q.front==Q.rear&&flag==1）
return MAXQSIZE；
else
return（Q.rear-Q.front+MAXQSIZE）%MAXQSIZE；
}//算法3-1 6 结束
补充说明：若采用第一种方法区分队空和队满条件时，无论何时，队列的长度都可采用（Q.rear-Q.front+MAXQSIZE）%MAXQSIZE计算而得；若采用第三种方法区分队空和队满条件时，其中num的值就随时记录着队列的长度。
从上述算法描述可知：顺序队列上述操作算法的时间复杂度都为O（1）。
3.2.4 链队列及其基本操作的实现
1．链队列的存储结构描述
队列的链式存储结构用带头结点的单链表来实现。为了便于实现入队和出队操作，需要引进两个指针front和rear来分别指向队首元素和队尾元素的结点。现将链队列的存储结构描述如下：
typedef struct QNode
{ QElemType data；
struct QNode *next；
}QNode，*QueuePtr； //链队列的结点类型及指向结点的指针类型
typedef struct
{ QueuePtr front； //队首指针
QueuePtr rear； //队尾指针
}LinkQueue； //链队列类型
图3-17为空队列和非空队列a1，a2，…，an的链式存储结构。
图3-17 链队列的存储结构
2．链队列基本操作的实现
结合链队列的存储结构示意图，并借鉴第2章中，在带头结点的单链表上实现基本操作的主要步骤和算法描述，再来思考链队列相应操作的算法设计还是比较容易的。在此只要记住队列的入队操作是在链表的表尾进行，而出队操作则是在链表的表头进行；对于一个空队列来说，其链中只含一个头结点，而且队首指针和队尾指针都指向头结点，如图3-17（a）所示。因此，链队列的判空条件是Q.rear==Q.front。下面也只讨论链队列的初始化、入队、出队的实现方法及其算法描述。
1）链队列初始化操作
由图3-17（a）可知，要创建一个空的链队列，只要为头结点分配一个结点大小的空间，并使队首指针和队尾指针都指向该结点即可。
C0 3-2-5
【算法3-17】链队列初始化操作算法
Status InitQueue（LinkQueue&Q）
//创建一个空链队列Q（带头结点）
{ Q.front=（QueuePtr）malloc（sizeof（QNode））； //为链队列的头结点分配空间
if（! Q.front）
return OVERFLOW； //分配空间失败
Q.front-＞next=NULL；
Q.rear=Q.front； //使队尾指针也指向头结点
return OK；
}//算法3-1 7 结束
2）链队列的入队操作
链队列入队操作EnQueue（&Q，e）的基本要求是将数据元素e所对应的结点插入到链队列的尾部，使其成为新的队尾结点。此操作的基本思想与带头结点的单链表上的插入操作类似，不相同之处为链队列的插入位置是限制在表尾进行。实现此操作的主要步骤归纳如下：
① 创建数据域值为e的新结点。
② 修改链，使新结点链接到队列的尾部并使其成为新的队尾结点。
图3-18显示了链队列入队操作后状态的变化情况。
图3-18 链队列的入队操作后状态变化
【算法3-18】链队列的入队操作算法
C0 3-2-6
Status EnQueue（LinkQueue&Q，QElemType e）
//在链队列的队尾插入新的元素e，使其成为新的队尾元素
{ QueuePtr p=（QueuePtr）malloc（sizeof（QNode））；//为新结点分配空间
if（!p） //空间分配失败
return ERROR；
p-＞data=e； //e存入新结点的数据域
p-＞next=Q.rear-＞next； //修改链①，让新结点插入链队列的尾部
Q.rear-＞next=p；
Q.rear=p； //修改链②队尾指针使其指向新的队尾结点
return OK；
}//算法3-18 结束
3）链队列的出队操作
链队列出队操作DeQueue（&Q，e）的基本要求是将非空队列中的队首结点从链队列中移去，并通过e返回被移去结点的数据元素值。此操作的基本思想也与带头结点的单链表上删除操作类似，不相同之处为链队列出队的结点一定是链中第一个数据元素结点。实现此操作的主要步骤归纳如下：
① 判断链队列是否为空，若为空，则报告队列状态后结束算法，否则转②。
② 用p指针指向待删除的队首结点，并用e保存其数据元素值。
③ 修改链指针，使队首结点从链队列中脱离出来。
④ 若待删除结点既是队首结点，又是队尾结点时，则需修改队尾指针，使队列为空。
⑤ 释放被删结点空间。
C0 3-2-7
【算法3-19】链队列的出队操作算法
1 Status DeQueue（LinkQueue&Q，QElemType&e）
2 //删除链队列中的队首数据元素，并用e返回其值
3 { if（Q.front==Q.rear） //队空
4 { printf（"The Queue is NULL!\n"）；
5 return ERROR；
6 }
7 QueuePtr p=Q.front-＞next； //p指针指向待删除的队首结点
8 e=p-＞data； //用e保存队首结点的数据元素值
9 Q.front-＞next=p-＞next； //修改链指针，使队首结点从链中脱离
1 0 if（p==Q.rear） //如果被删的结点是队尾结点
1 1 Q.rear=Q.front；
12 free（p）； //释放待删结点空间
13 return OK；
14 }//算法3-19 结束
注意：在链队列中执行出队操作时，如果当前链队列只含一个数据元素结点，则待删除的结点既是队首结点，也是队尾结点。当此结点被删除后，则变成了一个空的链队列，所以此种情况下需修改队尾指针，使其与队首指针同指向队列的头结点，这就是算法3-19中第10～11行所描述的真正含义，请读者加以重视。
从上述算法描述可知，链队列的初始化，入队和出队操作算法的时间复杂度都为O（1）。
3.2.5 其他队列
1．优先级队列
在很多情况下，利用简单队列往往是不能解决问题的，队列的先进先出还应受到优先级的限制。例如：在车站排队买车票时，残疾人可以优先于其他人先买，即当售票员工作时，尽管还有人排在队伍的前面，残疾人仍可以优先得到服务。又如：在计算机系统中，为了保证系统的正常运行和系统资源的有效利用，即使程序p1比程序p2早进入等待队列，p2仍可在p1之前运行。这些情况都需要使用优先级队列。
优先级队列是一种带有优先级的队列。优先级可以反映使用频率、生日、工资、职位等不同的优先规则，也可以是程序队列中的预估运行时间。通常用数字来代表优先级，数字值越小表示优先级越高。
优先级队列可以用两种链表来表示。一种是优先级队列中的元素按优先级从高到低有序排列，也就是说优先级最高的总是排在队首。因此，在优先级队列中也是从队首删除元素，但元素的插入不一定是在队尾进行，而是顺序插入队列的合适位置，以确保队列的优先级顺序。另一种是优先队列中的元素按顺序进入队尾，而删除元素则要从优先队列中选择优先级最高的元素出队。这两种情况下的总操作时间复杂度都是O（n），这是因为在按优先级有序排列的队列中，可以立即从队首取出一个元素出队，但入队操作需要的时间复杂度是O（n），而在未按优先级排序的队列中，可以立即插入一个元素到队尾，但出队操作需要的时间复杂度是O（n）。
例如，计算机操作系统用一个优先队列来实现进程的调度管理。在一系列等待执行的进程中，每一个进程可以用一个数值来表示它的优先级，优先级越高，这个值越小。优先级高的进程应该最先获得处理器。假设操作系统中每个进程的数据由进程号和优先级两部分组成。进程号是每个不同进程的唯一标识；优先级通常是一个0到40的数值，规定0为优先级最高，40为优先级最低。如下为一组模拟数据：
进程号 优先级
1 2 0
2 40
3 0
4 1 0
5 40
则当前按优先级从高到低所形成的优先队列存储结构可用图3-19表示。
图3-19 优先队列的存储结构
思考：请读者按如图3-19所示的存储结构示意图，写出其存储结构的类型描述，并设计此优先队列的入队操作算法（出队操作的算法与一般队列的相同）。
2．双端队列
双端队列也是一种操作受限的线性结构。
（1）双端队列：指允许两端都可以进行入队和出队操作的队列，其两端分别被称为前端和后端，两端都可以进行入队和出队操作，如图3-20所示。在双端队列上实现入队操作时，前端进的元素排列在队列中后端进的元素的前面，后端进的元素排列在队列中前端进的元素的后面；在双端队列上实现出队操作时，无论在前端还是后端出队，先取出的元素排列在后取出的元素的前面。
图3-20 双端队列
（2）输出受限的双端队列：指允许在一端进行出队操作，但允许两端进行入队操作的双端队列，如图3-21和图3-22所示。
图3-21 输出受限的双端队列（1）
图3-22 输出受限的双端队列（2）
（3）输入受限的双端队列：指允许在一端进行入队操作，但允许在两端进行出队操作的双端队列，如图3-23和图3-24所示。如果限定双端队列从某端插入的元素只能从该端删除，则该双端队列就蜕变为两个栈底相邻接的栈了。
图3-23 输入受限的双端队列（1）
图3-24 输入受限的双端队列（2）
若以1，2，3，4作为双端队列的输入序列，满足以下条件的输出序列有：
（1）能由输入受限的双端队列得到，但不能由输出受限的双端队列得到的输出序列为：4，1，3，2。
（2）能由输出受限的双端队列得到，但不能由输入受限的双端队列得到的输出序列为：4，2，1，3。
（3）既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列为：4，2，3，1。
3.2.6 队列的应用
由于队列是一种具有先进先出特性的线性表，所以在现实世界中，当求解具有先进先出特性的问题时可以使用队列。例如：操作系统中各种数据缓冲区的先进先出管理，应用系统中各种任务请求的排队管理，软件设计中对树的层次遍历和对图的广度遍历过程等，都需使用队列。队列的应用非常广泛，本节通过两个实例来说明队列在解决实际问题中的应用。
【例3-6】设计算法，借助队列计算并打印杨辉三角形的前n行内容，如图3-25所示为8行的杨辉三角形。
图3-25 杨辉三角形
【分析】从图中观察可知，在杨辉三角形中，每行第一个和最后一个数都是1，从第3行开始的其余数等于上一行对应位置的左、右两个数之和。例如，第3行的第2个数2是第2行的第1个数1和第2个数1的和；第6行的第3个数10是第5行的第2个数4和第5行的第3个数6的和。也就是说，除每行的第一个数和最后一个数之外，其他数都可由上一行对应位置的两个数求出。为此，可以借助一个队列来存放上一行的数，每次由队列前两个数来求出下一行的一个数，运算完成后需将参与运算的当前队首数删除（出队），而运算结果再加入队列的尾部（入队）。
注意：
（1）为了能正确求出从第2行起，每一个行的第一个数1，需要在上一行的第一个数前面加一个0。例如：图3-26展示了由第7行求得第8行对应数的过程。
图3-26 杨辉三角形第8行的求解过程
（2）每行的最后一个1不能通过上一行计算而得，所以只能直接输出这个1。
【算法3-20】例3-5中设计的相关算法
void OutYangHuiSanJiao（int n）
{ int s1，s2，s；
SqQueue Q；
InitQueue（Q）；
for（int i=1；i＜=4*（n-1）；i++） //输出第 1 行数 1 左边的空格
printf（""）；
printf（"%8d\n"，1）； //输出第 1 行上的数 1
EnQueue（Q，1）； //输出的 1 入队
for（int i=2；i＜=n；i++）
{ s1=0； //存放前一个出队的数
for（int k=1；k＜=n*4-4*i；k++）//输出第i行第一个数左边的空格
printf（""）；
for（int j=1；j＜=i-1；j++） //计算并输出第i行的数据
{ DeQueue（Q，s2）； //队首元素出队
s=s1+s2； //计算出第i行中的一个数
printf（"%8d"，s）； //输出第i行中的一个数
EnQueue（Q，s）； //输出的数入队
s1=s2；
}
printf（"%8d\n"，1）； //输出第i行的最后一个 1
EnQueue（Q，1）； //第i行最后一个 1 入队
}
}//算法3-20 结束
【例3-7】设计算法：实现求解素数环问题。
【问题描述】将1～n的n个自然数排列成环形，使得每相邻两数之和为素数，从而构成一个素数环。例如：当n=6时，其素数环为1，4，3，2，5，6；而当n=8时，其素数环为1，2，3，8，5，6，7，4。
【问题分析】由问题描述可知，当n为奇数时，素数环一定不存在，所以可先排除此情况。对于偶数n，则可借助线性表和队列的基本操作来求解此问题。本题是采用顺序表和顺序队列，其中顺序表是用来存放加入素数环中的自然数，而顺序队列是用来存放求解过程中还未加入素数环中的自然数。首先将自然数1加到素数环中，2～n加入队列中。然后再依次判断2～n中的每个自然数能以何种顺序加入素数环。主要的步骤可归纳如下：
（1）先创建一个空顺序表L和空顺序队列Q。
（2）将顺序表L和顺序队列Q置上初值：将1加入顺序表L中，将2～n的自然数全部加入Q队列中。
（3）将队列Q的队首自然数p出队，并与素数环L中的最后一个自然数q相加。若两数之和是素数，则将p加入素数环L中，否则说明p暂时无法处理，必须再次入队等待，重复此过程。若p为队列中最后一个自然数，则还需判断它与素数环的第一个自然数相加的和是否为素数。若是素数，则将p加入素数环，素数环构造成功，其结果以顺序表的值返回，求解结束；若不是素数，则说明不满足素数环条件，需将素数环中的最后一个自然数移至队列的尾部，再重复（3）。如此重复，直到队列为空或已对队列中每一个数据元素都遍历了一次且未能加入素数环为止，此时意味着构造素数环不成功。
【算法3-21】例3-7中设计的相关算法
bool IsPrime（int num）
//判断正整数num是否为素数
{ if（num==1） //整数 1 返回false
return false；
int n=（int）sqrt（num）； //求平方根
for（int i=2；i ＜=n；i++）
if（num% i==0） //模为 0 返回false
return false；
return true；
}//IsPrime
int InsertRing（SqList&L，SqQueue Q，int m，int n）
//判断队列Q中的队首自然数是否能加入素数环L，若能则加入并返回 1，否则返回 0
//其中素数环L中有m-1个自然数，队列Q中有n-m个自然数
{
int count=0；//记录遍历队列中的数据元素的个数，防止在一次循环中重复遍历
while（! QueueEmpty（Q）&&count ＜=n-m） //队列非空，且未重复遍历队列中的自然数
{ int p；
DeQueue（Q，p）； //队首自然数p出队
int q；
GetElem（L，ListLength（L），q）； //q为顺序表中的最后一个数据元素
if（m==n） //为队列中的最后一个自然数
{ if（IsPrime（p+q）&&IsPrime（p+1）） //满足素数环的条件
{ ListInsert（L，ListLength（L）+1，p）；//将p插入顺序表表尾
return 1；
}
else //不满足素数环条件
EnQueue（Q，p）； //p重新入队
}
else if（IsPrime（p+q））//未遍历到队列的最后一个自然数，且满足相邻数和为素数条件
{ ListInsert（L，ListLength（L）+1，p）；//将p插入顺序表表尾
//递归调用函数，若返回值不为 0，即已成功找到素数环，返回 1
if（InsertRing（L，Q，m+1，n）!=0）
return 1；
ListDelete（L，ListLength（L），p）； //删除顺序表表尾的自然数p
EnQueue（Q，p）； //并将p重新入队
}
else
EnQueue（Q，p）； //p重新入队
++count； //遍历次数加 1
}
return 0；
}//InsertRing
voidMakePrimeRing（SqList&L，int n）
//求n个正整数的素数环，结果以顺序表L返回
{ if（n% 2 !=0） //n为奇数则素数环不存在
{ printf（"素数环不存在!\n"）；
exit（0）；
}
ClearList（L）； //清空已知的顺序表L
ListInsert（L，1，1）； //将自然数 1 加入表L中
SqQueue Q；
InitQueue（Q）； //创造一个空队列
for（int i=2；i ＜=n；i++） //将自然数2～n分别加入队列
EnQueue（Q，i）；
InsertRing（L，Q，2，n）；
}//算法3-2 1 结束