手撕数据结构—队列

队列

1. 队列的话只允许在一端插入，在另外一端删除。插入数据的那一段叫做队尾，出数据的那一段叫做队头（从尾巴插入）。

2. 因此的话队列是先进先出的。入的顺序与出的顺序的话是一样的。这个与栈是不一样的，因为栈的话就是说如果你入的过程当中边入边出的话，这个出的序列是不一样的。而对于队列来说没有这个影响。

3. 如果要去模拟队列的话，用链式结构相对来说更加方便。我们就用单链表来模拟队列。因为我们到时候必须要进行尾插，因此我们也由此可以得知，到时候必须要得有一个尾指针。

---

对各种结构的简单比对与回顾总结

对于链表而言，不管是带不带哨兵位头结点，它的话仅仅只需要一个指针就够了。链表的话基本上几乎都只需要一个指针，单与双都一样，无非就是要么指向第一个节点（存有效数据），要么就是指向哨兵位头结点。

栈&顺序表

1. 原始状态：这两个的话都形式十分的相近，首先他们两个都必须得有一个类似于中枢控制系统的一个结构体，我们都知道这个结构体里面的话，他有三个成员：size,capacity,堆区指针。在一开始最开始，让我们创建完这个结构体类型之后，就会紧接着去创建这么一个结构体。（创建结构体类型+结构体变量）

2. 初始化：由于创建结构体的时候，是不能够对这个结构体进行初始化的，因此我们就有了初始化这个函数，把size与capacity的数据进行修改之后，我们还需要额外的去向内存的堆去申请一块空间，然后让堆区指针这个成员去指向这块从堆区申请过来的内存空间。 （初始化结构体变量的成员）

3. 传参说明：由于我这个结构体是在函数外面就已经创建好了。因此我传参的时候只需要穿结构体的地址（一级指针）。 （一级指针）

单链表

1. 原始状态：对于链表而言的话，仅仅只需要一个指针就已经可以了。一开始最开始就先创建一个结构体类型（是用来描述每一个节点的），然后再去创建一个该结构体指针phead，然后置空，防止成为野指针。 （创建结构体类型+链表头指针）

2. 初始化：如果是不带哨兵位头结点的，那么就根本没有必要去初始化，当有新的节点要插入进来的时候，别人自然自己会BuySLTNode （没有必要，节点push进来自己会BuySLTNode）

3. 参数说明：由于接下来各种各样的操作会改变这个phead所指向的位置，因此这个时候在函数内部传一级指针的话是没有任何意义的，因为形参的改变并不会影响实参，为了要真正能够改变phead的值/指向的位置，这个时候就需要传phead的地址，因此这边传参是二级指针。 (二级指针)

双向循环带头链表

1. 原始状态：因为不管怎么说，这还是一个链表嘛，当然首先还是得创建一个结构体，用来描述一下节点。然后再创建一个结构体指针phead并置空。 （创建结构体类型+链表头指针）

2. 初始化：由于这个链表是带哨兵位头结点的，因此有必要进行初始化这一步操作。初始化的内容也十分的简单，就去malloc一个哨兵位头结点，然后prev与next都指向自己就完事了。（BuyLTNode哨兵位头节点）

3. 参数说明：当我去进行初始化malloc一个哨兵位头结点的时候，虽然我也要去改动phead的指向位置（因为现在要指向这个哨兵位头结点了嘛），但是我可以让他返回malloc出来的哨兵位头结点地址，然后在函数外头把这个函数的返回结果赋给phead就OK，然后对于其他的函数各种操作，由于都是改变结构体的成员，因此只需要传入结构体的指针就可以，所以说这种情况的参数设置的话是一级指针。（一级指针）

队列

1. 原始状态：（创建两个结构体类型+结构体变量）

2. 初始化：（对结构体变量三个成员初始化）

3. 参数说明：（结构体指针，即一级指针）

---

用单链表来模拟实现队列

---

队列的节点(结构体)创建与队列指针集合(结构体)创建

1. 首先我们是用单链表去模拟队列。因此首先我们得创建一个结构体，用来描述一个节点。

2. 但值得一提的是，由于是队列，尾部只能插入，头部只能弹出，因此我创建一个头指针置空后，我还是可以创建一个尾指针并置空，这个主要是为了方便之后我去进行尾插。然后多组数据的话最好放进一个结构里面。于是乎我们就再创建一个结构体，用来存头指针，尾指针，顺便维护一下队列中元素的个数。

3. 那为什么之前在单链表的时候不怎么干呢？主要原因在于意义不大，比如说我要进行尾删，你这样子有用吗？还是需要找前一个，反正都这么矬了，索性直接给一个头指针就完事了，但是在队列这边，该数据结构已经保证在队尾的话，数据只能进行插入，所以尾指针是有必要的。

typedef int QueueDataType;
typedef struct QueueNode
{QueueDataType data;struct QueueNode* next;
}QueueNode;
typedef struct Quene
{QueueNode* head;QueueNode* tail;int size;
}Queue;

队列的初始化

1. 队列的初始化主要就是把指针集合的头指针与尾指针都变成空指针，然后此时此刻，由于队列当中没有元素，所以说size为0

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

队列的销毁

1. 并不说是任何东西都是在内存栈区上面，但比如说局部变量，函数栈帧这些东西确实是在内存的栈区上面，内存栈区里面的东西如果它一旦出了作用域，就会自动销毁，它所占的这个茅坑就会还给操作系统。

2. 但是像链表当中的每一个节点都是在内存的堆区上面，内存堆积上面的东西是不会自动释放的，需要程序员去手动释放，如果不去释放的话，就永远占据在那，就会造成内存泄露。

3. 显而易见，空队列也支持销毁。

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

队列的队尾插入（入队）

1. 在队列的队尾插入这一个操作当中，我们知道队列的话，它是用单链表来模拟，插入操作势必会涉及到节点的增加，对于单链表新增一个节点，这边的话并不重新分装成一个函数，而是直接在push函数里面malloc一下。

2. 在这边的话还要尤其注意当队列中为空的这种特殊情况（也就是head与tail都为NULL）

void QueuePush(Queue* pq, QueueDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));if (newnode == NULL){perror("QueuePush::Malloc");return;}newnode->data = x;newnode->next = NULL;if (pq->head != NULL){pq->tail->next = newnode;pq->tail = newnode;}else{pq->head = newnode;pq->tail = newnode;}pq->size++;
}

队列的队头弹出（出队）

1. 如果说一个队列想要在队头弹出一个元素的话，首先必须得保证这个队列不是空的，如果说这个队列是空的话，那弹个毛线啊。

2. 然后接下来还有一个特殊情况，当一个队列只有一个元素的时候，此时head与tail都是指向头结点，然后队头弹出把这个头结点给free了，此时此刻还需要额外处理一下tail，把它也变为NULL

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

队列的求元素个数

int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

队列的判断是否为空

bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}

队列的返回队头元素

QueueDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->size > 0);return pq->head->data;
}

队列的返回队尾元素

QueueDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->size > 0);return pq->tail->data;
}