数据结构：队列(链表和数组模拟实现)

目录

1.何为队列

2.链表模拟实现

2.1 节点和队列创建

2.2 初始化队列

2.3 入队操作

2.4 出队操作

2.5 遍历队列

2.6 获取队首和队尾元素

2.7 判断队列是否为空

2.8 完整实现

3.?数组模拟实现

3.1 创建队列

3.2 入队和出队操作

3.3 遍历队列

3.4 获取队首和队尾元素

?3.5 判断队列是否为空

3.6 完整实现

---

1.何为队列

? ? ? ?队列也是一种数据结构，队列和栈不同的是，栈是先进后出，而队列是先进先出，这跟我们平时排队是一样的，先排的先办完事走，后排的后走，队列又被称为先进先出的线性表，简称FIFO(First In First Out)。

? ? ? ?那队列是怎么来实现的呢？下面从链表和数组两个方面来模拟实现

2.链表模拟实现

2.1 节点和队列创建

? ? ? ?我们用链表来模拟每个队列元素，可以用链表节点来表示，data是数据域，next是指针域

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

? ? ? 栈有栈顶，那队列也应该有队首和队尾

typedef struct Queue
{
	QueueNode* head, * tail;
	int size;
}Queue;

2.2 初始化队列

? ? ? 创建一个队列和队首、队尾，并进行初始化

void QueueCreate(Queue* que)
{
	que->head = NULL;
	que->tail = NULL;
	que->size = 0;
}

2.3 入队操作

? ? ? 万事具备，就差元素入队填满队列了！

? ? ? 队列的插入操作叫做入队，它是将数据元素从队尾进行插入的过程

? ? ? 4号元素是原先的队尾，在它后面插入元素6，就是入队的过程

? ? ? 我们首先创建一个值为data的队列节点vtx，如果队尾非空，则将vtx作为队尾元素的后继，否则将队首元素置为vtx，队尾元素变成vtx，队列的长度加一。

void QueueEnter(Queue* que, int data)//入队就是将元素从队尾插入的过程
{

	QueueNode* vtx = (QueueNode*)malloc(sizeof(QueueNode));
	vtx->data = data;
	vtx->next = NULL;
	if (que->tail)
	{
		que->tail->next = vtx;
	}
	else
	{
		que->head = vtx;
	}
	que->tail = vtx;
	que->size++;
}

2.4 出队操作

? ? ? 队列的删除操作叫做出队，它是将队首元素进行删除的过程。

? ? ? 将队首变成原先队首的后继元素，就实现了出队操作

? ? ? 我们将队首元素缓存到temp中，将当前的队首变成temp的后继，释放temp的内存，队列长度减一，如果此时队列为空，则将队尾置为空。

void QueueDelete(Queue* que)
{
	QueueNode* temp = que->head;
	que->head = temp->next;
	free(temp);
	que->size--;
	if (que->size == 0)
	{
		que->tail = NULL;
	}

2.5 遍历队列

? ? 我们建立一个cur指向队首，如果cur!=NULL，则cur变为cur的后继

void QueueTravel(Queue* que)
{
	QueueNode* cur = que->head;
	while (cur)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}

2.6 获取队首和队尾元素

int QueueGetFront(Queue* que)//获取队首元素
{
	return que->head->data;
}
int QueueGetBack(Queue* que)//获取队尾元素
{
	return que->tail->data;
}

2.7 判断队列是否为空

? ? ?如果队首等于队尾，说明队列为空，否则队列不为空。

bool QueueIsEmpty(Queue* que)
{
	return que ->head == que->tail;
}

2.8 完整实现

#include<stdio.h>
#include<stdlib.h>
typedef struct QueueNode//创建队列节点
{
	int data;
	struct QueueNode* next;
}QueueNode;
typedef struct Queue//创建队列结构
{
	QueueNode* head, * tail;//队首允许删除，队尾允许插入
	int size;
}Queue;
void QueueCreate(Queue* que)//队列初始化
{
	que->head = NULL;
	que->tail = NULL;
	que->size = 0;
}
void QueueEnter(Queue* que, int data)//入队就是将元素从队尾插入的过程
{

	QueueNode* vtx = (QueueNode*)malloc(sizeof(QueueNode));
	vtx->data = data;
	vtx->next = NULL;
	if (que->tail)
	{
		que->tail->next = vtx;
	}
	else
	{
		que->head = vtx;
	}
	que->tail = vtx;
	que->size++;
}
void QueueDelete(Queue* que)//出队就是将元素从队尾删除的过程
{
	QueueNode* temp = que->head;
	que->head = temp->next;
	free(temp);
	que->size--;
	if (que->size == 0)
	{
		que->tail = NULL;
	}
}
void QueueTravel(Queue* que)//队列的遍历
{
	QueueNode* cur = que->head;
	while (cur)
	{
		printf("%d ", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
int QueueGetFront(Queue* que)//获取队首元素
{
	return que->head->data;
}
int QueueGetBack(Queue* que)//获取队尾元素
{
	return que->tail->data;
}
bool QueueIsEmpty(Queue* que)//判断队列是否为空
{
	return que ->head == que->tail;
}
int main()
{
	Queue* que = (Queue*)malloc(sizeof(Queue));
	QueueCreate(que);
	int n;
	scanf_s("%d\n", &n);

	//执行n次入队操作
	while (n--)
	{
		int data;
		scanf_s("%d", &data);
		QueueEnter(que, data);
	}

	//遍历并打印队列元素
	QueueTravel(que);
	
	//打印队首元素
     printf("队首元素为：%d\n", QueueGetFront(que));

	//打印队尾元素
	 printf("队尾元素为：%d\n", QueueGetBack(que));

	//判断队列是否为空
	printf("%d",QueueIsEmpty(que));

	return 0;
	
}

3.?数组模拟实现

3.1 创建队列

? ? ?在用数组创建队列时，不需要我们开辟空间，数组已经开好了

const int N = 100010;
int q[N];//队列
int hh = 0;//hh表示队首
int tt = -1;//tt表示队尾

3.2 入队和出队操作

? ? ?我们只需要hh++即可完成队首元素的删除操作，并不是真的删除，而是把队首元素的下标从队列数组中剔除了。

q[++tt] = x;//入队
hh++;//出队

3.3 遍历队列

//遍历并打印队列每个元素的值
for (int i = 0; i <=tt;i++)
{
	printf("%d ", q[i]);
}
printf("\n");

3.4 获取队首和队尾元素

//获取队首的值
printf("队首的值为：%d\n", q[hh]);

//获取队尾的值
printf("队尾的值为：%d\n", q[tt]);

3.5 判断队列是否为空

? ? ?如果hh<=tt说明队列不为空

//判断队列是否为空，如果hh<=tt，则表示不为空
if (hh <= tt)printf("队列不为空");

3.6 完整实现

#include<stdio.h>
const int N = 100010;
int q[N];
int hh = 0;//hh表示队首
int tt = -1;//tt表示队尾
int main()
{
	int n;
	scanf_s("%d", &n);
	
	while (n--)
	{
		int x;
		scanf_s("%d", &x);
		q[++tt] = x;//入队操作，向队尾插入一个数
	}

	//遍历并打印队列每个元素的值
	for (int i = 0; i <=tt;i++)
	{
		printf("%d ", q[i]);
	}
	printf("\n");

	hh++;//出队操作，从队首删除一个数
	printf("队首的值为：%d\n", q[hh]);
	
	//判断队列是否为空，如果hh<=tt，则表示不为空
	if (hh <= tt)printf("队列不为空");

	return 0;
}