当前位置： 首页 > news >正文

队列

news 来源：原创 2024/5/18 21:58:09

队列，进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。
队列特点：先进先出

队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明

队列分为：
①、单向队列（Queue）：只能在一端插入数据，另一端删除数据。
②、双向队列（Deque）：每一端都可以进行插入数据和删除数据操作。
③、优先级队列（Priority）：优先级队列是比栈和队列更专用的数据结构，在优先级队列中，数据项按照关键字进行排序，关键字最小（或者最大）的数据项往往在队列的最前面，而数据项在插入的时候都会插入到合适的位置以确保队列的有序。

 

在实现之前，我们先看下面几个问题：
①、与栈不同的是，队列中的数据不总是从数组的0下标开始的，移除一些队头front的数据后，队
头指针会指向一个较高的下标位置，如下图：

在这里插入图片描述

②、我们再设计时，队列中新增一个数据时，队尾的指针rear 会向上移动，也就是向下标大的方
向。移除数据项时，队头指针 front 向上移动。
 

总结：因为队列的是输出、输入是分别从前后端来处理，因此需要两个变量front（队头指针）、rear（队尾指针）分别记录队列前后端的下标，front会随着数据输出而改变，而rear则是随着数据输入而改变。maxSize是队列的最大容量。

1.数组实现简单的单向队列（非循环）：

当我们将数据存入队列时称为addQueue，addQueue的处理需要有两个步骤。

1）将尾指针往后移：rear+1（因为是顺序存储结构，地址是连续的，所以这两个指针可以直接用int型，所以直接+1），当front==rear表示空队列。

2）若尾指针rear小于队列的最大下标maxSize-1，则将数据存入rear所指的数组元素中，否则无法存入数据。rear == maxSize-1表示队满。

注意，rear是指向队列最后元素（包含），而front指向队列最前元素（不包含）

public class Queue {
    // 用数组模拟一个单向肺循环队列
    private int maxSize; // 数组最大容量
    private int front; // 队头指针
    private int rear; // 队尾
    private int[] queue; // 模拟队列

    // 创建队列的构造器
    public Queue(int maxSize) {
        this.maxSize = maxSize;
        queue = new int[maxSize]; // 初始化，不new无法初始化
        front = rear = -1; // 对空，指向队列头部，而不是队列第一个元素
    }

     // 判断队列是否满
    public boolean isFull(){
        return rear == maxSize - 1;
    }

    // 判断队列是否空
    public boolean isEmpty(){
        return front == rear; // 不止为-1时，在中间取完了也有可能
    }

    // 添加数据到队列
    public void addQueue(int n){
        // 首先判断队列是否满
        if(isFull()){
            System.out.println("队列已满。不能再添加元素！");
        }else{
            rear++; // 尾指针后移动
            queue[rear] = n; // 元素保存进去
        }
    }

    // 从队列删除数据，并获取
    public int deleteQueue(){ // 只能从表头删
        int result;
        if(isEmpty()){
            // 抛出异常
            throw new RuntimeException("队列为空，不能取数据！"); // 立马终止，所以不用再写return
        }
        result = queue[front+1];
        front++;
        return result;
    }

    // 显示队列所有数据
    public void show(){
        // 遍历
        if(isEmpty()) System.out.println("队列为空");
        for (int i = front + 1; i <= rear; i++) {
            System.out.printf("queue[%d]=%d\n",i,queue[i]); // 格式化写法
        }
    }

    // 显示队列的头数据，注意不是取出数据
    public int headQueue(){
        if(isEmpty()) throw new NullPointerException("队列为空，不存在头数据");
        return queue[front + 1];
    }
}
public static void main(String[] args) {
    Queue queue = new Queue(15); // 构造方法创建最大容量队列

    // 判断是否为空
    System.out.println(queue.isEmpty());
    // 判断是否满
    System.out.println(queue.isFull());
    // 添加元素
    queue.addQueue(3);
    queue.addQueue(3);
    queue.addQueue(5);
    queue.addQueue(4);
    // 显示队列
    queue.show();
    System.out.println("---------");
    // 从队头移除两个数据
    queue.deleteQueue();
    queue.deleteQueue();
    // 再次显示队列
    queue.show();
    // 显示队头数据
    System.out.println(queue.headQueue());
}

运行截图：

循环队列

③、如果向第②步这样移动指针，相信队尾指针很快就移动到数据的最末端了，这时候可能移除过
数据，那么队头会有空着的位置，然后新来了一个数据项，由于队尾不能再向上移动了，那该怎么办
呢？如下图：

在这里插入图片描述

为了避免队列不满却不能插入新的数据，我们可以让队尾指针绕回到数组开始的位置，这也称为“循环队列”。

核心使用取模%。

思路分析：

1.front指针含义做一个调整：front指向队列的第一个元素（而不是前一个）

2.rear指针含义做一个调整：rear指向队列最后一个元素的后一个位置。

调整原因：空出一个空间（最后一个元素和第一个元素之间空一个位置）作为约定。

循环队列为什么要空一个位置呢？

这个是根据需要来用的
循环队列中，由于入队时尾指针向前追赶头指针；z出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。因此，无法通过条件front==rear来判别队列是"空"还是"满"。
解决这个问题的方法至少有三种：
①另设一布尔变量以区别队列的空和满；
②少用一个元素的空间。约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；
③使用一个计数器记录队列中元素的总数（即队列长度）。

当队列满时：（rear + 1) % maxSize == front

当队列空时：rear == front

初始值：front = rear = 0

此时队列中有效的数据个数为：（rear + maxSize - front）% maxSize

添加队尾元素的时候：rear后移，为保证不越界，rear = (rear + 1) % maxSize

删除队头元素的时候：front后移，为保证不越界，front = (front + 1) % maxSize

遍历有效数据的时候：从front开始，因为有效数据个数为（rear + maxSize - front）% maxSize，所以到front + (（rear + maxSize - front）% maxSize)为止。

代码：

package 数据结构;

public class CircularQueue {
    // 用数组模拟一个循环能循环队列
    private int maxSize; // 数组最大容量
    private int front; // 队头指针，指向第一个元素
    private int rear; // 队尾，指向队尾元素的下一个位置
    // 默认maxSize留空一位
    private int[] queue; // 模拟队列

    // 创建队列的构造器
    public CircularQueue(int maxSize) {
        this.maxSize = maxSize;
        queue = new int[maxSize]; // 初始化，不new无法初始化
        front = rear = 0; // 队空
    }

     // 判断队列是否满
    public boolean isFull(){
        return (rear + 1) % maxSize == front;
    }

    // 判断队列是否空
    public boolean isEmpty(){
        return front == rear; // 不止为0时，在中间取完了也有可能
    }

    // 添加数据到队列
    public void addQueue(int n){
        // 首先判断队列是否满
        if(isFull()){
            System.out.println("队列已满。不能再添加元素！");
        }else{
            queue[rear] = n; // 元素保存进去
            // 尾指针向后移动，因为循环，这里必须考虑取模，否则可能越界
            rear = (rear + 1) % maxSize;
        }
    }

    // 从队列删除数据，并获取
    public int deleteQueue(){ // 只能从表头删
        int result;
        if(isEmpty()){
            // 抛出异常
            throw new RuntimeException("队列为空，不能取数据！"); // 立马终止，所以不用再写return
        }
        result = queue[front];
        // 也要考虑循环因素
        front = (front + 1) % maxSize;
        return result;
    }

    // 求出当前有效数据个数
    public int size(){
        return (rear + maxSize - front) % maxSize;
    }
    // 显示队列所有数据
    public void show(){
        // 遍历
        if(isEmpty()) System.out.println("队列为空");
        // 思路：从front遍历
        // 由于有效个数为(front+maxSize-rear)%maxSize
        for (int i = front; i <= front + size(); i++) {
            System.out.printf("queue[%d]=%d\n",i % maxSize,queue[i % maxSize]); // 格式化写法
        }
    }

    // 显示队列的头数据，注意不是取出数据
    public int headQueue(){
        if(isEmpty()) throw new NullPointerException("队列为空，不存在头数据");
        return queue[front];
    }
}

 

双端队列

双端队列就是一个两端都是结尾或者开头的队列， 队列的每一端都可以进行插入数据项和移除数据项，这些方法可以叫做：insertRight()、insertLeft()、removeLeft()、removeRight()
1）如果严格禁止调用insertLeft()和removeLeft()（或禁用右端操作），那么双端队列的功能就和前面讲的栈功能一样。
2）如果严格禁止调用insertLeft()和removeRight(或相反的另一对方法)，那么双端队列的功能就和单向队列一样了。

 

参考博客：

https://blog.csdn.net/qq_39513430/article/details/104949994?utm_medium=distribute.pc_relevant.none-task-blog-baidujs_baidulandingword-0&spm=1001.2101.3001.4242

https://blog.csdn.net/yrwan95/article/details/82464118?utm_medium=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.baidujs&dist_request_id=&depth_1-utm_source=distribute.pc_relevant_t0.none-task-blog-BlogCommendFromMachineLearnPai2-1.baidujs

https://blog.csdn.net/weixin_41845059/article/details/107222179

https://blog.csdn.net/changshuchao/article/details/87861542

相关文章：

  • 单链表LinkedList的增删改查
  • 双向链表和环形链表（单向和双向）约瑟夫环实例
  • IO流概述+字节输出流
  • 字节输入流
  • 字符流（字符输入流和字符输出流）
  • IO异常的处理
  • 栈Stack（数组模拟、单链表模拟）
  • 属性集合Properties
  • 缓冲流
  • 转换流InputStreamReader类和OutputStreamWriter（字符编码和字符集）
  • 序列化与反序列化和transient瞬态关键字
  • 打印流
  • 前缀（波兰）、中缀、后缀（逆波兰）表达式
  • 递归（回溯之迷宫问题+八皇后）
  • 算法题-Java实现：从 1 到 n 整数中 1 出现的次数（时间复杂度O(logn)）
  • 【编码】-360实习笔试编程题（二）-2016.03.29
  • 【每日笔记】【Go学习笔记】2019-01-10 codis proxy处理流程
  • 【刷算法】从上往下打印二叉树
  • 0基础学习移动端适配
  • 78. Subsets
  • chrome扩展demo1-小时钟
  • CSS3 聊天气泡框以及 inherit、currentColor 关键字
  • egg(89)--egg之redis的发布和订阅
  • JavaScript 基础知识 - 入门篇(一)
  • JavaScript设计模式系列一：工厂模式
  • js中forEach回调同异步问题
  • October CMS - 快速入门 9 Images And Galleries
  • Promise面试题2实现异步串行执行
  • SpiderData 2019年2月16日 DApp数据排行榜
  • vue学习系列（二）vue-cli
  • 从零到一：用Phaser.js写意地开发小游戏（Chapter 3 - 加载游戏资源）
  • 动态规划入门（以爬楼梯为例）
  • 回流、重绘及其优化
  • 基于 Babel 的 npm 包最小化设置
  • 来，膜拜下android roadmap，强大的执行力
  • 吐槽Javascript系列二：数组中的splice和slice方法
  • 我这样减少了26.5M Java内存！
  • 宾利慕尚创始人典藏版国内首秀，2025年前实现全系车型电动化 | 2019上海车展 ...
  • # Maven错误Error executing Maven
  • #laravel 通过手动安装依赖PHPExcel#
  • #NOIP 2014# day.2 T2 寻找道路
  • （Matalb时序预测）WOA-BP鲸鱼算法优化BP神经网络的多维时序回归预测
  • （附源码）springboot教学评价 毕业设计 641310
  • （附源码）springboot太原学院贫困生申请管理系统 毕业设计 101517
  • （附源码）springboot猪场管理系统 毕业设计 160901
  • (汇总)os模块以及shutil模块对文件的操作
  • (切换多语言)vantUI+vue-i18n进行国际化配置及新增没有的语言包
  • （转）ObjectiveC 深浅拷贝学习
  • (转)关于多人操作数据的处理策略
  • （转）树状数组
  • ./mysql.server: 没有那个文件或目录_Linux下安装MySQL出现“ls: /var/lib/mysql/*.pid: 没有那个文件或目录”...
  • .NET 8 中引入新的 IHostedLifecycleService 接口 实现定时任务
  • .net CHARTING图表控件下载地址
  • .NET Framework 4.6.2改进了WPF和安全性
  • .net 提取注释生成API文档 帮助文档