一.代码解析
//队列（链式非循环队列）
//从队尾入，从队头出（先进先出）
#include <iostream>
#include <assert.h>
#include <stdlib.h>
using namespace std;//数据类型
typedef int QDataType;//定义结构
//定义链式结构
typedef struct QueueNode {//结构体指针，储存的是下一个节点的地址struct QueueNode* next;//数据QDataType data;
}QueueNode;//定义队头和队尾
typedef struct Queue {QueueNode* head;QueueNode* tail;
}Queue;//初始化
//定义结构体指针，所以参数无需传二级指针
void QueueInit(Queue* pq) {//断言，检查传入的指针的正确与否assert(pq);//pq的队头和队尾指向空pq->head = pq->tail = NULL;
}//销毁
void QueueDestroy(Queue* pq) {//断言，检查传入的指针的正确与否assert(pq);//定义一个变量指向队头QueueNode* cur = pq->head;while (cur!=NULL) {//要先定义一个变量来指向cur的下一个节点//否则在释放掉cur后，系统会将cur的下一个节点置成随机值，导致数据丢失QueueNode* next = cur->next;free(cur);cur = next;}//将队头和队尾置为空pq->head = pq->tail = NULL;
}//插入数据
void QueuePush(Queue* pq,QDataType x) {//在队尾插入数据//断言，检查传入的指针的正确与否assert(pq);//要先扩容QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));//在扩容的节点中插入数据newnode->data = x;newnode->next = NULL;//插入数据要考虑两种情况//情况一：队列为空if (pq->head == NULL) {pq->head = pq->tail=newnode;}//情况二：队列不为空else{//在队尾插入数据//1.改变队尾指针的指向//2.将新插入的节点设置队尾pq->tail->next = newnode;pq->tail = newnode;}
}//声明判空函数
bool QueueEmpty(Queue* pq);//删除数据
void QueuePop(Queue* pq) {//断言，检查传入的指针的正确与否assert(pq);//删除数据时，若队列本身为空，则无法进行删除操作assert(!QueueEmpty(pq));//从队头开始删除数据//1.用一个变量储存队头元素指向的下一个元素//2.将队头元素free掉//3.将变量定义为新的队头QueueNode* next = pq->head->next;free(pq->head);pq->head = next;//要注意：当队头为空时，程序会崩溃if (pq->head==NULL) {pq->tail = NULL;}
}//检查是否为空
bool QueueEmpty(Queue* pq) {assert(pq);//为空返回真return pq->head == NULL;
}//取队尾元素
QDataType QueueBack(Queue* pq) {assert(pq);//判断队列是否为空assert(!QueueEmpty(pq));return pq->tail->data;
}//获取队头元素
QDataType QueueFront(Queue* pq) {assert(pq);//检查队列是否为空assert(!QueueEmpty(pq));return pq->head->data;
}//计算元素个数
int QueueSize(Queue* pq) {assert(pq);//定义一个变量用来记录队列中元素的个数int n = 0;//定义一个变量指向队头QueueNode* cur = pq->head;//当cur不为空时，n++while (cur!=NULL) {n += 1;cur = cur->next;}return n;
}//打印函数
void QueuePrint(Queue* pq) {assert(pq);//判断队列是否为空assert(!QueueEmpty(pq));//定义一个变量指向队头QueueNode* cur = pq->head;while (cur!=NULL) {cout << cur->data << "->";cur = cur->next;}cout << endl;
}//测试函数
void Test() {//初始化Queue q;QueueInit(&q);//插入数据cout << "插入数据:" << endl;QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);QueuePush(&q, 5);QueuePrint(&q);cout << "--------------------" << endl;//删除数据//先进先出，先进的先删除cout << "删除数据:" << endl;QueuePop(&q);QueuePop(&q);QueuePrint(&q);//3 4 5cout << "--------------------" << endl;//取队头元素cout << "取队头元素:" << endl;cout << QueueFront(&q) << endl;;//3cout << "--------------------" << endl;//取队尾元素cout << "取队尾元素:" << endl;cout << QueueBack(&q) << endl;//5//计算元素个数cout << "--------------------" << endl;cout << "队列中元素个数为:" << endl;cout << QueueSize(&q) << endl;//3//判断队列是否为空cout << "--------------------" << endl;cout << "队列判空与否:";if (QueueEmpty(&q)) {cout << "队列为空" << endl;}else {cout << "队列不为空" << endl;}cout << "--------------------" << endl;cout << "销毁队列:" << endl;//销毁队列QueueDestroy(&q);QueuePrint(&q);
}
int main()
{Test();return 0;
}
二.运行结果正确截图
