队列的顺序储存结构概念

队列的顺序存储结构通常是由一个静态数组和一个记录队列头元素位置的变量front以及一个记录队列尾元素的下一个位置的变量rear组成，因为数组的空间大小在创建时就已经确立了，所以顺序存储结构还存储了队列的最大容量maxsize

假设一开始我们将front和rear两个变量置为0，每次将元素入队后rear都会加一，那么当rear=maxsize时就可以判断队列为满吗？显然我们忽略了一个重要的东西：front一定为0吗？，如果我们一开始将几个元素入队(入队在队尾入)，然后再出队(出队是在队头出)那么front就会++，不会再指向0，然后再往队列里面插入元素，当rear=maxsize时如果还有元素要插入的话就会造成数组越界(从下标为0开始，最大下标为maxsize-1)，但是front(front不为0)之前还有位置是空的还可以再插入数据，此时怎么将数据插入到下标为0的位置呢？

我们可以用pq->rear = (pq->rear + 1) % pq->maxsize这个式子，当rear==maxsize-1时执行这条语句后rear就会变成0，也就是说将数组最大下标为maxsize-1的位置插入数据后，下一个要插入数据的位置就变成了0，这样就完美解决了数组越界问题，队列也变成了循环队列。同理，每次出队时front都会加一，当从数组最大下标位置(maxsize-1)出队后front就会回到0这个位置，可以推出式子为：pq->front = (pq->front + 1) % pq->maxsize

如上图，那么又来了一个问题：当rear=front时(初始化都为0)可以判断队列为空，但是当队列为满时rear也刚好等于front，那该怎么解决这个问题呢？以下给出三种解决方案：

第一种：人为浪费一个空间，在申请数组空间大小时再多申请一个空间，然后当(pq->rear + 1)%(pq->maxsize + 1)等于pq->front时队列为满

第二种：在队列结构体里再存储一个记录队列有效数据个数的变量size，当size=maxsize时说明队列为满

第三种：在对列结构体里再存储一个变量msg，初始化为0，每次出队都将msg设置为0，每次入队都将msg设置为1。因为只有出队才能让队列为空，只有入队才能让队列为满。当pq->rear等于pq->front同时msg等于1时队列为满，当pq->rear等于pq->front同时msg等于0时队列为空

 接下来介绍第一种方法，第一种方法示意图如下：

头函数： 

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>

typedef int QDataType;
typedef struct Queue {
	QDataType* data;//存储有效数据的数组
	int front;//队列头指针
	int rear;//队列尾指针(指向尾元素的下一个位置)
	int maxsize;//队列最大容量
}Queue;

各函数实现：

#include "wknb.h"
// 初始化队列
Queue* init_queue(int sum) {
    Queue* Q = (Queue*)malloc(sizeof(Queue));
    QDataType* tmp = (QDataType*)malloc((sum + 1) * sizeof(Queue));
    if (tmp == NULL) {
        printf("error");
        exit(1);
    }
    Q->data = tmp;
    Q->front = Q->rear = 0;
    Q->maxsize = sum;
    return Q;
}

// 判空
bool empty_queue(Queue* Q) {
    assert(Q);
    return Q->front == Q->rear;
}

// 判满
bool full_queue(Queue* Q) {
    assert(Q);
    return (Q->rear + 1) % (Q->maxsize + 1) == Q->front;
}

// 入队
void push_queue(Queue* Q, QDataType num) {
    assert(Q);
    assert(!full_queue(Q));
    Q->data[Q->rear] = num;
    Q->rear = (Q->rear + 1) % (Q->maxsize + 1);
}

// 出队列，队头
void pop_queue(Queue* Q) {
    assert(Q); // pq != NULL
    assert(!empty_queue(Q)); // 队列不为空
    Q->front = (Q->front + 1) % (Q->maxsize + 1);
}

// 取队头数据
QDataType front_queue(Queue* Q) {
    assert(Q);
    assert(!empty_queue(Q)); // 队列不为空
    return Q->data[Q->front];
}

// 取队尾数据
QDataType rear_queue(Queue* Q) {
    assert(Q);
    assert(!empty_queue(Q)); // 队列不为空
    int temp = Q->rear - 1;
    if (temp < 0) { // 如果 rear 指向位置是 0，应该回绕
        temp = Q->maxsize;
    }
    return Q->data[temp];
}

// 有效长度
int size_queue(Queue* Q) {
    assert(Q);
    return ((Q->rear - Q->front + (Q->maxsize + 1)) % (Q->maxsize + 1));
}

// 打印队列数据
void print_queue(Queue* Q) {
    assert(Q); // pq != NULL
    while (!empty_queue(Q)) {
        printf("%d ", front_queue(Q));
        pop_queue(Q); 
    }
    printf("\n");
}

// 销毁队列
void QueueDestory(Queue* Q) {
    assert(Q); // pq != NULL
    if (Q->data) {
        free(Q->data); // 销毁数据空间
    }
    free(Q); // 销毁队列结构体
}

测试案例：

int main() {
    Queue* Q = init_queue(5); // 使用 init_queue 来初始化队列
    push_queue(Q, 1);
    push_queue(Q, 2);
    pop_queue(Q);
    push_queue(Q, 6);
    print_queue(Q);
    QueueDestory(Q); // 销毁队列
    return 0;
}

 结果：

优点：

空间利用率高：在静态分配的内存空间中，顺序存储队列的存储密度大，空间利用率高。
访问效率高：由于数据是连续存储的，队列的访问（如查看队首或队尾元素）操作效率高，时间复杂度为O(1)。

缺点：

假溢出问题：在顺序存储队列中，如果队列满了（即队尾指针达到了数组的上界），但实际可能队首还有空间未被利用，这会导致队列出现“假溢出”现象。解决假溢出的方法之一是采用循环队列，但这会增加实现的复杂度。
动态扩容成本高：如果采用动态数组实现顺序队列，当队列容量不足时，需要进行扩容操作，这通常涉及到大量数据的移动，成本较高。
空间限制：顺序存储队列的大小受限于静态分配的内存大小，或者动态扩容的阈值。