队列？是你了解的这样吗？

，我们今天来学习队列

说起队列大家能想起什么咧？

食堂打饭时排的长长的队，还是银行办理业务时的排号……

它们都有共同的一个特征：就是先到先得嘛！

学完今天的内容，你会发现数据结构中的队列也是如此

让我们卷起了吧！！！

学习目录：

1.队列的概念及结构

2.队列的实现

1.队列的概念及结构

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

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

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

注意：队列和栈的不同点

栈：只能从栈顶插入和删除，满足先进后出的原则

队列：是从队尾插入，对头删除，满足先进先出的原则

2.队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构， 出队列在数组头上出数据，效率会比较低。

数组存储：

总结：利用数组的结构去存储队列，插入时只需要尾插时间复杂度为O(1)，删除时需要把对头后面的元素依次往前移这样时间复杂度就为O(n).

**链表存储： **

总结：利用单链表的结构进行队的存储，插入只需要尾插时间复杂度为O(1)，删除只需要头删时间复杂度为O(n)。可以从上图中看出队列完美避开了单链表需要找前一个结点的问题。

下面我们就来利用单链表实现队列吧！！！

①首先我们先定义两个结构体类型

typedef int QDataType;

typedef struct QueueNode
{
    struct QueueNode* next;
    QDataType data;
}QNode;

typedef struct Queue
{
    QNode* head;
    QNode* tail;
}Queue;

第一个结构体类型QueueNode是结点，第二个Queue是队头和队尾

② 初始化

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

初始化的时候，我们把队头和队尾分别指向NULL

③插入

//队尾入
void QueuePush(Queue* pq, QDataType x)
{
    assert(pq);
    QNode* newnode = (QNode*)malloc(sizeof(QNode));
    if (newnode == NULL)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    newnode->data = x;
    newnode->next = NULL;
    if (pq->tail == NULL)
    {
        pq->head = pq->tail = newnode;
    }
    else
    {
        pq->tail->next = newnode;
        pq->tail = newnode;
    }
}

④删除

//队头出
void QueuePop(Queue* pq)
{
    assert(pq);
    assert(pq->head);

    //一个   多个
    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;
    }

}

⑤取队头

//取队头
QDataType QueueFront(Queue* pq)
{
    assert(pq);
    assert(pq->head);
    return pq->head->data;
}

我们首先得断言一下队列里面是否有数据，如果没有就不能返回，如果有才能返回

⑥取队尾

//取队尾
QDataType QueueBact(Queue* pq)
{
    assert(pq);
    assert(pq->tail);
    return pq->tail->data;
}

⑦队中有多少个结点

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

⑧判空

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

利用bool型进行判空，bool型就是真和假嘛

⑨销毁

//销毁
void QueueDestory(Queue* pq)
{
    assert(pq);
    QNode* cur = pq->head;
    while (cur)
    {
        QNode* next = cur;
        free(cur);
        cur = next;
    }
    pq->head = pq->tail = NULL;
}

销毁的好处是：防止内存泄漏的问题.

本期的内容就到这了

 欢迎下方评论哦！！！

QQ：2186529582

有不懂的问题欢迎加我QQ向我提问哦！！！