目录

• 队列的概念
• 队列的结构声明
• 队列的初始化
• 数据入队
• 判断队列是否为空
• 队列出数据
• 获取队头
• 获取队尾
• 获取队列长度
• 摧毁队列

队列的概念

只允许从一端插入数据，另一端出数据。
队头:出数据的一端叫队头。
队尾:入数据的一端叫队尾。
通俗地说，就是把栈的数据结构栈底给凿开了用来出数据。

入队演示

出队演示

队列的结构声明

我们知道队列有队头和队尾，队尾只添数据不删数据，队头只删数据不添数据。所以我们声明的时候可以用2个指针，一个指向队头，一个指向队尾。

typedef int QDataType;//队列的节点
struct QueueNode
{QDataType val;QueueNode* next;
};struct Queue
{//一个指针指向头QueueNode* head;//一个指针指向尾QueueNode* tail;
};

队列的初始化

队列初始时是没有值的，也就意味着没有节点，所以我们把它的头节点和尾节点都指向NULL。

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

数据入队

数据入队，我们只需要让tail 指向 新节点，如果 head是空的话，也就是刚初始化状态，那么让head也指向这个节点。

如果head 和tail为空

如果不为空

代码

//创建节点
QueueNode* CreateNode(QDataType x)
{QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));if (newNode == NULL){printf("malloc faile\n");exit(-1);}newNode->next = NULL;newNode->val = x;return newNode;
}//数据入队
void QueuePush(Queue* q, QDataType x)
{//断言assert(q);//创建节点QueueNode* newNode = CreateNode(x);//如果head NULLif (q->head == NULL){q->head = newNode;q->tail = newNode;}else{//尾节点指向新节点q->tail->next = newNode;//尾节点移动位置q->tail = newNode;}}

判断队列是否为空

很简单，如果头节点为空了，那么整个队列自然就为空了。因为是从队头开始出数据，没有数据出了，那就空了。

//判断队列是否为空
bool QueueIsEmpty(Queue* q)
{return q->head == NULL;
}

队列出数据

出数据很简单，释放头节点，让头节点指向下一个，因为队列是先进先出，所以头节点是队头，从队头开始出数据。

代码

//数据出队
void QueuePop(Queue* q)
{assert(q);//要保证队列里有数据可以删除assert(!QueueIsEmpty(q));//头删QueueNode* next = q->head->next;free(q->head);q->head = next;
}

获取队头

只要队列不为空，就可以获取到队头，所以断言一下，直接获取队头即可。

//获取队头
QDataType QueueGetFront(Queue* q)
{assert(q);//要保证队列里有数据assert(!QueueIsEmpty(q));return q->head->val;
}

获取队尾

和队头一样，直接获取，不过要保证队列有数据

//获取队尾
QDataType QueueGetBack(Queue* q)
{assert(q);//要保证队列里有数据assert(!QueueIsEmpty(q));return q->tail->val;
}

获取队列长度

从头开始找到尾，返回长度即可。

//获取队列长度
size_t QueueGetSize(Queue* q)
{assert(q);//要保证队列里有数据assert(!QueueIsEmpty(q));int len = 1;QueueNode* head = q->head;QueueNode* tail = q -> tail;while (head != tail){len++;head = head->next;}return len;
}

摧毁队列

直接释放所有节点，指针置为NULL即可

//销毁
void QueueDestroy(Queue* q)
{QueueNode* cru = q->head;while (cru != NULL){//存储下一个位置地址QueueNode* next = cru->next;free(cru);cru = next;}	
}

以上代码Git链接