数据结构（C语言版）---队列
1、队列：在表的一端插入，表的另一端删除，允许插入的一端为队尾，允许删除的一端为队头。先进先出FIFO。
2、队列的基本操作
InitQueue(&Q)：构造空队列
DestroyQueue(&Q)：销毁队列
ClearQueue(&Q)：清空队列
QueueEmpty(Q)：判断队列是否为空
QueueLength(Q)：求队列长度
GetHead(Q,&e)：用e返回队列的队头元素
EnQueue(&Q,e)：插入e作为队列的新队尾
DeQueue(&Q,&e)：删除队头元素，并用e返回
3、队列的顺序存储：连续的存储单元，附设两个指针front指示队头元素，rear指示队尾元素的下一个位置
1）循环队列：将顺序队列变成环状空间。
（1）初始化建空队列时：front=rear=0
（2）每当插入新的队列尾元素时，rear=(rear+1)%maxsize
（3）每当删除队头元素时，front=(front+1)%naxsize
（4）在非空队列中，头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置。
（5）队列长度：(rear+maxsize-front)%maxsize
2）判别队列空间是“空”还是“满”。
（1）设一个标志位tag以区别队列是“空”还是“满”，初始tag=0，入队成功tag=1，出队成功tag=0。
队空：因删除元素导致rear==front&&tag==0；队满：因插入元素导致rear==front&&tag==1
（2）少用一个元素空间，约定以“队列头指针在队列尾指针的下一个位置（指环状的下一个位置）上”作为队列“满”的标志。
队空：rear==front；队满：(rear+1)%maxsize==front；队中元素的个数：(rear+maxsize-front)%maxsize
（3）设置计数器count，初始count=0，入队成功count+1，出队成功count-1。
队空：count==0；队满：count>0&&rear==front
3）队列的顺序存储类型描述
#define Maxsize 50
typedef struct {
int data[Maxsize];
int front, rear;
int tag = 0;//如果不需要设置标志位可以不声明。
}SqQueue;
初始状态（队空条件）：Q.front==Q.rear==0；进队操作：队不满时，插入队尾，队尾指针+1；出队操作：队不空时，取队头元素的值，头指针+1。
4）顺序存储时一些基本操作的实现
（1）初始化
void initqueue(SqQueue &Q)
{
Q.rear = Q.front = 0;
}
（2）判断队列为空
bool queueempty(SqQueue Q)
{
if (Q.rear == Q.front)
{
return true;
}
else
{
return false;
}
}
（3）入队
bool enqueue(SqQueue & Q,int e)
{
if ((Q.rear + 1) % Maxsize == Q.front)
{
return false;
}
Q.data[Q.rear] = e;
Q.rear = (Q.rear + 1) % Maxsize;
return true;
}
（4）设有tag标志的循环队列入队
bool enqueue2(SqQueue & Q, int e)
{
if (Q.front == Q.rear&&Q.tag == 1)
{
return false;
}
Q.data[Q.rear] = e;
Q.rear = (Q.rear + 1) % Maxsize;
Q.tag = 1;
return true;
}
（5）出队
bool dequeue(SqQueue &Q, int &e)
{
if (Q.rear == Q.front)
{
return false;
}
e = Q.data[Q.front];
Q.front = (Q.front + 1) % Maxsize;
return true;
}
（6）设有tag标志的循环队列出队
bool dequeue2(SqQueue &Q, int &e)
{
if (Q.front == Q.rear&&Q.tag == 0)
{
return false;
}
e = Q.data[Q.front];
Q.front = (Q.front + 1) % Maxsize;
Q.tag = 0;
return true;
}
4、双端队列：限定插入和删除操作在表的两端进行的线性表。
1）输出受限的双端队列：一个端点允许插入和删除，另一个端点只允许插入。
2）输入受限的双端队列：一个端点允许插入和删除，另一个端点只允许删除。
5、队列的链式存储
1）链队列：用链表表示的队列，一个含有头指针（指向队头结点）和尾指针（指向队尾结点）的单链表。
2）当链队列有头结点时，当尾指针和头指针均指向头结点，则链队列尾空。
3）队列的链式存储类型描述
typedef struct {
int data;
struct Linkqueuenode *next;
}Linkqueuenode;
typedef struct {
Linkqueuenode *front, *rear;
}Linkqueue;
//Q.front==null&&Q.rear==null，链式队列为空。
4）链式存储时一些基本操作的实现
（1）初始化
void initqueue(Linkqueue &Q)
{
Q.front = Q.rear = (Linkqueuenode *)malloc(sizeof(Linkqueuenode));
Q.front->next = NULL;
}
（2）判断队列是否为空
bool queueempty(Linkqueue Q)
{
if (Q.rear == Q.front)
{
return true;
}
else
{
return false;
}
}
（3）入队
void enqueue(Linkqueue &Q, int e)
{
Linkqueuenode *s = (Linkqueuenode *)malloc(sizeof(Linkqueuenode));
s->data = e;
s->next = NULL;
Q.rear->next = s->next;
Q.rear = s;
}
（4）出队
bool dequeue(Linkqueue &Q, int &e)
{
if (Q.front == Q.rear)
{
return false;
}
Linkqueuenode *p = Q.front;
e = p->data;
Q.front->next = p->next;
if (Q.rear == p)
{
Q.rear = Q.front;
}
free(p);
return true;
}