队列
队列是一种先进先出 ( F I F O ) (FIFO)(FIFO) 的线性表. 在表一端插入,在另一端删除。
0.队列的基本概念
定义
只能在表的一端（队尾）进行插入，在另一端（队头）进行删除运算的线性表
逻辑结构
与线性表相同，仍为一对一关系
存储结构
用顺序队列或链队存储均可
运算规则
先进先出（FIFO）
实现方式
关键是编写入队和出队函数，具体实现依顺序队或链队的不同而不同
1.队列的实现
可用一个数组和两个变量优化为循环队列或者STL实现。比如循环队列queue，双端队列deque
2.1循环队列的相关条件和公式：
队空条件：rear==front
队满条件：(rear+1) %QueueSIze==front，其中QueueSize为循环队列的最大长度
计算队列长度：（rear-front+QueueSize）%QueueSize
入队：（rear+1）%QueueSize
出队：（front+1）%QueueSize
3.链队列
typedef struct QNode{
QElemType data;
struct Qnode *next;
}Qnode, *QueuePtr;
typedef struct {
QueuePtr front; //队头指针
QueuePtr rear; //队尾指针
}LinkQueue;
链队列初始化
Status InitQueue (LinkQueue &Q){
Q.front=Q.rear=(QueuePtr) malloc(sizeof(QNode));
if(!Q.front) exit(OVERFLOW);
Q.front->next=NULL;
return OK;
}
销毁链队列
Status DestroyQueue (LinkQueue &Q){
while(Q.front){
Q.rear=Q.front->next;
free(Q.front);
Q.front=Q.rear; }
return OK;
}
判断链队列是否为空
Status QueueEmpty (LinkQueue Q)
{
return (Q.front==Q.rear);
}
求链队列的队头元素
Status GetHead (LinkQueue Q, QElemType &e){
if(Q.front==Q.rear) return ERROR;
e=Q.front->next->data;//有头结点
return OK;
}