1、和栈相反，队列是一种先进先出（first in first out，缩写为FIFO）的线性表，它只允许在表的一端插入，在表的另一端删除元素。其中允许插入的一段称为队尾，允许删除的一端则称为对头。
2、用链表表示的队列称为链队列，一个链队列显然需要两个分别表示对头和队尾的指针（分别称为头指针跟尾指针）才能唯一确定。为了操作方便起见，我们也给链队列添加一个头结点，并令头指针指向头结点，由此，判断链队列为空的等价条件便是头指针跟尾指针均指向了头结点。
3、下面是链队列的存储表示以及基本操作的C语言算法描述伪代码：
typedef struct QNode {
QElemType data;
struct QNode *next;
}QNode, *QueuePtr; //队列结点
typedef struct {
QueuePtr front; //对头指针
QueuePtr rear; //队尾指针
}LinkQueue;
Status InitQueue(LinkQueue &CppLive)
{
//构造一个空队列CppLive
CppLive.front = CppLive.rear = (QueuePtr)malloc(sizeof(QNode));
if (!CppLive.front) exit(OVERFLOW);
CppLive.front->next = NULL;
return OK;
}
Status DestoryQueue(LinkQueue &CppLive)
{
//销毁队列CppLive
while (CppLive.front)
{
CppLive.rear = CppLive.front->next;
free(CppLive.front);
CppLive.front = CppLive.rear;
}
return OK;
}
Status EnQueue(LinkQueue &CppLive， QElemType e)
{
//插入元素e为CppLive的新的队尾元素
p = (QueuePtr)malloc(sizeof(QNode));
if (!p) exit(OVERFLOW);
p->data = e;
p->next = NULL;
CppLive.rear ->next = p;
CppLive.rear = p;
return OK;
}
Status DeQueue(LinkQueue &CppLive, QElemType &e)
{
//若队列不空，则删除Q的队列头元素，用e返回其值，并返回OK
//否则返回ERROR
if (CppLive.front == CppLive.rear) return ERROR;
p = CppLive.front->next;
e = p->data;
CppLive.front->next = p->next;
if (CppLive.rear == p) CppLive.rear = CppLive.front;
free(p);
return OK;
}
4、和顺序栈相类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素之外，还需要附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。但是这种顺序表示的队列如果依靠纯粹的累加来实现入队出队，那样很可能出现数组越界的情况，但事实是数组中某些已经出队的区域仍然空闲而没法再利用，于是为了合理利用存储空间来实现顺序存储的队列，我们引入了循环队列这一概念。
5、判断循环队列空间是“空”还是“满”，有两种处理方式：其一是另设一个标志位一区别队列是否已满；其二是少用一个元素空间，约定以“队列头指针在队列尾指针的下一位置（指环状的下一位置）上”作为队列呈“满”状态的标志。
6、若用户无法预估所用队列的最大长度，则不要采用循环队列，而宜采用链队列。
7、下面是循环队列的存储表示以及基本操作的C语言算法描述伪代码：
#define MAXQSIZE 100 //最大队列长度
typedef struct {
QElemType *base; //初始化的动态分配存储空间
int front; //头指针，若队列不空，指向队列头元素
int rear; //尾指针，若队列不空，指向队列尾元素的下一位置
}SqQueue;
Status InitQueue(SqQueue &CppLive)
{
//构造一个空队列
CppLive.base = (QElemType *)malloc(MAXQSIZE * szieof(QElemType));
if (!CppLive.base) exit(OVERFLOW); //存储分配失败
CppLive.front = CppLive.rear = 0;
return OK;
}
int QueueLength(SqQueue CppLive)
{
//返回CppLive的元素个数，即队列的长度
return (CppLive.rear - CppLive.front + MAXQSIZE) % MAXQSIZE;
}
Status EnQueue(SqQueue &CppLive, QElemType e)
{
//插入元素e为CppLive的新的队尾元素
if ((CppLive.rear + 1) % MAXQSIZE == CppLive.front) return ERROR; //队列满
CppLive.base[CppLive.rear] = e;
CppLive.rear = (CppLive.rear + 1) % MAXQSIZE;
return OK;
}
Status DeQueue(SqQueue &CppLive, QElemType &e)
{
//若队列不空，则删除Q的对头元素，用e返回其值，并返回OK
//否则返回ERROR
if (CppLive.front == CppLive.rear) return ERROR;
e = CppLive.base[CppLive.front];
CppLive.front = (CppLive.front + 1) % MAXQSIZE;
return OK;
}
除非注明，文章均为CppLive 编程在线原创，转载请注明出处，谢谢。
