@TOC
上次实现队列，是在三个月之前，拖到现在才写文章非常惭愧，但细节忘得差不多了反倒利于我思考嘞，写的过程也犯了几个傻错误，它们都变成小注意写在文章中了。

正文开始

1. 队列的概念和结构

1.1 队列的概念

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

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

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

" title="">

1.2 队列结构

队列也可以数组和链表的结构实现。但数组结构明显不适合，出队列，即头删要挪动数据，效率会低。

//队列
typedef struct QueueNode
{
    QDataType data;
    struct QueueNode* next;
}QueueNode;

为了避免每次找尾的麻烦，我们定义一个尾指针，一头一尾构成队列的结构体。

//多个变量，那就用结构体封起来
typedef struct Queue
{
    QueueNode* head;
    QueueNode* tail;
}Queue;

2. 队列的实现

头文件附在后面大家自己写嗷，单链表增删查改都会了，这个就是一样的，除了尾指针的加入带来了一点小变动，也没关系，小注意都写好嘞~

2.1 初始化和销毁

2.1.1 初始化

" title="">
开始时，队列为空，因此我们这样初始化这个结构体 ——
" title="">

我要的改变head，tail是结构体中的内容，不需要传二级指针，要改变结构体，就传结构体指针就行。

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

2.1.2 销毁

遍历销毁即可。

void QueueDestroy(Queue* pq)
{
    assert(pq);
    QueueNode* cur = pq->head;
    while (cur)
    {
        QueueNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->head = pq->tail = NULL;
}

2.2 求队列中有效元素个数、队列是否为空

2.2.1 求队列中有效元素个数

int QueueSize(Queue* pq)
{
    assert(pq);
    int size = 0;
    QueueNode* cur = pq->head;
    while (cur)
    {
        cur = cur->next;
        size++;
    }
    return size;
}

2.2.2 队列是否为空

bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->head == NULL;
}

2.3 入队和出队

要考虑的和单链表的尾插和头删基本一致。

2.3.1 入队

尾插考虑空链表时的插入。

void QueuePush(Queue* pq, QDataType x)
{
    assert(pq);
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    newnode->data = x;
    newnode->next = NULL;
    if (pq->head == NULL)
    {
        pq->head = pq->tail = newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;//迭代
    }
}

2.3.2 出队

注意！删完了，此时head为空，tail要更改，否则是野指针。

如果不过更改看似好像没什么问题，毕竟正常人谁会销毁了队列还去访问它呢，但我就是抽风我去取队尾元素，原本被销毁后空间归还系统应该拿不到，可tail未被更改，就还是能拿得到。

void QueuePop(Queue* pq)
{
    assert(pq);
     assert(!QueueEmpty(pq)); 
    QueueNode* newhead = pq->head->next;
    free(pq->head);
    pq->head = newhead;
    if (pq->head == NULL)
    {
        pq->tail = NULL;
    }
}

2.4 取队头队尾元素

注意断言空链表。

2.4.1 取队头数据

QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->head->data;
}

2.4.2 取队尾数据

QDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->tail->data;
}

附

Queue.h

#pragma once

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

typedef int QDataType;

//队列
typedef struct QueueNode
{
    QDataType data;
    struct QueueNode* next;
}QueueNode;

//多个变量，那就用结构体封起来
typedef struct Queue
{
    QueueNode* head;
    QueueNode* tail;
}Queue;

//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);

//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//求队列中有效元素个数
int QueueSize(Queue* pq);
//判断队列是否为空？
bool QueueEmpty(Queue* pq);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1

#include"Queue.h"

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

void QueueDestroy(Queue* pq)
{
    assert(pq);
    QueueNode* cur = pq->head;
    while (cur)
    {
        QueueNode* next = cur->next;
        free(cur);
        cur = next;
    }
    pq->head = pq->tail = NULL;
}

void QueuePush(Queue* pq, QDataType x)
{
    assert(pq);
    QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
    newnode->data = x;
    newnode->next = NULL;
    if (pq->head == NULL)
    {
        pq->head = pq->tail = newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;//迭代
    }
}

void QueuePop(Queue* pq)
{
    assert(pq);
     assert(!QueueEmpty(pq));
    QueueNode* newhead = pq->head->next;
    free(pq->head);
    pq->head = newhead;
    if (pq->head == NULL)
    {
        pq->tail = NULL;
    }
}

QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
    assert(pq);
    assert(!QueueEmpty(pq));
    return pq->tail->data;
}

int QueueSize(Queue* pq)
{
    assert(pq);
    int size = 0;
    QueueNode* cur = pq->head;
    while (cur)
    {
        cur = cur->next;
        size++;
    }
    return size;
}

bool QueueEmpty(Queue* pq)
{
    assert(pq);
    return pq->head == NULL;
}

test.c

• [ ] 遍历队列要保证队列的性质，先进先出。
• [ ] 想取下一个，那就pop掉这个再取下一个，别忘记pop。

#define _CRT_SECURE_NO_WARNINGS 1

#include"Queue.h"

void testQueue1()
{
    Queue q;
    QueueInit(&q);
    QueuePush(&q, 1);
    QueuePush(&q, 2);
    QueuePush(&q, 3);
    QueuePush(&q, 4);
    QueuePop(&q);
    QueuePop(&q);
    /*QueuePop(&q);
    QueuePop(&q);*/

    printf("front:%d\n", QueueFront(&q));
    printf("rear:%d\n", QueueBack(&q));
    printf("size:%d\n", QueueSize(&q));

    QueueDestroy(&q);
}

void testQueue2()
{
    Queue q;
    QueueInit(&q);
    QueuePush(&q, 1);
    QueuePush(&q, 2);
    QueuePush(&q, 3);
    QueuePush(&q, 4);

    // 遍历栈，要保证先进先出的性质
    while (!QueueEmpty(&q))
    {
        printf("%d ", QueueFront(&q));
        QueuePop(&q);//想取下一个，那就pop掉这个再取下一个
    }
    QueueDestroy(&q);
}

int main()
{
    //testQueue1();
    testQueue2();
    return 0;
}