【数据结构】队列的定义以及C语言代码的实现（仅供学习交流使用）

1、队列的定义

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

2、队列的实现

        用单链表的形式去实现，非常的合适,只要找到一个头结点当队头，一个尾结点当队尾，然后依次实现头删，尾插即可

typedef int QDtatType;
typedef struct QueueNode
{
    struct QuedeNode*next;
    QDtatType data;
}QNode;
typedef struct Queue
{
    QNode*head;
    QNode*tail;
}Queue;

3、队列的接口函数

实现如下的接口函数

void QueueInit(Queue*pq);//初始化队列
void QueueDestory(Queue*pq);//摧毁队列
void QueuePush(Queue*pq, QDtatType x);//队尾入
void QueuePop(Queue*pq);//队头出
//取队头队尾的数据
QDtatType QueueFront(Queue*pq);
QDtatType QueueBack(Queue*pq);
int QueueSize(Queue*pq);//取数据的个数
bool QueueEmpty(Queue*pq);//判断队列是否为空

（1）初始化队列

void QueueInit(Queue*pq)//
{
    assert(pq);
    pq->head = NULL;
    pq->tail = NULL;
}

（2）摧毁队列

void QueueDestory(Queue*pq)
{
    assert(pq);
    QNode*cur = pq->head;
    while (cur != NULL)
    {
        QNode*next = cur->next;//先把下一个保存了
        free(cur);
        cur = next;
    
    }
    pq->head = pq->tail = NULL;
}

（3）队尾入

void QueuePush(Queue*pq, QDtatType x)//队尾入
{
    assert(pq);
    QNode*newnode =  (QNode*)malloc(sizeof(QNode));//先弄一个新的节点出来；
    if (newnode == NULL)
    {
        printf("malloc fail");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    if (pq->tail == NULL)
    {
        pq->head = newnode;
        pq->tail = newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = pq->tail->next;
    }
}

（4）队头出

void QueuePop(Queue*pq)//队头出
{
    assert(pq);
    assert(pq->head);
    if (pq->head->next == NULL)//这里的目的是为了防止队列只有一个节点的时候，出现tail野指针的情况
    {
        free(pq->head);
        pq->head = pq->tail = NULL;
    }
    else//多个节点的情况
    {
        //先保存下一个
            QNode*next = pq->head->next;
            free(pq->head);
            pq->head = next;
    }
    
}

（5）取队头队尾的数据

QDtatType QueueFront(Queue*pq)
{
    assert(pq);
    assert(pq->head);
    return pq->head->data;
}
QDtatType QueueBack(Queue*pq)
{
    assert(pq);
    assert(pq->head);
    return pq->tail->data;
}

（6）队列中数据的个数

int QueueSize(Queue*pq)//取数据的个数
{
    assert(pq);
    int size = 0;
    QNode*cur = pq->head;
    while (cur)
    {
        ++size;
        cur = cur->next;
    }
    return size;
}

（7）判断队列是否为空

bool QueueEmpty(Queue*pq)//判断队列是否为空
{
    assert(pq);
    return pq->head == NULL;//等于空则真，不等于空则假
}