一，队列的定义与形式
队列是线性表的一种特例，它是一种限定在表的一端进行插入而在另一端进行删除的线性 表，并且也分为顺序结构和链式结构。其中，在队列中，允许删除的一端称为对头，允许插入的一端称为队尾，向队列中插入新元素称为入队，从列队中删除元素称为出队。如图：
由图可知，队的逻辑结构反映了“先来先服务”的原则，在平常遇到的复杂问题中像“排队”问题的，基本就需要队列的形式结构。
因为队需要表明队头和队尾，所以在创建队的时候要对头结点和为结点进行标明，在这里，我用链式队列的结构跟大家演示队的基本结构框架：
typedef int Datatype;
typedef struct node//队的结点
{
Datatype a;
struct node* next;
}link;
typedef struct queue//队列的结构
{
link* front;
link* end;
}Queuelink;
二，队列的几种基本运算
首先说明的是，队列既然属于线性表，那么队列的基本运算也就是线性栈的几种运算，其中最为常用的是入队和出队算法，下面我以链式结构为例。
（1）入队算法：在对的末尾进行插入，将队尾指针重新指向新的管理空间。
void Inqueue(Queuelink* p, Datatype n)
{
link* pa, * pp;
pa = (link*)malloc(sizeof(link));
pp = (link*)malloc(sizeof(link));
pa->a = n;
pa->next = pp;
pp->a = pp->next = 0;
p->end->next->next = pa;
p->end->next = pa;
}
（2）出队算法：将对头指针指向下一个元素空间，然后解放上一个地址空间即可。
void Outqueue(Queuelink* p)
{
link* pa;
pa = (link*)malloc(sizeof(link));
pa = p->front->next->next;
free(p->front->next);
p->front->next = pa;
}
需提醒一下，一般情况下，删除对头元素时，仅修改头结点中的指针，但当队列中的最后一个元素被删除后，队列尾指针也就丢失了，因此需要队尾指针重新赋值。至于其它的基本算法跟顺序栈几乎如出一辙，在这里不做过多详解。
三，队列的运用
队列在算法应用中其实也是非常广泛的，因为队列的特殊限定结构，所以在计算机所设计的优先原则中，都需要运用队列来解决，只不过目前的所学中只是基础阶段。下面，我们将运用队列中的典型例子的算法，迷宫问题：
#include<stdio.h>
#define m 10
#define n 15
#define num m*n
int maze[m + 1][n + 1];
typedef struct note
{
int x, y;//x,y为到达点的坐标
int pre;//pre为（x，y）的前趋点在数组sq中的下标
}sqtype;
typedef struct link
{
int dx;
int dy;
}moved;
void shortpath(int maze[m][n], moved move[8])
{
sqtype sq[num];
int front, end;
int x, y, i, j, v;
front = end = 0;
sq[0].x = 1;
sq[0].y = 1;
sq[0].pre = -1;
maze[1][1] = -1;
while (front <= end)
{
x = sq[front].x;
y = sq[front].y;
for (v = 0; v < 8; v++)
{
i = x + move[v].dx;
j = x + move[v].dy;
if (maze[i][j] == 0)
{
end++;
sq[end].x = i;
sq[end].y = j;
sq[end].pre = front;
maze[i][j] = -1;
}
if (i == m && j == n)
{
print(sq, end);
restore(maze);
return 1;
}
}
front++;
}
return 0;
}
void print(sqtype sq[], int end)//路径算法，打印迷宫的路径
{
int i = end;
do
{
fprintf(stdout, "(%d, %d)?", sq[i].x, sq[i].y);
i = sq[i].pre;
} while (i != -1);
}
由以上的算法程序可看出，队列虽然学起来非常简单，但在实际的问题运用的其实并不好运用，我们不仅要学会知识，更应该要学会如何灵活的使用。而在本问题的算法中，先将队列中保留探索到的路径序列，然后运用队列的逻辑将其记录。
