对头出，队尾入。
基本操作

InitQueue(*Q)
QueueEmpty(Q)
EnQueue(*Q,x)
DeQueue(*Q,*x)
GetHead(Q, *x)

---

顺序实现

#define MaxSize 50
typedef struct
{
    ElemType data[MaxSize];
    int front, rear;
}* SqQueue;

初始时Q->front=Q->rear=0
空队时Q->front==Q->rear
其余时候front指向队头，rear指向队尾的后一个位置
但会出现，数组前面由于出队空了很多位置，但rear==MaxSize无法继续入队的假溢出现象。
循环队列
初始时：Q->front=Q->rear=0
队首出队时加一：Q->front=(Q->front+1)%MaxSize
队尾入队时加一：Q->rear=(Q->rear+1)%MaxSize
队列长度：(Q->rear+MaxSize-Q->front)%MaxSize
由于队空和队满时都有Q->front==Q->rear无法判断
解决办法
1.入队时少用一个队列单元
队满：(Q->rear+1)%MaxSize==Q->front
队空：Q->front==Q->rear
2.增设表示元素个数的数据成员
3.增设tag，代表上次操作，若tag为0，由于出队导致front==rear则队空，为1，则是由入队导致的，则队满

队列.PNG
初始化

void InitQueue(SqQueue Q)
{
    Q->rear=Q->front=0;
}

判空

bool isEmpty(SqQueue Q)
{
    if(Q->rear==Q->front)    return true;
    else    return false;
}

入队

bool EnQueue(SqQueue Q, ElemType x)
{
    if((Q->rear+1)%MaxSize==Q->front) return false;
    Q->data[Q->rear]=x;
    Q->rear=(Q->rear+1)%MaxSize;
    return true;
}

出队
bool DeQueue(SqQueue Q, ElemType* x)
{
if(Q->rear==Q->front) return false;
*x=Q->data[Q->front];
Q->front=(Q->front+1)%MaxSize;
return true;
}

---

链式存储结构

同时带有队头指针和队尾指针的单链表

typedef struct
{
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct
{
    LinkNode *front, *rear;
}LinkQueue;

为使其空队时插入删除操作统一，一般将其设计成带头节点的单链表

带头节点单链表实现的队列.PNG

初始化

void InitQueue(LinkQueue* Q)
{
    Q->front=Q->rear=（LinkNode*)malloc(size of(LinkNode));
    Q->front->next=NULL；
}

判空

bool IsEmpty(LinkQueue* Q)
{
    if(Q->front==Q->rear)    return true;
    return false;
}

入队

void EnQueue(LinkQueue* Q, ElemType x)
{
    LinkNode* s=(LinkNode*)malloc(size of(LinkNode));
    s->data=x;
    s->next=NULL;
    Q->rear->next=s;
    Q->rear=s;
}

出队

bool DeQueue(LinkQueue* Q, ElemType* x)
{
    if(Q->front==Q->rear)    return false;
    LinkNode* first=Q->front->next;
    *x=first->data;
    Q->front=first->next;
    if(Q->rear==first)            //原队列只有一个节点，删除后变空
        Q->rear=Q->next;
    free(first);
    return true;
}

---

双端队列

两端都可以进行入队和出队操作
输出受限的双端队列：出队在某一段进行
输入受限的双端队列

---

队列应用

二叉树层次遍历
使用队列来保存下一步的处理顺序
1.根节点入队
2.若队列为空则遍历完毕，否则重复3
3.队首出队，并访问之，将其左孩子和右孩子依次入队，返回2
计算机系统中的应用
1.解决主机与外部设备之间速度不匹配的问题（打印数据缓冲区）
2.解决由多用户引起的资源竞争问题（CPU的分配）

---

特殊矩阵的压缩存储

将矩阵更有效地存储在内存中，并能方便地提取矩阵中的元素
压缩矩阵：为多个值相同的元素只分配一个存储空间，对零元素不分配存储空间。
特殊矩阵：具有许多相同矩阵元素或零元素，且分布有一定规律性。（对称矩阵，上下三角矩阵，对角矩阵）
找出特殊矩阵中值相同的矩阵元素的分布规律，把那些呈现规律性分布的，值相同的多个矩阵元素压缩存储到一个存储空间中。
关键在于找A和B的下标转换
1.对称矩阵
A[1...n][1...n]->B[n(n+1)/2]
2.三角矩阵
A[1...n][1...n]->B[n(n+1)/2+1]
那个1是用来存三角区域的常数的
3.对角矩阵
4.稀疏矩阵
将非零元素及其相应的行和列构成一个三元组（行标，列标，值），失去了随机存取特性。