目录
一.队列(queue)的基本介绍
二.队列的常用操作
三.实现代码
3.1 队列的定义
3.2 队列的初始化(QueueInit)
3.3 队列的销毁(QueueDestory)
3.4插入数据(QueuePush)
3.5 删除数据(QueuePop)
3.6 返回队首数据(QueueFront)
3.6 返回队尾数据(QueueFront)
3.7 返回队列元素的大小(QueueSize)
3.8 判断队列是否为空(QueueEmpty)
四.简单测试
一.队列(queue)的基本介绍
队列是一种只能在一端进行插入，另外一端进行删除元素的结构。
队列是一种先进先出的数据结构，之前聊到的栈是一种后进先出的数据结构。
队列允许插入数据的一端称为队尾，允许删除数据的一端称为队首。
我们可以使用顺序表来实现队列，也可以使用链表来实现队列。不过，对于队列来说，使用链表实现的好处比线性表多。所以我们使用链表来实现队列。
使用链表实现队列的好处：
数组队列弹出数据需要大量挪动数据，消耗大，而链表只需改动一个节点
二.队列的常用操作
//初始化队列
void QueueInit(Queue* pq);//销毁队列
void QueueDestory(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);三.实现代码
3.1 队列的定义
先定义出节点的结构体，再定义队列（包含队首和队尾）
//数据类型
typedef int DataType;//链表节点
typedef struct QueueNode
{DataType val;struct QueueNode* next;
}QueueNode;//链表的定义
typedef struct Queue
{QueueNode* head;QueueNode* tail;
};3.2 队列的初始化(QueueInit)
void QueueInit(Queue* pq)
{assert(pq);pq->head = nullptr;pq->tail = nullptr;
}3.3 队列的销毁(QueueDestory)
void QueueDestory(Queue* pq)
{assert(pq);//使用循环依次找到队列中的所有节点并依次销毁QueueNode* cur = pq->head;while (cur != nullptr){QueueNode* curnext = cur->next;delete cur;cur = curnext;}//将头尾指针置空pq->head = pq->tail = nullptr;
}3.4插入数据(QueuePush)
//只能从尾节点后面插入新节点
void QueuePush(Queue* pq, DataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));//开辟新节点assert(newnode != nullptr);//防止开辟失败newnode->val = x;newnode->next = nullptr;//如果链表为空，将新节点赋值给头节点if (pq->head == nullptr){pq->head = pq->tail = newnode;}else{//插入新节点，更新队尾节点pq->tail->next = newnode;pq->tail = newnode;}
}3.5 删除数据(QueuePop)
//队列头删尾插
void QueuePop(Queue* pq)
{assert(pq);assert(pq->head);QueueNode* newhead = pq->head->next;free(pq->head);pq->head = newhead;//注意，当队列中只有一个节点的时候，将头节点置空的时候，尾节点会变为野指针！//尾指针仍指向删除前的头节点if (pq->head == nullptr){pq->tail = pq->head;}
}3.6 返回队首数据(QueueFront)
DataType QueueFront(Queue* pq)
{assert(pq);assert(pq->head != nullptr);return pq->head->val;
}3.6 返回队尾数据(QueueFront)
DataType QueueBack(Queue* pq)
{assert(pq);assert(pq->head != nullptr);return pq->tail->val;
}3.7 返回队列元素的大小(QueueSize)
//计算大小只需循环遍历即可
int QueueSize(Queue* pq)
{assert(pq);int n = 0;QueueNode* cur = pq->head;while (cur){n++;cur = cur->next;}return n;
}3.8 判断队列是否为空(QueueEmpty)
bool QueueEmpty(Queue* pq)
{if (pq->head){return true;}else{return false;}
}四.简单测试
测试代码
#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"void QueueInit(Queue* pq)
{assert(pq);pq->tail = NULL;pq->head = NULL;
}void QueueDestory(Queue* pq)
{assert(pq);QueueNode* cur = pq->head;while (cur != NULL){QueueNode* curnext = cur->next;free(cur);cur = curnext;}pq->head = pq->tail = NULL;
}void QueuePush(Queue* pq, QDataType x)
{assert(pq);QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));assert(newnode!=NULL);newnode->data = x;newnode->next = NULL;if (pq->head == NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = pq->tail->next;}
}void QueuePop(Queue* pq)
{//队列先进先出，所以是尾插头删除assert(pq);assert(pq->head!=NULL);QueueNode* newhead = pq->head->next;free(pq->head);pq->head = newhead;//注意，当head指向空的时候，tail还指向尾。此时tail指针是野指针，队列无法再次插入数据if (pq->head == NULL)pq->tail = pq->head;
}QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->head != NULL);return pq->head->data;
}QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->head != NULL);return pq->tail->data;
}int QueueSize(Queue* pq)
{assert(pq);int n = 0;QueueNode* cur = pq->head;while (cur){n++;cur = cur->next;}return n;
}bool QueueEmpty(Queue* pq)
{if (pq->head== NULL){return true;}else{return false;}
}测试结果
