数据结构-c/c++实现队列（链表实现）

目录

一.队列(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;}
}

测试结果