数据结构——队列（C++实现）

队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除操作的特殊线性表，队列最重要的特性是先进先出（First In First Out）

入队列：进行插入操作的一端称为队尾

出队列：进行删除操作的一端称为队头

下面来看一下图片理解队列的结构

队列的实现

队列可以使用数组实现，也可以使用链表实现，但是相对于数组，使用链表会更优一些。因为如果使用数组的话，出队列的时候，是出在数组的第一个元素，需要将后面的元素都往前移动一个位置，会增加了O(N)的时间复杂度，效率会比较低。

入队列：

出队列：

队列的代码实现

队列有初始化队列、插入元素、删除元素、判断队列是否为空、队列的大小（即元素个数）、输出队头元素、输出队尾元素、释放内存

队列的头文件

#pragma once

struct QueueNode
{
	int data;
	QueueNode* next;
};

struct Queue
{
	QueueNode* head;
	QueueNode* tail;
};

//初始化队列
void QueueInit(Queue* q);

//插入数据
void QueuePush(Queue* q, int x);

//删除数据
void QueuePop(Queue* q);

//判断队列是否为空
bool QueueEmpty(Queue* q);

//队列大小
int QueueSize(Queue* q);

//输出队头数据
int QueueFront(Queue* q);

//输出队尾数据
int QueueBack(Queue* q);

//释放内存
void QueueDestroy(Queue* q);

1、初始化队列

每次创建一个队列，我们都应该先对它进行初始化

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

2、插入元素

在队尾插入元素

//插入数据
void QueuePush(Queue* q, int x)
{
	QueueNode* newNode = new QueueNode;
	newNode->data = x;
	newNode->next = NULL;
	if (q->head == NULL)
	{
		q->head = q->tail = newNode;
	}
	else
	{
		q->tail->next = newNode;
		q->tail = newNode;
	}
}

3、删除元素

在队头删除元素

//删除数据
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	QueueNode* next;
	next = q->head->next;
	delete q->head;
	q->head = next;

	//避免野指针问题
	if (q->head == NULL)
		q->tail = NULL;
}

4、队列是否为空

判断队列是否为空，若为空，返回真，若不为空，则返回假

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

5、队列的大小（即队列中元素的个数）

//队列大小
int QueueSize(Queue* q)
{
	assert(q);
	int n = 0;
	QueueNode* cur;
	cur = q->head;
	while (cur)
	{
		n++;
		cur = cur->next;
	}
	return n;
}

6、输出队头元素

//输出队头数据
int QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->head->data;
}

7、输出队尾元素

//输出队尾数据
int QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->tail->data;
}

8、销毁队列，释放内存

因为我们是动态添加元素，会使用到new ，所以必定需要有delete来释放内存空间

//释放内存
void QueueDestroy(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	QueueNode* cur = q->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		delete cur;
		cur = next;
	}
	q->head = q->tail = NULL;
}

完整的源文件代码

#include"Queue.h"
#include<assert.h>

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

//插入数据
void QueuePush(Queue* q, int x)
{
	QueueNode* newNode = new QueueNode;
	newNode->data = x;
	newNode->next = NULL;
	if (q->head == NULL)
	{
		q->head = q->tail = newNode;
	}
	else
	{
		q->tail->next = newNode;
		q->tail = newNode;
	}
}

//删除数据
void QueuePop(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	QueueNode* next;
	next = q->head->next;
	delete q->head;
	q->head = next;

	//避免野指针问题
	if (q->head == NULL)
		q->tail = NULL;
}

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

//队列大小
int QueueSize(Queue* q)
{
	assert(q);
	int n = 0;
	QueueNode* cur;
	cur = q->head;
	while (cur)
	{
		n++;
		cur = cur->next;
	}
	return n;
}

//输出队头数据
int QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->head->data;
}

//输出队尾数据
int QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	return q->tail->data;
}

//释放内存
void QueueDestroy(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));
	QueueNode* cur = q->head;
	while (cur)
	{
		QueueNode* next = cur->next;
		delete cur;
		cur = next;
	}
	q->head = q->tail = NULL;
}

总结

队列最重要的特点是先进先出，我们在做题或者做项目的时候要注意这一点

数据结构——队列（C++实现）

队列的概念及结构

队列的实现

队列的代码实现

完整的源文件代码

总结

推荐题目巩固知识

相关推荐