数据结构实验2：队列的应用

目录

一、实验目的

二、实验原理

1.1 队列的基本操作

1.1.1 队列的定义

1.1.2 队列的初始化

1.1.3 入队操作

1.1.4 出队操作

?1.1.5 检查队列是否为空

1.1.6 返回队列的长度?

2.1队列的运用

三、实验内容

问题描述

代码

截图

分析

---

一、实验目的

1、理解并掌握队列的逻辑结构和存储结构;理解队列的相关基本运算;

2、编程对相关算法进行验证;

3、学会利用队列解决实际问题。

二、实验原理

队列是一种数据结构，它遵循先进先出（First In First Out，FIFO）的原则。队列通常用于在程序中按顺序存储和访问数据元素。

1.1 队列的基本操作

1.1.1 队列的定义

可以使用结构体来定义队列的基本结构。一个典型的队列结构可能包括一个数组（用于存储数据元素）和两个指针（分别指向队列的前端和后端）。

#define MAX_SIZE 100

typedef struct Queue {
	int array[MAX_SIZE];
	int front, rear;
};

front指向队列的第一个元素，rear指向队列的最后一个元素。

1.1.2 队列的初始化

在使用队列之前，需要进行初始化。将队列的前端和后端指针都设置为-1，表示队列为空。

void Initialize_Queue(Queue* queue) {
	queue->front = -1;
	queue->rear = -1;
}

1.1.3 入队操作

将元素添加到队列的后端。在进行入队操作时，需要更新队列的rear指针。

void enqueue(Queue* queue,int elem) {
	if ((queue->rear == (MAX_SIZE - 1))&&(queue->front==0)) {//如果队列已满
		cout << "队列已满，不可再添加元素"<<endl;
		return;
	}
	if(queue->front==-1){//如果队列为空，更新front指针
		queue ->front = 0;
	}
	queue->rear++;
	queue->rear = queue->rear % MAX_SIZE;
	queue->array[queue->rear] = elem;//添加到队尾
}

其中队列为空时，front指针要更新，这个不容易想得到?

1.1.4 出队操作

?从队列的前端移除元素。在进行出队操作时，需要更新队列的front指针。

int dequeue(Queue* queue) {
	int elem;
	if (queue->front == -1) {//如果队列为空
		cout << "队列为空" << endl;
		return -1;
	}
	elem=queue->array[queue->front];
	if (queue->front == queue->rear) {//如果队列中只有一个元素，则将队列清空
		Initialize_Queue(queue);
	}
	else {
		queue->front++;
		//循环队列的关键之处
		if (queue->front > (MAX_SIZE - 1)) {
			queue->front = 0;
		}
	}
	return elem;
}

?1.1.5 检查队列是否为空

通过检查front指针是否为-1，可以确定队列是否为空。

int IsEmpty(Queue* queue) {
	return queue->front == -1;//空返回1，否则返回0
}

1.1.6 返回队列的长度?

int size(Queue* queue) {
	if (queue->rear < queue->front) {//队尾在队首前
		return queue->rear + MAX_SIZE - queue->front + 1;
	}
	else {
		return queue->rear - queue->front + 1;
	}
}

2.1队列的运用

1. 任务调度： 操作系统使用队列来管理待执行的任务。进程按照先进先出（FIFO）的顺序排队等待执行。

2. 广度优先搜索（BFS）： 在图算法中，广度优先搜索使用队列来按层次顺序遍历图中的节点。它常用于寻找最短路径、解决迷宫问题等。

3. 打印队列： 打印队列用于打印机管理，确保文档按照提交的顺序进行打印。

4. 缓冲区管理： 队列常被用作缓冲区，处理数据传输或异步通信过程中的临时存储。

5. 网络数据包处理： 网络路由器和交换机使用队列来存储和处理传入的数据包，确保按照先进先出的顺序进行处理。

6. 消息传递系统： 队列用于消息队列系统，允许系统中的不同组件之间进行异步通信。

7. 多线程编程： 在多线程环境中，队列可用于线程之间的安全数据传递。一个线程将数据放入队列，而另一个线程从队列中取出数据。

8. 模拟： 队列经常用于模拟系统，例如银行服务窗口模拟、汽车排队等。

9. 调度算法： 在调度算法中，队列可用于管理进程或任务的执行顺序。

10. 计算机网络中的流量控制： 队列用于调整网络流量，以防止过载和拥塞。

三、实验内容

问题描述

编写一个程序，实现链队列的各种基本运算， (MAXQSIZE=5)，并在此基础上设计一个主程序完成如下功能:

（1）初始化队列 q；

（2）判断队列 q 是否为空；

（3）依次进队列元素 1,12,-10；

（4）出队一个元素，并输出该元素；

（5）输出队列的长度（元素个数）；

（6）依次进队元素 13,-12,10；

（7）输出队列长度；

（8）输出出队序列

代码

#include<iostream>
using namespace std;
#define MAX_SIZE 5

typedef struct Queue {
	int array[MAX_SIZE];
	int front, rear;
};

void Initialize_Queue(Queue* queue) {
	queue->front = -1;
	queue->rear = -1;
}

void enqueue(Queue* queue,int elem) {
	if ((queue->rear == (MAX_SIZE - 1))&&(queue->front==0)) {//如果队列已满
		cout << "队列已满，不可再添加元素"<<endl;
		return;
	}
	if(queue->front==-1){//如果队列为空，更新front指针
		queue ->front = 0;
	}
	queue->rear++;
	queue->rear = queue->rear % MAX_SIZE;
	queue->array[queue->rear] = elem;//添加到队尾
}

int dequeue(Queue* queue) {
	int elem;
	if (queue->front == -1) {//如果队列为空
		cout << "队列为空" << endl;
		return -1;
	}
	elem=queue->array[queue->front];
	if (queue->front == queue->rear) {//如果队列中只有一个元素，则将队列清空
		Initialize_Queue(queue);
	}
	else {
		queue->front++;
		//循环队列的关键之处
		if (queue->front > (MAX_SIZE - 1)) {
			queue->front = 0;
		}
	}
	return elem;
}

int IsEmpty(Queue* queue) {
	return queue->front == -1;//空返回1，否则返回0
}

int size(Queue* queue) {
	if (queue->rear < queue->front) {//队尾在队首前
		return queue->rear + MAX_SIZE - queue->front + 1;
	}
	else {
		return queue->rear - queue->front + 1;
	}
}

int main() {
	Queue q;
	int data,a;
	Initialize_Queue(&q);//初始化队列q
	if (IsEmpty(&q) == 1) {
		cout << "队列为空" << endl;
	}
	else {
		cout << "队列不为空"<<endl;
	}
	for (int i = 0; i < 3; i++) {
		cin >> data;
		enqueue(&q, data);
	}
	a = dequeue(&q);//出队一个元素
	cout << "出队第一个元素："<<a << endl;
	int length = size(&q);
	cout <<"输出队列的长度："<< length << endl;
	for (int i = 0; i < 3; i++) {
		cin >> data;
		enqueue(&q, data);
	}
	length = size(&q);
	cout << "输出队列的长度：" << length << endl;
	if (q.rear < q.front) {//队尾在队首之前
		q.rear += MAX_SIZE;
	}
	for (int i = q.front; i <= q.rear; i++)
	{
		cout << q.array[i%MAX_SIZE]<<" ";
	}
	return 0;
}

截图

分析

由于采用的是循环队列，则由于将10入队时，队尾指针在队首指针前面，若采用非循环队列，则10入队时，队列已满