数据结构（队列）

什么是队列？

• 队列和栈类似，也是一类特殊的线性表。特殊之处也是在于操作上。
• 队列：只允许在一端进行插入数据操作（入队），在另一端进行删除数据操作（出队）的特殊的线性表。
• 具有先进先出，后进后出的特点。
• 进行插入操作（入队）的一端称为队尾。进行删除操作（出队）的一端称为队头。

队列的意义（作用）

队列的实现

• 和栈类似，也有两种实现方式。一种是数组，也就是顺序表，一种是链表。

• 两种方式都是可以的，不过相比之下，链表更优一些。

• 因为队列是在队头出数据，也就是头部删除数据，那么顺序表要删除头部数据需要一个个的移动数据进行覆盖。所以我们优先选择链表实现。

• 链表类型的选择

• 

实现代码

• 头文件.h

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

typedef int QDateType;
typedef struct QueueNode
{
    struct QueueNode* next;
    QDateType date;
}QNode;

typedef struct Queue
{
    QNode * head;
    QNode * tail;
    int size;
}Que;

//队列初始化
void QueueInit(Que* pq);
//队列销毁
void QueueDestroy(Que* pq);

//入队（尾部插入数据）
void QueuePush(Que* pq,QDateType x);
//出队（头部删除数据）
void QueuePop(Que* pq);

//获得队头节点的值
QDateType QueueFront(Que* pq);
//获得队尾节点的值
QDateType QueueBack(Que* pq);

//判断队列是否为空
bool QueueEmpty(Que* pq);
//获得队列的长度（有效元素个数）
int QueueSize(Que* pq);

• 函数实现文件.c

#include "Queue.h"

//队列初始化
void QueueInit(Que* pq)
{
    assert(pq);

    pq->head=pq->tail=NULL;
    pq->size=0;
}
//队列销毁
void QueueDestroy(Que* pq)
{
    assert(pq);
    QNode* cur=pq->head;
    while(cur)
    {
        QNode *next=cur->next;
        free(cur);
        cur=next;
    }

    pq->head=pq->tail=NULL;
    pq->size=0;
}

//入队（尾部插入数据）
void QueuePush(Que* pq,QDateType x)
{
    assert(pq);

    QNode *newnode=(QNode*) malloc(sizeof (QNode));
    if(newnode==NULL)
    {
        perror("malloc failed");
        exit(-1);
    }

    newnode->next=NULL;
    newnode->date=x;

    if(pq->tail==NULL)
    {
        pq->head=pq->tail=newnode;
    }
    else
    {
        pq->tail->next=newnode;
        pq->tail=newnode;
    }

    pq->size++;
}
//出队（头部删除数据）
void QueuePop(Que* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));

    if(pq->head->next==NULL)
    {
        free(pq->head);
        pq->head=pq->tail=NULL;
    }
    else
    {
        QNode *next=pq->head->next;
        free(pq->head);
        pq->head=next;
    }

    pq->size--;

}

//获得队头节点的值
QDateType QueueFront(Que* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));

    return pq->head->date;
}
//获得队尾节点的值
QDateType QueueBack(Que* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));

    return pq->tail->date;
}

//判断队列是否为空
bool QueueEmpty(Que* pq)
{
    assert(pq);

    return pq->head==NULL;
}
//获得队列的长度（有效元素个数）
int QueueSize(Que* pq)
{
    assert(pq);

    return pq->size;
}

函数解析

• 队列结构

typedef int QDateType;
typedef struct QueueNode
{
    struct QueueNode* next;
    QDateType date;
}QNode;

typedef struct Queue
{
    QNode * head;
    QNode * tail;
    int size;
}Que;

• 队列初始化

//队列初始化
void QueueInit(Que* pq)
{
    assert(pq);

    pq->head=pq->tail=NULL;
    pq->size=0;
}

• 队列销毁

//队列销毁
void QueueDestroy(Que* pq)
{
    assert(pq);
    QNode* cur=pq->head;
    while(cur)
    {
        QNode *next=cur->next;
        free(cur);
        cur=next;
    }

    pq->head=pq->tail=NULL;
    pq->size=0;
}

• 入队（尾部插入数据）

//入队（尾部插入数据）
void QueuePush(Que* pq,QDateType x)
{
    assert(pq);

    QNode *newnode=(QNode*) malloc(sizeof (QNode));
    if(newnode==NULL)
    {
        perror("malloc failed");
        exit(-1);
    }

    newnode->next=NULL;
    newnode->date=x;

    if(pq->tail==NULL)
    {
        pq->head=pq->tail=newnode;
    }
    else
    {
        pq->tail->next=newnode;
        pq->tail=newnode;
    }

    pq->size++;
}

• 出队（头部删除数据）

//出队（头部删除数据）
void QueuePop(Que* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));

    if(pq->head->next==NULL)
    {
        free(pq->head);
        pq->head=pq->tail=NULL;
    }
    else
    {
        QNode *next=pq->head->next;
        free(pq->head);
        pq->head=next;
    }

    pq->size--;

}

• 获得队头节点的值

//获得队头节点的值
QDateType QueueFront(Que* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));

    return pq->head->date;
}

• 这个不多说。

• 获得队尾节点的值

//获得队尾节点的值
QDateType QueueBack(Que* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));

    return pq->tail->date;
}

• 不多说了。

• 判断队列是否为空

//判断队列是否为空
bool QueueEmpty(Que* pq)
{
    assert(pq);

    return pq->head==NULL;
}

• 连头都没有，那是不是空的？或者pq->tail==NULL。也可以判空。

• 获得队列的长度（有效元素的个数）

//获得队列的长度（有效元素个数）
int QueueSize(Que* pq)
{
    assert(pq);

    return pq->size;
}

• 不多说，每次插入删除数据，都会带上它变化的。它就是用来记录元素个数的。

• 那么队列的基本知识就基本完成了。