假期连载之六
（限定性线性表——队列，一个初级迷宫解法的讨论及延伸B）
本节我们介绍另外一个重要的线性表——队列。首先会讨论队列的几种不同的存储结构，以及相关结构的基本运算问题，最后，我们会对连载五中介绍的迷宫Maze解法进行第一步优化工作。
队列Queue
与栈相类似，队列也是一种限定存储位置的线性表。它只允许在表的一端插入，在另一端删除。通常把允许插入的一端称为队尾Rear，而把允许删除的一端称为队头Front。队列所具有的这种特性就被称为先进先出First in First out。
首先给出队列的抽象数据类型定义：
ADT Queue
{
InitQueue(&Q); //队列初始化
IsEmpty(Q); //判空操作，为空返回TRUE，否则返回NULL
IsFull(Q); //与上相反
EnterQueue(&Q,x); //进队操作，在队列Q的队尾插入x
DeleteQueue(&Q,&x); //出队操作，用x取得队头元素的值
GetHead(Q,&x); //取对头元素操作，同样用x取得，成功则返回TRUE，否则返回NULL
ClearQueue(&Q); //队列置空操作
DestoryQueue(&Q); //队列销毁操作
}
相应地，队列也分为顺序存储和链式存储两种表示形式，但这与其它线性表中所定义的顺序表和链表有所不同，需要注意。
循环队列
循环队列是一种基于数组的顺序队列。对于数组队列elements[maxSize]，我们首先设置其队头和队尾指针front和rear。初始化后front=rear=0。当加入新元素时，先将新元素加入rear所在位置，并使rear进1。如果要退出对头元素，应当前将front位置的元素记录下来，并且使front进1，这就构成了顺序队列的基本运算原理。
由于顺序队列的特性，其最大空间固定，且随着front递增，其front位置不断进1，逻辑上造成队列所能容纳元素个数的逐步递减。为了能充分利用数组空间，一般将数组的前端和后端连接起来，形成一个环形的表，当front和队尾指针rear进到maxSize-1后，再前进一个位置就自动到0，这就是循环队列circular queue。
判断是否进1或为0的方法如下：
front=(front+1)%maxSize;
rear=(rear+1)%maxSize;
同时为了避免当队列满时发生rear==front的情况，还应增加一个判断队列是否已满的条件：
(rear+1)%maxSIze==front;
下面给出C语言描述的队列入队出队操作：
int EnterQueue(SeqQueue *Q,QueueElementType x)
{
if((Q->rear+1)%maxSize==Q->front)
return FALSE;
Q->element[Q->rear]=x;
Q->rear=(Q->rear+1)%maxSize;
return TRUE;
}
int DeleteQueue(SeqQueue *Q,QueueElementType *x)
{
if((Q->rear==Q->front)
return FALSE;
*x=Q->element[Q->front];
Q->front=(Q->front+1)%maxSize;
return TRUE;
}
这里另外给出一个C++队列类中对于一次输出队列中所有元素值的方法函数，其原理是对<<运算符进行了重载，这在需要顺序输出的数据结构算法中经常用到。
friend ostream& operator << (ostream& os,SeqQueue<T>& Q)
{
os<<”font=”<<Q.front<<”,rear=”<<Q.rear<<endl;
for(int i=front;i!=rear;i=(i+1)%maxSize)
os<<i<<”:”<<Q.elements[i]<<endl;
return os;
}
链式队列
顾名思义，链式队列是基于单链表的一种存储表示。链式队列的优点在于，由于单链表本身可以设置队头指针和队尾指针，因而其入队出队运算非常方便，同时由于不存在队列满的情况，故实际应用上比循环链表的性能更好。在一些需要多个队列的程序中，大多数使用链式存储方式，相较循环队列而言将大大节约系统资源。
由于链式队列的代码与循环队列、单链表操作较为相似，因此这里就不再详述。
在OS的process scheduling机制中我们了解到，系统对于就绪队列的操作方法有很多种，并不限于FCFS形式，例如SPF。这说明在一些高级别算法中，产生了一种区别于传统意义上的队列，有时统称为优先级队列Priority Queue。这种队列的应用同样非常广泛。
优先级队列可以为最大优先级队列，也可以是最小优先级队列，以需求不同而论。其一般原理是，当队列初始化后，新元素首先放至队尾，然后调用调整函数。调整函数是一个从队末向队首递增的迭代算法，旨在比较当前元素与新插入元素的优先级大小，如果新元素优先级较高，则与当前元素互换位置，类似于一次冒泡排序。由于算法涉及到了循环操作，其时间复杂度达到了O(n)，为了进一步提升算法性能，今后我们会介绍一种最高效的优先级队列存储结构“堆”，它将使类似算法的性能有较大提高。
双端队列
我们在连载四中给出了双端栈Destack的概念，其目的主要是为了解决一个程序中应用两个栈时存在的空间利用问题。这里介绍的双端队列Double-ended Queue，与最初引入双端栈的目的并不一致，主要是为了提供一种算法更为灵活的存储结构。但了解双端队列后可以知道，双端栈有时也是双端队列的一类特例。
双端队列，即队列本身并不拘泥于FIFO规则，有可能为两端均能执行插入、删除操作，也有可能插入、删除操作在一端执行、另一端只执行插入操作。这种形式对于栈、一般队列来说灵活的多。
但是，在实际应用中我们会发现大量类似于栈或者队列的存储结构，却很少能碰到有双端对列类似要求的结构，因此其实际利用度并不十分高。尽管如此，这并不影响双端队列被列为第三种限定性线性表结构，这也是引入本部分的目的。
初级迷宫Maze解法的优化讨论
现在我们回顾上节内容中介绍的一个初级迷宫解法。在上一节我们介绍了在解决简单二维迷宫时一般用到的两种算法——递归回溯和栈回溯。我们知道，栈回溯相较于递归回溯而言算法性能上得到了提高，并且在智能化扩展上也有了很大进步。但是我们同样意识到，由于算法的原理是在不断探索中，一旦发现终点则退出，就可能产生解出的路径是否为最优解的问题。
事实上连载五中程序结果显示的例子证明，其最终路径并不是路程最短的解。
为了解决这一问题，通常需要在发现终点后，要根据起点和终点及其相互联系区域之间所存在的关系而定。
1 1 1 1 1 1
0 0 1 1 0 1
1 0 0 1 1 1
1 1 0 1 0 1
1 0 1 0 0 0
1 1 1 1 1 1
首先我们假定起点Maze[1][0]的值为2，把与起点相邻的方格标记为3…依次类推，直到探索出终点位置，为此我们得到以下矩阵：
1 1 1 1 1 1
2 3 1 1 0 1
1 3 4 1 1 1
1 1 4 1 6 1
1 5 1 5 6 7
1 1 1 1 1 1
根据以上数据可知最优解的路径总数为7-2=5，此时我们从终点出发，选择相邻小于1的元素作为路径点，并按此规律回溯到起点。最终所能得出的路径即为最优路径。
值得注意的是，由于规则和迷宫形态的不确定性，有时可能会出现多条最优解的情况，但这恐怕也就说明了该迷宫的复杂度较低吧。
这里选择队列作为本算法的存储表示，那么除了要参考栈的迭代回溯算法的原理之外，另需构建一个双循环回溯算法，下面仅提供该部分内容：
for(j=PathLen-1;j>=0;j–)
//nbr为下一个移动的目标元素，offsets[]为前进方向表，here为当前位置，grid为保存探索中已经过元素的矩阵
{
for(i=0;i<NumOfNbs;i++)
{
nbr.row=here.row+offsets[i].row;
nbr.col=here.col+offsets[i].col;
if(grid[nbr.row][nbr.col]==j+2)
break;
}
here=nbr;
}
这里我们仅介绍一种简单的迷宫最优解的解法，并不涉及到高级算法设计中关于最优解的讨论，但由于本部分内容实际上为ACM的重要组成部分，因此在今后的连载中我们将予以详细说明。
(未完待续)