数据结构与算法 队列_数据结构中的排序算法

数据结构与算法 队列_数据结构中的排序算法一、什么是队列队列是一种特殊的线性表。队列元素的进出遵循“先进先出”原则:即只允许在前端(front)也就是队头进行删除操作,而只能在后端(rear)也就是队尾进行插入操作。如图所示:队列的最

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

一、什么是队列

队列是一种特殊的线性表

队列元素的进出遵循“先进先出”原则:即只允许在前端(front)也就是队头进行删除操作,而只能在后端(rear)也就是队尾进行插入操作。

数据结构与算法 队列_数据结构中的排序算法

如图所示:

  • 队列的最大长度为MaxSize,最大下标为MaxSize-1
  • 入队时队头下标不变而队尾下标改变,出队时则相反

二、模拟队列

1.简单的使用数组模拟队列:

/**
 * @Author:huang
 * @Date:2020-06-11 16:28
 * @Description:用数组模拟队列
 */
public class Queue {

    //队列最大长度
    private int maxSize;
    //存放数据的数组
    private Object[] arr;
    //头指针,指向队头的元素的前一个位置
    private int front;
    //尾指针,指向队尾的元素所在位置
    private int rear;

    //构造器
    public Queue(int size) {
        this.maxSize = size;
        this.arr = new Object[maxSize];
        this.front = -1;
        this.rear = -1;
    }

    /**
     * 判断队列是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        //当头指针和尾指针相等时队列为空
        return rear == front;
    }

    /**
     * 判断队列是否已满
     * @return
     */
    public boolean isFull(){
        //当尾指针等于maxSize-1时队列满
        return rear == maxSize - 1;
    }

    /**
     * 入队
     * @param item 入队元素
     * @return
     */
    public int addQueue(Object item) {
        //判断队列是否已满
        if (isFull()) {
            throw new RuntimeException("队列已满!");
        }
        //尾指针后移
        rear++;
        arr[rear] = item;
        return rear;
    }

    /**
     * 出队
     * @return
     */
    public Object quitQueue() {
        //判断队列是否为空
        if (isEmpty()) {
            throw new RuntimeException("队列为空!");
        }
        //头指针后移
        front++;
        return arr[front];
    }

}

2.解决“内存溢出”

咋一眼看上去没问题,但是实际上随着入队和出队操作,头指针和尾指针会不断后移,最后都到达maxSize-1的位置,此时即使实际上有空闲空间也无法往里面添加数据了。

如果要解决这个问题,可以这样改进:

当入队的时候进行一次判断,如果尾指针已经移动到maxSize-1的位置,并且头指针不在-1位置,也就是队列仍然还有空位,就触发一次数据迁移。

打个比方,如果队列长度为6,现在头指针在3,尾指针在5,触发数据迁移后下标3-5的数据移动到0-2去,然后把头指针移到0,尾指针移到2。

基于这个逻辑,只需要改变一下addQueue()入队方法即可:

/**
 * 入队
 * @param item 入队元素
 * @return
 */
public int addQueue(Object item) {
    //判断队列是已满还是只是尾指针到头
    if (isFull()) {
        //队列已满
        if (front == -1){
            throw new RuntimeException("队列已满!");
        }else {
            //尾指针到头,触发数据迁移
            for (int i = front; i < rear; i++) {
                arr[i - front] = arr[i];
            }
            //移动指针
            rear = rear - front;
            front = -1;
        }
    }
    //尾指针后移
    rear++;
    arr[rear] = item;
    return rear;
}

虽然问题解决了,但是频繁的移动数据会消耗性能,为此仍需要加以改进:

当尾指针到头以后,如果头指针前还有空闲空间,尾指针应当能移动到头指针之前的位置,也就是队头元素出队了,空出的空间将可以放在队尾被元素入队。

打个比方,就相当于原本的队列是一条直线,走到头就没了,现在要把头和尾连接到一起,让它变成循环队列

三、循环队列

数据结构与算法 队列_数据结构中的排序算法

对于循环队列,有两个问题需要考虑,一个是下标,另一个是队空和队满的判断条件

1.环形队列的下标计算

由于队头元素出队后空间即用于队尾元素入队,所以很可能出现长度5的队列,头指针在1,尾指针在4,这个时候在按照原来的思路用rear+1去入队就会下标越界,因此需要进行取余操作,也就是(rear+1)% maxSize,这样获取下标的问题就解决了。

2.环形队列的状态判断

由于队列变为环形,所以front=rear即可能是队满也可能是队空,针对这个问题有两种思路:

第一种是添加一个变量来记录队列中元素的数量,以区分front=rear时是队满还队空;

第二种是在rear后预留一个空位,通过计算判断rear+1后是否等于front以判断队满还是队空;

这里先用第二种来实现一下:

  • 队空的时候就是front=rear

  • 队满的时候就是rear+1=front,考虑到多次操作后指针可能跑了不止一圈,rear和front可能会大于maxSize,故也需要进行取余操作,所以正确的公式是

    (rear+1)%maxSize = front%maxSize

3.代码实现

/**
 * @Author:huang
 * @Date:2020-06-14 16:13
 * @Description:环形队列
 */
public class CricleQueue {

    //队列最大长度
    private int maxSize;
    //存放数据的数组
    private Object[] arr;
    //头指针,指向队头的元素的位置
    private int front;
    //尾指针,指向队尾的元素的位置
    private int rear;

    public CricleQueue(int maxSize) {
        //由于需要在尾指针后空一位作为队满队空的区分,所以实际大小是maxSize+1
        this.maxSize = maxSize + 1;
        this.arr = new Object[maxSize + 1];
        this.front = 0;
        this.rear = 0;
    }

    /**
     * 判断队列是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        //当头指针和尾指针相等时队列为空
        return rear == front;
    }

    /**
     * 判断队列是否已满
     * @return
     */
    public boolean isFull(){
        //头尾指针+1并取余时相等时队列满
        return (rear + 1) % maxSize == front;
    }

    /**
     * 入队
     * @param item
     */
    public void addQueue(Object item) {
        if (isFull()){
            throw new RuntimeException("队列已满!");
        }
        arr[rear] = item;
        rear = (rear + 1) % maxSize;
    }
    
	/**
     * 出队
     * @return
     */
    public Object quitQueue() {
        if (isEmpty()){
            throw new RuntimeException("队列为空!");
        }
        Object item = arr[front];
        front = (front + 1) % maxSize;
        return item;
    }

}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/170819.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • kali中间人攻击—-盗取账号和密码

    kali中间人攻击—-盗取账号和密码声明:本案例仅供个实验使用,并不作任何违法违纪等不正当,请遵守约定。1.原理解析在局域网内通信都是通过交换机及路由器连接外部网络的,对于局域网内大家都使用的一个协议为ARP协议,这个协议很奇特因为它是用来标定局域网内每台主机的MAC地址使用的,还有就是ARP协议也是用来规定网关的。  在我们下面要做的实验的过程中,kali系统会时刻向选定的机器发送“我是网关”,这样堵塞了真…

  • 【数字图像处理】C++读取、旋转和保存bmp图像文件编程实现

    【数字图像处理】C++读取、旋转和保存bmp图像文件编程实现通过我这些天用C++读写bmp图像的经历,摸索再摸索,终于对bmp文件的结构、操作有了一定的了解,下面就大概介绍bmp图片纯C++的读取、旋转和保存的实现过程。要用C++读取bmp图片文件,首先要弄清楚bmp格式图片文件的结构。可以参考这篇文章:http://blog.csdn.net/xiajun07061225/article/details/5813726有几点需要注意的是:在读

  • vue-router(路由)详细教程

    vue-router(路由)详细教程  由于Vue在开发时对路由支持的不足,于是官方补充了vue-router插件。vue的单页面应用是基于路由和组件的,路由用于设定访问路径,并将路径和组件映射起来。传统的页面应用,是用一些超链接来实现页面切换和跳转的。在vue-router单页面应用中,则是路径之间的切换,实际上就是组件的切换。路由就是SPA(单页应用)的路径管理器。再通俗的说,vue-router就是我们WebApp的链…

  • 大话数据结构PDF/word

    大话数据结构PDF/word《大话数据结构》PDF版本链接:https://pan.baidu.com/s/1nfaEZBBEi-3-mTX7A4qfbA提取码:30kyword版本链接:https://pan.baidu.com/s/18hpIqQYy4wiVUAoBabqZ-A提取码:e4ja

  • pycharm永久激活码2021【注册码】

    pycharm永久激活码2021【注册码】,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • C++读写锁介绍_数据库读写锁

    C++读写锁介绍_数据库读写锁一点睛先看看互斥锁,它只有两个状态,要么是加锁状态,要么是不加锁状态。假如现在一个线程a只是想读一个共享变量i,因为不确定是否会有线程去写它,所以我们还是要对它进行加锁。但是这时又有一个线程b试图去读共享变量i,发现被锁定了,那么b不得不等到a释放了锁后才能获得锁并读取i的值,但是两个读取操作即使是同时发生的,也并不会像写操作那样造成竞争,因为它们不修改变量的值。所以我们期望在多个线…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号