1.队列的定义

队列（Queue）：是只允许在一端进行插入，在另一端删除的线性表；

• 入队就是插入操作
• 出队就是删除操作

特点： 先进先出（FIFO）

重要术语：队头、队尾、空队列

• 队头：允许删除的一端
• 队尾：允许插入的一端
• 空队列：没有任何数据元素

2.队列的基本操作

• InitQueue(&Q)：初始化队列，构造一个空队列Q
• DestoryQueue(&Q)：销毁队列，销毁并释放队列Q所占用的内存空间
• EnQueue(&Q,x)：入队，若队列Q未满，将x加入，使之成为新的队尾
• DeQueue(&Q,&x)：出队，若队列Q非空，删除队头元素，并用x返回
• GetHead(Q,&x)：读对头元素，若队列Q非空，则将队头元素赋值给x

3.队列的顺序实现

用静态数组存放队列元素，在定义一个队头指针，一个队尾指针

#define Maxsize 10
typedef struct{
    ElemType data[MaxSize];
    int front;
    int rear;
}SqQueue;

3.1初始化操作

初始化队列：

void InitQueue(SqQueue &Q){
    Q.rear=Q.front=0;    //初始队头、队尾指针指向0
}

判断队列是否为空：

bool QueueEmpty(SqQueue Q){
    Q.rear==Q.front
        return true
    return false;
}

3.2入队操作

入队操作只能从队尾入队；实现分析：需要先判断队列是否为满，然后将新元素插入队尾，然后修改队尾的指针后移。

bool EnQueue(SqQueue &Q,ElemType x){
    if(队列已经满)
        return false;
    Q.dara[Q.rear]=x;
    Q.rear=Q.rear+1;   
        return true;
}

3.2.1方案一（判空）

如果直接给队尾指针直接后移是会出问题的，当整个静态数组被存满的时候，rear指针就会指向MaxSize，如果依次让对头出队的时候，rear依然是指向MaxSize,所以rear==MaxSize的条件不能判断队列已经满了。所以需要修改为：让队尾指针+1后取模

Q.rear=(Q.rear+1)%MaxSize;

用模运算将储存空间在逻辑上变成了“环状”

3.2.2方案二（判空）

用size记录队列的当前长度，初始化size为0。

int size=0;  //初始化时候
size++;   //插入成功
size--;   //删除成功
队列空：size=0；
队列为满：size==MaxSize

3.2.3方案三（判空）

标记位，删除成功的时候tag=0,插入成功的时候tag=1；

• 队列满：front==rear && tag==1
• 队列空：front==rear && tag==0

3.3出队操作

删除一个队列头元素，并且用x返回

bool DeQueue(SqQueue &Q,ElemType &X){
    if(Q.rear==Q.front)   //判断队列是否为空
        return false;
    x=Q.data[Q.front];
    Q.front=(Q.front+!)%MaxSize;  //队列头指针后移
}

3.4 查队头元素

获得队列头元素值并用x返回

bool GetQueue(SqQueue Q,ElemType &X){
    if(Q.rear==Q.front)   //判断队列是否为空
        return false;
    x=Q.data[Q.front];
    return true;
}