队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

队列的特性：

• 先进先出、后进后出。

• 只允许 从一端 添加元素，从 另一端 删除元素。

• 队头 出元素，队尾 进元素。

队列的顺序存储

顺序队的基本操作

顺序队的结构体定义

#define MAX 1000
typedef struct Queue{

    int data[MAX];            //顺序存储 数组模拟的队列
    int size;                //队列的大小(队列中元素的个数)

}Queue, *SeqQueue;

顺序队-初始化队

数组头做队头，数组尾做队尾。

SeqQueue init(){
    
    //申请队列空间，即数组空间
    SeqQueue p = (Queue *)malloc(sizeof(Queue));
    
    //判断队列空间申请失败
    if(!p){
        return NULL;
    }
    
    //初始化队列大小
    p->size = 0;
    
    //初始化队列值为0
    for(int i=0; i<MAX ;i++){
        p->data[i] = 0;
    }
    
    //返回队列指针
    reutrn p;
    
}

顺序队-入队

void push(SeqQueue p){
    
    //判断队列不存在
    if(!p){
        return;
    }
    
    //判断队列元素是否为满，拿队列当前的长度去跟数组的最大值作比较
    if(p->size == MAX){
        printf("队列元素已满！\n");
        return;
    }

    int value;
    printf("请输入待入队元素值：");
    scanf("%d",&value);
    
    //插入元素(进队)
    p->data[p->size] = value;
    
    //元素入队，队列长度增加
    p->size ++;
    
}

顺序队 - 出队

void push(SeqQueue p){
    
    //判断队列不存在
    if(!p){
        return;
    }
    
    //判断队列元素是否为空，拿队列当前的长度与0比较
    if(p->size == 0){
        printf("队列元素已空！\n");
        return;
    }
    
    //出队 删除数组首元素
    for(int i=0; i< p->size -1 ;i++){
        p->data[i] = p->data[i+1];
    }
    
    //元素出队，队列长度减少
    p->size --;
    
}

---

队列的链式存储

链队的基本操作

链队的结构体定义

//结点结构体
struct Node{

    int data;             //数据域
    struct Node* next;     //指针域

};

//队列的结构体
typedef struct LQueue{

    struct Node header;     //头结点
    int size;               //队列大小
    struct Node* pTail;     //尾结点指针

}LQueue, *LinkQueue;

链队-初始化队

LinkQueue init_LinkQueue(){

    //创建队列结构体
    struct LQueue* myQueue = (struct LQueue*)malloc(sizeof(struct LQueue));
    
    if (!myQueue){
        return NULL;
    }

    //初始化队列长度
    myQueue->size = 0;

    //初始化队列头指针的指针域
    myQueue->header.next = NULL;
    myQueue->pTail = &myQueue->header;

    return myQueue;
}

链队-入队

void push_LinkQueue(LinkQueue queue, int data){

    //本质 尾插
    if (!queue){
        return;
    }

    //创建新结点
    struct Node * newNode = (struct Node *)malloc(sizeof(struct Node));
    if (!newNode){
        return;
    }

    newNode->data = data;

    //更新指针的指向
    queue->pTail->next = newNode;
    newNode->next = NULL;
    queue->pTail = newNode;

    //更新队列大小
    queue->size++;

}

链队-出队

void pop_LinkQueue(LinkQueue queue){

    //本质头删
    if (!queue){
        return;
    }

    if (queue->size == 0){
        printf("空队，无法出队\n");
        return;
    }

    //记录第一个结点
    struct Node* pFirst = queue->header.next;

    //更新指针的指向
    queue->header.next = pFirst->next;

    //判断结点存在并释放结点
    if (pFirst){
        free(pFirst);
    }

    //队列中只有一个结点的时候，再出队会影响尾指针，需要特判
    if (queue->size == 1){
        queue->pTail = &queue->header;
    }

    //队列大小更新
    queue->size--;

}