【数据结构】C++语言实现队列(详细解读)

用户11036582

发布于 2024-05-24 14:02:35

420

发布于 2024-05-24 14:02:35

文章被收录于专栏：跟我一起学编程跟我一起学编程

c语言中的小小白-CSDN博客c语言中的小小白关注算法,c++,c语言,贪心算法,链表,mysql,动态规划,后端,线性回归,数据结构,排序算法领域.

https://blog.csdn.net/bhbcdxb123?spm=1001.2014.3001.5343

给大家分享一句我很喜欢我话： 知不足而奋进，望远山而前行！！！ 铁铁们，成功的路上必然是孤独且艰难的，但是我们不可以放弃，远山就在前方，但我们能力仍然不足，所有我们更要奋进前行！！！今天我们更新了队列内容，

什么是队列？

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（head）进行删除操作，而在表的后端（tail）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。

这个队列就可以理解成我们平时的排队，先进入的先出去，与我们之前实现的先进后出的栈相反。

用什么来实现栈？

再把上次的图拿出来，我们看看是用线性表来实现队列，还是链表比较好❓

由于我们队列中有多少元素不确定，为了方便，我们使用链表，可以做到需要就直接申请，还有一点就是队列是先进先出，顺序固定，不需要随机访问。所以我们这里实现队列使用链表。

队列的实现

头文件：

#include<stdlib.h>
#include<assert.h>
#include<stdio.h>
#include<stdbool.h>
#include<iostream>

定义结构体：

typedef int QDataType;

typedef struct QueueNode//队列的元素节点
{
	struct QueueNode* next;
	QDataType val;
}QNode;

typedef struct Queue//队列
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;

函数声明：

//初始化
void QueueInit(Queue* pq);

//队尾插入
void QueuePush(Queue* pq, QDataType x);

//头删
void QueuePop(Queue* pq);

//获取长度
int QueueSize(Queue* pq);

//队列的销毁
void QueueDestroy(Queue* pq);

//取出队首元素
QDataType QueueFront(Queue* pq);

//取出队尾元素
QDataType QueueBack(Queue* pq);

//判断是否为空
bool QueueEmpty(Queue* pq);

函数的实现：

队列的初始化：

//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}

初始化还是比较简单的，就是令这个头和尾都为NULL，size=0。

队列的尾插：

//尾插
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc failed!");
		exit(0);
	}

	newnode->next = NULL;
	newnode->val = x;
	
	if (pq->ptail == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail = pq->ptail->next = newnode;

	}
	pq->size++;
}

尾插这里我们要注意分为两种情况，一种就是此时这个队列还为空队列，这时就要令ptail和phead都为newnode，然后若不是，那么我们就只令ptail的下一个点等于newnode，然后ptail指向下一个点。

队列的头删：

//头删
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->size != 0);

	//一个节点，防止出现野指针
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;

		pq->size--;
	}
}

头删我们这里也要注意，因为我们这个队列玩意只有一个点，那么我们删除之后可能就会造成ptail为野指针的情况，所以我们这里也要分情况：一种就是如果phead指向NULL，即只有一个节点，所以我们就要free掉phead的同时，还要将两个都置为NULL，另一种情况就只需要关注phead，操作完之后将phead指向下一个点。

获取队列长队：

//获取长度
int QueueSize(Queue* pq)
{
	assert(pq);
	
	return pq->size;
}

这里就是我们前面创建对列要加一个size的原因，这样我们就可以方便的知道队列的大小，否则每次想得到队列的大小都要重新计算一遍，浪费更多的时间。

队列的销毁：

//队列的销毁
void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur); 
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
}

队列的销毁也没什么好说的，就是创建一个新的队列，然后循环不断free每一个队列点。

获取队尾元素和队首元素：

//获取队首元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead && pq->ptail);//防止为空
	return pq->phead->val;

}
//获取队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->phead && pq->ptail);
	
	return pq->ptail->val;
}

这个就是先断言一下，然后直接返回对应的值即可。

判断是否为空：

//判断是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->ptail == NULL;
}

这里直接用bool来判断，是就返回true，否则返回false。

完整代码：

Queue.h

#pragma once
#include<stdlib.h>
#include<assert.h>
#include<stdio.h>
#include<stdbool.h>
#include<iostream>

using namespace std;

typedef int QDataType;

typedef struct QueueNode
{
	struct QueueNode* next;
	QDataType val;
}QNode;

typedef struct Queue
{
	QNode* phead;
	QNode* ptail;
	int size;
}Queue;


//初始化
void QueueInit(Queue* pq);

//队尾插入
void QueuePush(Queue* pq, QDataType x);

//头删
void QueuePop(Queue* pq);

//获取长度
int QueueSize(Queue* pq);

//队列的销毁
void QueueDestroy(Queue* pq);

//取出队首元素
QDataType QueueFront(Queue* pq);

//取出队尾元素
QDataType QueueBack(Queue* pq);

//判断是否为空
bool QueueEmpty(Queue* pq);

Queue.cpp:

#include"Queue.h"


//初始化
void QueueInit(Queue* pq)
{
	assert(pq);
	pq->phead = NULL;
	pq->ptail = NULL;
	pq->size = 0;
}


//尾插
void QueuePush(Queue* pq, QDataType x)
{
	assert(pq);
	
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc failed!");
		exit(0);
	}

	newnode->next = NULL;
	newnode->val = x;
	
	if (pq->ptail == NULL)
	{
		pq->phead = pq->ptail = newnode;
	}
	else
	{
		pq->ptail = pq->ptail->next = newnode;

	}
	pq->size++;
}



//头删
void QueuePop(Queue* pq)
{
	assert(pq);
	assert(pq->size != 0);

	//一个节点，防止出现野指针
	if (pq->phead->next == NULL)
	{
		free(pq->phead);
		pq->phead = pq->ptail = NULL;
	}
	else
	{
		QNode* next = pq->phead->next;
		free(pq->phead);
		pq->phead = next;

		pq->size--;
	}
}



//获取长度
int QueueSize(Queue* pq)
{
	assert(pq);
	
	return pq->size;
}


//队列的销毁
void QueueDestroy(Queue* pq)
{
	assert(pq);

	QNode* cur = pq->phead;
	while (cur)
	{
		QNode* next = cur->next;
		free(cur); 
		cur = next;
	}
	pq->phead = pq->ptail = NULL;
}

//获取队首元素
QDataType QueueFront(Queue* pq)
{
	assert(pq);
	assert(pq->phead && pq->ptail);//防止为空
	return pq->phead->val;

}
//获取队尾元素
QDataType QueueBack(Queue* pq)
{
	assert(pq);
	assert(pq->phead && pq->ptail);
	
	return pq->ptail->val;
}





//判断是否为空
bool QueueEmpty(Queue* pq)
{
	assert(pq);

	return pq->ptail == NULL;
}

test.cpp:

#include"Queue.h"

int main()
{
	Queue q;

	QueueInit(&q);
	QueuePush(&q, 1);
	QueuePush(&q, 2);
	QueuePush(&q, 3);
	QueuePush(&q, 4);
	QueuePush(&q, 5);
	QueuePop(&q);
	while (!QueueEmpty(&q))
	{
		cout << QueueFront(&q)<<endl;
		QueuePop(&q);
	}

	return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-05-24，如有侵权请联系 cloudcommunity@tencent.com 删除

链表