好用的ppt模板网站,电子商务网站建设的步骤,深圳做网页的网站,网站推广免费一、前言
队列是一种重要的数据结构#xff0c;它按照“先入先出”#xff08;FIFO#xff09;的原则管理数据。本文将介绍队列的概念、应用场景#xff0c;以及如何使用数组实现普通队列和环形队列。 二、内容
2.1 概述
#xff08;1#xff09;什么是队列#xff1…一、前言
队列是一种重要的数据结构它按照“先入先出”FIFO的原则管理数据。本文将介绍队列的概念、应用场景以及如何使用数组实现普通队列和环形队列。 二、内容
2.1 概述
1什么是队列
队列Queue是一种常见的数据结构它是一个线性数据结构按照先入先出FIFOFirst-In-First-Out的原则来管理数据。 注意先入先出的原则就意味着最早进入队列的元素将最先被取出而最后进入队列的元素将最后被取出类似于排队等候服务的行为。 队列可以使用数组或链表来实现具体实现方式因应用需求而异。
队列支持两种主要的操作即入队Enqueue和出队Dequeue。
入队将元素添加到队列的尾部。出队从队列的头部取出元素并删除它。
2应用场景
队列的应用场景有很多比如
任务调度操作系统使用队列来管理待执行的任务或进程确保按照进入队列的顺序分配处理时间。数据缓冲队列用于数据传输和处理中特别是在异步通信或生产者-消费者模式中可以缓冲待处理的数据。广度优先搜索在图论和搜索算法中队列用于实现广度优先搜索以逐层遍历图结构。打印任务队列打印机队列用于管理待打印的文档确保按照顺序打印。网页请求队列Web服务器可以使用队列来处理收到的请求以便有序响应客户端请求。排队系统在银行、餐馆、医院等场所队列被用来管理等待服务的客户确保服务按照先来先服务的原则。......
队列在计算机科学和实际应用中非常有用因为它们提供了一种有效的方法来管理和调度数据或任务以确保按照特定的顺序进行处理。 2.2 数组模拟队列
下面我们用数组来模拟一个简单的队列数据结构。
1队列类定义
首先给出类的定义
class ArrayQueue {private int maxSize;private int front;private int rear;private int[] data;ArrayQueue(int queueMaxSize) {maxSize queueMaxSize; // 队列的最大容量data new int[maxSize]; // 存放队列的数据front -1; // 指向队列头的前一个位置rear -1; // 直接指向队列尾部}// ... 方法定义
}在这里ArrayQueue 是一个队列类使用数组作为内部数据存储。它包括最大容量maxSize、队列头front、队列尾rear和一个整数数组data来存放队列的数据。
构造函数 ArrayQueue 接受一个整数参数 queueMaxSize表示队列的最大容量。初始化时队列的头front和尾都rear被置为-1表示队列为空。
需要注意这里的定义在这里front 变量指的是指向队列首元素的前一个位置而 rear 变量则指向队列的尾部元素即最后一个元素。
因此初始队列的结构图如下 2isEmpty
public boolean isEmpty() {return rear front;
}isEmpty() 方法用于检查队列是否为空。如果队列头和队列尾相等表示队列中没有数据返回 true否则返回 false。
3isFull
public boolean isFull() {return rear maxSize - 1;
}isFull() 方法用于检查队列是否已满。如果队列尾等于最大容量减1表示队列已满返回 true否则返回 false。
4enQueue
// 入队操作添加数据到队尾
public void enQueue(int num) {if(isFull()) {System.out.println(队列已满无法入队);return;}rear;data[rear] num;
}enQueue 方法用于将数据添加到队列的尾部。首先它会检查队列是否已满如果是将输出一条错误消息并不执行入队操作。如果队列未满将 rear 后移然后将数据存入队列尾部。
再次强调一下这里的 rear 变量用于指向队列的最后一个数据即队列的尾部。 5deQueue
// 出队操作取出队头数据
public int deQueue() {if(isEmpty()) {throw new RuntimeException(队列为空无法出队); }front;return data[front];
}deQueue 方法用于取出队列头部的数据。首先它会检查队列是否为空如果是将抛出一个运行时异常。如果队列不为空将 front 后移然后返回队头的数据。
再次强调一下这里的 front 变量指向的是队列头数据的前一个位置。 6headQueue
// 查看队头数据注意不是取出数据
public int headQueue() {if(isEmpty()) {throw new RuntimeException(队列为空没有数据);}return data[front1];
}headQueue 方法用于获取队列头部的数据但不会将其出队。它会检查队列是否为空如果是将抛出一个运行时异常。如果队列不为空将返回队头的数据。
7showQueue
// 打印队列
public void showQueue() {if(isEmpty()) {System.out.println(队列为空没有数据);return;}// 简单的遍历队列for(int i 0; i data.length; i) {System.out.printf(data[%d] %d\n, i, data[i]);}
}showQueue 方法用于简单地打印队列的所有元素。如果队列为空将输出一条消息表示队列为空。否则它会简单地遍历队列打印每个数据元素的索引和值。 2.3 数组模拟环形队列
1存在的问题
我们再来思考一个问题虽然上述的队列类实现了一个简单的队列数据结构但仍然存在弊端。那就是数组使用一次后不能复用。
什么意思
具体的我们可以发现每当队列入队一个数据rear 变量就会往后移一位。每当有元素出队front 变量也会往后移一位。但是一旦 rear 变量到达队列的尾部如果队列头部仍有空余的空间就像这样 那么此时根据 isFull() 方法的判断下该队列是满的。因此无法再入队。
因此我们说对于之前的队列简单实现来说一旦队列中的数据元素被取出对应的数组位置就不能再次使用。数据从头部添加从尾部取出。一旦数组被填满我们无法再添加新的数据即使队列的前面已经有一些位置被释放出来。这就会导致内存资源浪费。
为了解决这个问题我们考虑使用环形队列来优化。
那什么是环形队列
事实上环形队列是一种更高效的队列实现方式它允许队列在达到最大容量后继续添加元素以覆盖掉队列头部已经被取出的数据实现数据的循环复用。
我们通过取模运算 % 来实现环形队列。
2思路分析
当我们考虑了队列内部数据存储资源的复用后我们就需要对 front 和 rear 变量的含义进行一个的调整当然不调整也行看个人习惯。
具体如下
front 变量 表示指向队列的第一个元素即首元素。data[front] 是队列的第一个元素。front的初始值为 0。rear 变量 表示指向队列最后一个元素的下一个位置。这是为了表示队列中哪些位置是可用的以便继续添加新的元素。rear 的初始值同样为 0。
当我们这样约定好了后就可以开始着手编写代码得到一个环形队列。
此时判断队列已满或空时逻辑需要略微调整。
判断环形队列空时条件为(rear front)。因为当 rear 指针等于 front 指针时表示队列没有有效的元素即队列为空。
判断环形队列满时条件为(rear 1) % maxSize front
这该怎么理解
事实上在含义调整后环形队列中的 rear 变量指向的位置实际上就是预留给下次入队的数据存放的位置。
当有一个新的数据入队时rear 指向的位置就可以存储本次入队的数据的值然后rear 就会加一并取余 maxSize 用于寻找下一个可以存储入队数据的位置。
因此当(rear 1) % maxSize 的值刚好等于 front那么证明该环形队列已经满了没有地方可以存储下一次入队的值。 举一个例子假设 maxSize 为 3初始时 front 和 rear 都是0 队列为空front 0, rear 0插入一个元素front 0, rear 1插入第二个元素front 0, rear 2插入第三个元素front 0, rear 0此时队列满因为 (rear 1) % maxSize 等于 front取出第一个元素front 1, rear 0此时队列有效元素个数为 2因为 (03-1) % 3 2 示意图如下 3优化后的队列类
优化后的代码实现如下
class CircleArrayQueue {private int maxSize;private int front; // 初始值为 0指向队头数据即首元素private int rear; // 初始值为 0指向队尾数据的下一个位置private int[] data;ArrayQueue(int queueMaxSize) {maxSize queueMaxSize; data new int[maxSize];}// 判断队列是否为空public boolean isEmpty() {return rear front;}// 判断队列是否满public boolean isFull() {return (rear 1) % maxSize front;}// 入队添加数据到队尾public void enQueue(int num) {if(isFull()) {System.out.println(队列已满无法入队);return;}data[rear] num;rear (rear 1) % maxSize;}// 出队取出队头数据public int deQueue() {if(isEmpty()) {throw new RuntimeException(队列为空无法出队); }int value data[front];front (front 1) % maxSize;return value;}// 显示队列的头数据不是取出数据public int headQueue() {if(isEmpty()) {throw new RuntimeException(队列为空没有数据);}return data[front];}// 返回环形队列当前的元素个数public int size() {return (rear maxSize - front) % maxSize;}// 打印队列public void showQueue() {if(isEmpty()) {System.out.println(队列为空没有数据);return;}// 遍历思路从 data[front] 遍历到 data[front size]for(int i front; i front size(); i) {System.out.printf(data[%d] %d\n, i%maxSize, data[i%maxSize]);}}
}三、总结
本文详细介绍了队列数据结构的概念和应用包括普通队列和环形队列的实现。队列是一种有序的数据结构它在计算机科学中被广泛应用用于管理数据和任务的顺序执行。普通队列使用数组实现但存在内存资源浪费的问题。为了解决这个问题我们引入了环形队列的概念它允许队列数据的循环复用更加高效地利用内存。
