带你深入了解队列(c/cpp双版本模拟实现)

目录

一.队列的概念及结构

二.队列的实现

2.1队列的结构

2.2初始化队列

2.3队尾入队列 

2.4队头出队列 

2.5获取队列头部元素 

2.6获取队列队尾元素

2.7获取队列中有效元素个数 

2.8检测队列是否为空

2.9销毁队列 

三.C++ 版本模拟实现队列

---

一.队列的概念及结构

队列：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out) 入队列：进行插入操作的一端称为队尾 出队列：进行删除操作的一端称为队头

二.队列的实现

队列也可以数组和链表的结构实现，使用链表的结构实现更优一些，因为如果使用数组的结构，出队列在数组头上出数据，效率会比较低。

2.1队列的结构

首先，先建立一个单链表，用来存储数据和链接结构

然后建立队列，队列有俩个节点，一个指向队列的开始，一个指向结尾

size 用于存储队列长度

// 链式结构：表示队列
typedef struct QListNode
{
struct QListNode* _pNext;
QDataType _data;
}QNode;
 
// 队列的结构
typedef struct Queue
{
QNode* _front;
QNode* _rear;
int size;
}Queue;

2.2初始化队列

队列的初始化，把队列的头尾都指向空，size设为0

void QueueInit(Queue* q)
{
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}

2.3队尾入队列 

1.首先，malloc一个节点cur

2.判断malloc是否开辟成功

3.给创建成功的节点进行赋值

4.判断如果队列为空，直接插入节点即可（使队列的头尾都指向这个节点）

5.如果不为空，使队列的尾的下一个位置指向新创建的节点，在然后队列的尾指向这个节点

6.最后，数据加一size++

void QueuePush(Queue* q, QDataType data)
{
	QNode* cur = (QNode*)malloc(sizeof(QNode));
     
	if (cur == NULL)
	{
		perror("malloc ");
		exit(-1);
	}
	cur->data = data;
	cur->next = NULL;
 
	if (q->rear == NULL)
	{
		q->front = q->rear = cur;
	}
	else
	{
		q->rear->next = cur;
		q->rear = cur;
	}
	q->size++;
}

2.4队头出队列 

1.先判断队列是否只有为空，如果是，退出

2.如果队列只有一个数据，直接对队列进行销毁即可

3.如果队列有多个数据，新建一个节点cur等于队列“头”的下一个地址，然后释放掉队头，再把队头指向cur（以前对头的下一个地址），使得第二个数据成为队头

4.最后，数据减一size--

void QueuePop(Queue* q)
{
     if(q->front==NULL)
     {
      exit(-1);
     }
	if (q->front->next == NULL)
	{
		free(q->front);
		q->front = q->rear = NULL;
	}
	else
	{
		QNode* cur = q->front->next;
		free(q->front);
		q->front = cur;
	}
	q->size--;
}

2.5获取队列头部元素 

直接取头指向的数据即可

QDataType QueueFront(Queue* q)
{
	return q->front->data;
}

2.6获取队列队尾元素

直接取队列尾指向的元素即可

QDataType QueueBack(Queue* q)
{
	return q->rear->data;
}

2.7获取队列中有效元素个数 

直接返回队列的size

int QueueSize(Queue* q)
{
	return q->size;
}

2.8检测队列是否为空

检测队列是否为空，如果为空返回非零结果，如果非空返回0 

bool QueueEmpty(Queue* q)
{
	return q->front == NULL && q->rear == NULL;
}

2.9销毁队列 

1.采用while循环依次把队列中的节点全部释放

2.使队列头尾指向空，并且size置为0

void QueueDestroy(Queue* q)
{
	QNode* cur = q->front;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
	}
	q->front = NULL;
	q->rear = NULL;
	q->size = 0;
}

三.C++ 版本模拟实现队列
 

     考虑到学校有好多老师上课，虽然说得是用c语言实现，却用cpp进行操作，现在给大家更新cpp版本的队列的模拟实现，cpp版本的扩容使用的new，函数参数使用的&，可能有同学对指针使用不太熟悉，所以我们同意用&（引用）来实现，方便大家的理解，就不再详细的进行说明了，思路跟c语言实现的一样，只是c和cpp的语言差距有所不同。

#include<iostream>
#include<assert.h>
using namespace std;
 
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)
{
	
	q.front = NULL;
	q.rear = NULL;
	q.size = 0;
}
// 队尾入队列 
void QueuePush(Queue& q, QDataType data)
{
	QNode* cur = new QNode[sizeof(QNode)];
 
	if (cur == NULL)
	{
		perror("malloc ");
		exit(-1);
	}
	cur->data = data;
	cur->next = NULL;
 
	if (q.rear == NULL)
	{
		q.front = q.rear = cur;
	}
	else
	{
		q.rear->next = cur;
		q.rear = cur;
	}
	q.size++;
}
// 队头出队列 
void QueuePop(Queue& q)
{
	if (q.front->next == NULL)
	{
		delete q.front;
		q.front = q.rear = NULL;
	}
	else
	{
		QNode* cur = q.front->next;
		delete q.front;
		q.front = cur;
	}
	q.size--;
}
// 获取队列头部元素 
QDataType QueueFront(const Queue& q)
{
	return q.front->data;
}
// 获取队列队尾元素 
QDataType QueueBack(const Queue& q)
{
	return q.rear->data;
}
// 获取队列中有效元素个数 
int QueueSize(const Queue& q)
{
	return q.size;
}
// 检测队列是否为空，如果为空返回非零结果，如果非空返回0 
bool QueueEmpty(const Queue& q)
{
	return q.front == NULL && q.rear == NULL;
}
// 销毁队列 
void QueueDestroy(Queue& q)
{
	QNode* cur = q.front;
	while (cur)
	{
		QNode* del = cur;
		cur = cur->next;
		free(del);
	}
 
	q.front = NULL;
	q.rear = NULL;
	q.size = 0;
}
 
int main()
{
	Queue q;
	QueueInit(q);
 
	QueuePush(q, 1);
	QueuePush(q, 2);
	QueuePush(q, 3);
	for (int i = 0;i < 3;i++)
	{
		cout << QueueFront(q) << endl;
		QueuePop(q);
	}
 
	printf("%d", !QueueEmpty(q));
 
	QueueDestroy(q);
	return 0;
}