队列及其实现_队列的实现csdn

目录

一：队列

1.队列的概念及结构

2.队列的实现

<1>.初始化队列

<2>.队尾入队列

<3>.队头出队列

<4>.获取队列头部元素

<5>.获取队列队尾元素

<6>.获取队列中有效元素个数 

<7>.销毁队列 

二：完整代码

---

一：队列

1.队列的概念及结构

---

<1>.初始化队列

---

void QueueInit(Queue* q)；

---

令队头，队尾为空，队列中的元素个数为 0 .

代码为：

// 初始化队列 
void QueueInit(Queue* q)
{
	assert(q);
 
	q-> _rear = NULL;
	q-> _front = NULL;
	q->size = 0;
}

<2>.队尾入队列

---

 void QueuePush(Queue* q, QDataType data);

---

 在队列尾部，入队列，本质上是对链表进行操作，需要开辟一个一个新的节点，将其于队列中的内容链接起来，最后对元素总数进行 ++ 操作。

 画图分析如下：

 代码为：

// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
 
	//插入数据 --- 链表 --- 开辟新的节点(结构体)
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->_data = data;
	newnode->_next = NULL;
 
	//判断队列中是否有元素
	if (q->_rear == NULL)
	{
		assert(q->_front == NULL);
		//相当于对链表进行头插
		q->_front = q->_rear = newnode;
	}
	else
	{
		//相当于在队列的结尾，插入一个结构体
		q->_rear->_next = newnode;
		q->_rear = newnode;
	}
	q->size++;
}

<3>.队头出队列

---

 void QueuePop(Queue* q);

---

在出队列时，我们需要考虑队列中是否有元素，若队列为空，则无法进行出队列操作 --- 即需要对链表进行判空。若队列中有元素，则需要考虑队列中有几个节点：若队列中只有一个节点，进行出队列操作一次后，队列即为空。若队列中有多个节点时，可以开辟一个新的节点用于记录头节点的下一个位置，然后释放头节点，将开辟的新节点看作队列的队头。

画图分析：

 

 代码为：

// 检测队列是否为空，如果为空返回零结果
int QueueEmpty(Queue* q)
{
	assert(q);
 
	return q->_rear == NULL;
}
// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
 
	//需要判断队列中是否有元素 --- 若队列为空，则无法进行出队列
	assert(!QueneEmpty(q));
 
	//判断有几个节点 --- 一个节点 --- 多个节点
	if (q->_front->_next == NULL)
	{
		free(q->_front);
		q->_front = NULL;
		q->_rear = NULL;
	}
	else
	{
		QNode* next = q->_front->_next;
		free(q->_front);
		q->_front = next;
	}
	q->size--;
}

<4>.获取队列头部元素

---

 QDataType QueueFront(Queue* q);

---

获取队列头部元素时，需要判断队列是否为空，若队列为空，则无队列头部元素。

获取头部元素 q->_front_data

代码为：

// 检测队列是否为空，如果为空返回零结果
int QueueEmpty(Queue* q)
{
	assert(q);
 
	return q->_rear == NULL;
}
 
 
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	//需要判断队列中是否有元素 --- 若队列为空，则无队列头部元素
	assert(!QueneEmpty(q));
 
	return q->_front->_data;
}

<5>.获取队列队尾元素

---

 QDataType QueueBack(Queue* q);

---

获取队列队尾元素时，需要判断队列中是否有元素，即需要判断队列是否为空。

获取尾部元素 q->_rear->_data

代码为：

// 检测队列是否为空，如果为空返回零结果
int QueueEmpty(Queue* q)
{
	assert(q);
 
	return q->_rear == NULL;
}
 
 
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	//需要判断队列中是否有元素 --- 若队列为空，则无队列尾q元素
	assert(!QueneEmpty(q));
 
	return q->_rear->_data;
}

<6>.获取队列中有效元素个数 

---

int QueueSize(Queue* q);

---

我们在入队列时，进行了q->_size++ , 出队列时，进行 q->_size-- 。

即 q->_size 即为队列中有效元素的个数。

代码为：

// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
 
	return q->size;
}

<7>.销毁队列 

---

void QueueDestroy(Queue* q);

---

队列内部建立的是链表结构，而链表在释放的时候需要一个一个销毁，在此时，我们需要建立一个结构体指针指向队列的头部（QNode* cur = q->_front)，然后一个一个地释放节点，循环条件更替条件为：cur = cur->_next , 当 cur 为空时，循环结束。然后将队列的内部元素置为空或者0。

画图分析：

 代码为：

// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	//链表需要一个一个销毁 -- 修改的为链表
	QNode* cur = q->_front;
 
	while (cur)
	{
		QNode* next = cur->_next;
		free(cur);
		cur = next;
	}
 
	q->size = 0;
	q->_front = NULL;
	q->_rear = NULL;
}

二：完整代码

 queue.h

#pragma once
 
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
 
typedef int QDataType;
 
 //链式结构：表示队列 
typedef struct QListNode
{
	struct QListNode* _next;
	QDataType _data;
}QNode;
 
// 队列的结构 
typedef struct Queue
{
	QNode* _front;//队头
	QNode* _rear;//队尾
	int size;
}Queue;
 
 //初始化队列 
void QueueInit(Queue* q);
// 队尾入队列 
void QueuePush(Queue* q, QDataType data);
// 队头出队列 
void QueuePop(Queue* q);
// 获取队列头部元素 
QDataType QueueFront(Queue* q);
// 获取队列队尾元素 
QDataType QueueBack(Queue* q);
// 获取队列中有效元素个数 
int QueueSize(Queue* q);
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
int QueueEmpty(Queue* q);
// 销毁队列 
void QueueDestroy(Queue* q);

queue.c

#include"quene.h"
 
// 初始化队列 
void QueueInit(Queue* q)
{
	assert(q);
 
	q-> _rear = NULL;
	q-> _front = NULL;
	q->size = 0;
}
 
// 队尾入队列 
void QueuePush(Queue* q, QDataType data)
{
	assert(q);
 
	//插入数据 --- 链表 --- 开辟新的节点(结构体)
	QNode* newnode = (QNode*)malloc(sizeof(QNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return;
	}
	newnode->_data = data;
	newnode->_next = NULL;
 
	//判断队列中是否有元素
	if (q->_rear == NULL)
	{
		assert(q->_front == NULL);
		//相当于对链表进行头插
		q->_front = q->_rear = newnode;
	}
	else
	{
		//相当于在队列的结尾，插入一个结构体
		q->_rear->_next = newnode;
		q->_rear = newnode;
	}
	q->size++;
}
 
// 检测队列是否为空，如果为空返回零结果
int QueueEmpty(Queue* q)
{
	assert(q);
 
	return q->_rear == NULL;
}
// 队头出队列 
void QueuePop(Queue* q)
{
	assert(q);
 
	//需要判断队列中是否有元素 --- 若队列为空，则无法进行出队列
	assert(!QueneEmpty(q));
 
	//判断有几个节点 --- 一个节点 --- 多个节点
	if (q->_front->_next == NULL)
	{
		free(q->_front);
		q->_front = NULL;
		q->_rear = NULL;
	}
	else
	{
		QNode* next = q->_front->_next;
		free(q->_front);
		q->_front = next;
	}
	q->size--;
}
 
// 获取队列头部元素 
QDataType QueueFront(Queue* q)
{
	assert(q);
	//需要判断队列中是否有元素 --- 若队列为空，则无队列头部元素
	assert(!QueneEmpty(q));
 
	return q->_front->_data;
}
 
 
// 获取队列队尾元素 
QDataType QueueBack(Queue* q)
{
	assert(q);
	//需要判断队列中是否有元素 --- 若队列为空，则无队列尾q元素
	assert(!QueneEmpty(q));
 
	return q->_rear->_data;
}
 
// 获取队列中有效元素个数 
int QueueSize(Queue* q)
{
	assert(q);
 
	return q->size;
}
 
// 销毁队列 
void QueueDestroy(Queue* q)
{
	assert(q);
	//链表需要一个一个销毁 -- 修改的为链表
	QNode* cur = q->_front;
 
	while (cur)
	{
		QNode* next = cur->_next;
		free(cur);
		cur = next;
	}
 
	q->size = 0;
	q->_front = NULL;
	q->_rear = NULL;
}