数据结构 --- 队列

队列概念

队列同���一样，是一种特殊的数据结构，只允许在一端进行插入操作，在另一端进行删除操作，队列遵循先进先出原则。

（）

进行插入操作的一端称为队尾，插入元素叫做入队

进行删除操作的一端称为队头，删除元素叫做出队

（）

---

队列同栈一样，可以使用数组实现，也可以使用链表实现。

各接口实现

typedef int QDataType;typedef struct QueueNode{struct QueueNode* ne;QDataType val;}QNode;//队列节点typedef struct Queue{QNode* head;//用于找到队头QNode* tail;//用于找到队尾int count;}Queue;//队列的基本结构，void QuInit(Queue* ps);void QuDestory(Queue* ps);void QuPush(Queue* ps, QDataType x);void QuPop(Queue* ps);QDataType QuFront(Queue* ps);QDataType QuBack(Queue* ps);bool QuEmpty(Queue* ps);int QuSize(Queue* ps);

QuInit初始化和QuDestory销毁空间

void QuInit(Queue* ps){assert(ps);ps->head = ps->tail = NULL;ps->count = 0;}

站的初始化很简单，将结构体中的内容初始化为NULL和0即可

---

void QuDestory(Queue* ps){assert(ps);QNode* cur = ps->head;while (cur){QNode* ne = cur->ne;free(cur);cur = ne;}ps->count = 0;ps->head = ps->tail = cur = NULL;}

销毁空间，因为这个队列使用链表实现的并且开辟空间用的malloc函数，所以不能直接把head和tail给free了，这样不会把所有开辟的空间给释放，会造成内存泄漏。

QuPush入队和QuPop出队

void QuPush(Queue* ps, QDataType x){assert(ps);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->val = x;newnode->ne = NULL;if (ps->head == NULL){assert(ps->tail == NULL);ps->head = ps->tail = newnode;}else{ps->tail->ne = newnode;ps->tail = newnode;}ps->count++;}

开辟空间的操作不多做解释。

在进行入队操作时，分两种情况，当head和tail都为NULL的时候，插入一个元素之后，队头和队尾其实是在同一个位置的。

另一种情况是，队内存在元素，这个时候，只需要把要入队的元素链接在队尾，然后让在移动tail指针，移动到链接之后的队尾即可。

---

void QuPop(Queue* ps){assert(ps);assert(ps->count);if (ps->head->ne == NULL){free(ps->head);ps->head = ps->tail = NULL;}else{QNode* cur = ps->head->ne;free(ps->head);ps->head = cur;}ps->count--;}

出队的时候，要注意，队内没有元素的时候是能出队的。

如果说队内元素只有一个，那么直接free掉即可。反之，就需要先创建一个临时变量，用来记录一下队头的下一个元素，然后free掉队头，在让队头移动到临时变量的位置即可。

查看队头元素QuFront和QuBack查看队尾元素

这个很简单，只要队列不为空，直接返回队头指向的元素值即可

QDataType QuFront(Queue* ps){assert(ps);assert(ps->count);return ps->head->val;}

查看队尾元素同查看队头元素一样。

QDataType QuBack(Queue* ps){assert(ps);assert(ps->count);return ps->tail->val;}

判断队列是否为空QuEmpty

bool QuEmpty(Queue* ps){assert(ps);assert(ps->count);return ps->head == NULL;}

如果队列的头指针head为空，则队列为空，反之，则队列不为空

队列长度QuSize

在实现队列的时候，我们会用一个count，来记录队列的长度，在这里，直接把count当成返回值即可

int QuSize(Queue* ps){assert(ps);return ps->count;}

源码

.h文件

#pragma once#include #include #include using namespace std;typedef int QDataType;typedef struct QueueNode{struct QueueNode* ne;QDataType val;}QNode;typedef struct Queue{QNode* head;QNode* tail;int count;}Queue;void QuInit(Queue* ps);void QuDestory(Queue* ps);void QuPush(Queue* ps, QDataType x);void QuPop(Queue* ps);QDataType QuFront(Queue* ps);QDataType QuBack(Queue* ps);bool QuEmpty(Queue* ps);int QuSize(Queue* ps);

.cpp文件

#include "queue.h"void QuInit(Queue* ps){assert(ps);ps->head = ps->tail = NULL;ps->count = 0;}void QuDestory(Queue* ps){assert(ps);QNode* cur = ps->head;while (cur){QNode* ne = cur->ne;free(cur);cur = ne;}ps->count = 0;ps->head = ps->tail = cur = NULL;}void QuPush(Queue* ps, QDataType x){assert(ps);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->val = x;newnode->ne = NULL;if (ps->head == NULL){assert(ps->tail == NULL);ps->head = ps->tail = newnode;}else{ps->tail->ne = newnode;ps->tail = newnode;}ps->count++;}void QuPop(Queue* ps){assert(ps);assert(ps->count);if (ps->head->ne == NULL){free(ps->head);ps->head = ps->tail = NULL;}else{QNode* cur = ps->head->ne;free(ps->head);ps->head = cur;}ps->count--;}QDataType QuFront(Queue* ps){assert(ps);assert(ps->count);return ps->head->val;}QDataType QuBack(Queue* ps){assert(ps);assert(ps->count);return ps->tail->val;}bool QuEmpty(Queue* ps){assert(ps);assert(ps->count);return ps->head == NULL;}int QuSize(Queue* ps){assert(ps);return ps->count;}