java数据结构与算法数组模拟队列示例详解

目录
  • 一、什么是队列
  • 二、用数组来模拟队列

一、什么是队列

  • 队列是一个有序列表,可以用数组或者链表来实现。
  • 遵循先入先出的原则,即:先存入队列的数据,要先取出。后存入的的数据,后取出。

看一张队列的模拟图,1,2,3表示同一个队列Queue。在队列中有2个指针,front表示队首,rear表示队尾。

  • 图1中表示队列里还没有数据,所以front跟rear初始化都是-1。
  • 当图2中有数据进行存入的时候,front没变,而rear则随着数据的增多而改变。存入了4个数据,于是rear=3。
  • 再看图3,front变成了2,rear没有变化,因为前面的2个数据被依次先取出,所以队首就变成了2。

这就是队列的“先进先出”了。

二、用数组来模拟队列

思路也比较简单,因为队列的输出、输入是分别从前后端来处理,因此需要两个变量front以及rear分别记录队列的前后端下标。

front会随着数据输出而改变,而rear则是随着数据的输入而改变。

package sparsearray;
import java.util.Scanner;
public class MyArrayQueue {
    public static void main(String[] args) {
        // 创建一个队列
        ArrayQueue arrayQueue = new ArrayQueue(3);
        char key = ' '; //接受用户输入
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        // 输出一个菜单
        while (loop) {
            System.out.println("s(show): 显示队列");
            System.out.println("e(exit): 退出程序");
            System.out.println("a(add): 添加数据到队列");
            System.out.println("g(get): 从队列取出数据");
            System.out.println("h(head): 显示队首的数据");
            key = scanner.next().charAt(0); // 接收一个字符
            switch (key) {
                case 's':
                    arrayQueue.showQueue();
                    break;
                case 'a':
                    System.out.println("请要添加的数");
                    int value = scanner.nextInt();
                    arrayQueue.addQueue(value);
                    break;
                case 'g':
                    try {
                        int res = arrayQueue.getQueue();
                        System.out.printf("取出的数据是:%d", res);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h':
                    try {
                        int headValue = arrayQueue.showHeadQueue();
                        System.out.printf("队首数据是:%d", headValue);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
            }
        }
        System.out.println("退出程序");
    }
}
// 把队列抽象成一个类,ArrayQueue
class ArrayQueue {
    //表示数组最大容量
    private int maxSize;
    // 队列头
    private int front;
    // 队列尾
    private int rear;
    // 用于存放数据的数组
    private int[] arr;
    // 构造器
    public ArrayQueue(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = -1; // 指向队首的前一个位置
        rear = -1; // 指向队列尾部,包括队列最后的这个数据
    }
    // 判断队列是否已经存满
    public boolean isFull() {
        return rear == maxSize - 1; // 注意这里的 maxSize-1 为什么要减1
    }
    // 判断队列是否为空
    public boolean isEmpty() {
        return rear == front;
    }
    // 添加数据到队列
    public void addQueue(int num) {
        // 判断队列是否满了
        if (isFull()) {
            System.out.println("队列已满,不可加入数据");
            return;
        }
        rear++; // 让rear后移
        arr[rear] = num;
    }
    // 拿出队列数据
    public int getQueue() {
        // 判断队列是否空
        if (isEmpty()) {
            // 抛出异常
            throw new RuntimeException("队列为空,不可取数据");
        }
        front++; // front后移
        return arr[front];
    }
    // 显示队列所有数据
    public void showQueue() {
        // 遍历
        if (isEmpty()) {
            System.out.println("队列为空");
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("arr[%d]=%d\n", i, arr[i]);
        }
    }
    // 显示队里的队首数据
    public int showHeadQueue() {
        if (isEmpty()) {
            // 抛出异常
            throw new RuntimeException("队列为空,不可取数据");
        }
        return arr[front + 1]; // 注意这里为甚么要+1,因为指向队首的前一个位置
    }
}

可以用代码分别的进行各项操作,看起来似乎没问题。

但是,实际是有问题。

这里创建的数组使用一次就不能接着用了,比如把数据取完后,再往里加数据就不行了。

所以要对其进行优化,使用算法,将其改成一个环形队列,以上就是java数据结构与算法数组模拟队列示例的详解内容,更多关于java数据结构算法数组模拟队列的资料请关注我们其它相关文章!

(0)

相关推荐

  • java数据结构与算法之双向循环队列的数组实现方法

    本文实例讲述了java数据结构与算法之双向循环队列的数组实现方法.分享给大家供大家参考,具体如下: 需要说明的是此算法我并没有测试过,这里给出的相当于伪代码的算法思想,所以只能用来作为参考! package source; public class Deque { private int maxSize; private int left; private int right; private int nItems; private long[] myDeque; //constructor p

  • Java数据结构与算法之稀疏数组与队列深入理解

    目录 一.数据结构和算法简介 二.稀疏数组 稀疏数组的应用实例 二维数组与稀疏数组的转换 二维数组 转 稀疏数组的思路 稀疏数组 转 原始的二维数组的思路 三.队列 数组模拟队列 代码优化:数组模拟环形队列 之前学完了Java SE的知识,掌握了面向对象的编程思想,但对集合.多线程.反射.流的使用等内容理解的还不是很深入,打算再学习数据结构与算法的同时,在空闲的时间里去图书馆看<Java核心技术 卷 I>这本书,很多大佬对这本书很推崇,之前在图书馆也看过其他Java的书籍,经过对比,这本书确实

  • Java数据结构与算法之循环队列的实现

    目录 概述 循环队列 循环队列实现 改变队列大小 enqueue 方法 dequeue 方法 main 完整代码  概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 循环队列 循环队列 (Circular Queue) 是一种特殊的队列. 循环队列解决了队列出队时需要将所有数据前移一位 (复杂度为 O(n)) 的问题. 循环队列的底层依然是数组, 不过增加了指向头和尾的指针. 循环队列实现 判断队列是否为空: 当头指针 Q.front == 尾指针 Q.rear,

  • 带你了解Java数据结构和算法之队列

    目录 1.队列的基本概念 2.Java模拟单向队列实现 3.双端队列 4.优先级队列 5.总结 1.队列的基本概念 队列(queue)是一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作,和栈一样,队列是一种操作受限制的线性表.进行插入操作的端称为队尾,进行删除操作的端称为队头.队列中没有元素时,称为空队列. 队列的数据元素又称为队列元素.在队列中插入一个队列元素称为入队,从队列中删除一个队列元素称为出队.因为队列只允许在一端插入,在

  • Java 数据结构与算法系列精讲之队列

    目录 概述 队列 队列实现 enqueue方法 dequeue方法 main 完整代码 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 队列 队列 (Queue) 遵循先进先出的原则 (First-In-First-Out). 举个例子, 早上我们排队买早餐的时候, 先排的人先买后排的人后买. 队列只能在队首进行删除操作, 在队尾进行插入操作. 队列实现 enqueue 方法 // 入队 public void enqueue(E element) { array

  • java数据结构与算法数组模拟队列示例详解

    目录 一.什么是队列 二.用数组来模拟队列 一.什么是队列 队列是一个有序列表,可以用数组或者链表来实现. 遵循先入先出的原则,即:先存入队列的数据,要先取出.后存入的的数据,后取出. 看一张队列的模拟图,1,2,3表示同一个队列Queue.在队列中有2个指针,front表示队首,rear表示队尾. 图1中表示队列里还没有数据,所以front跟rear初始化都是-1. 当图2中有数据进行存入的时候,front没变,而rear则随着数据的增多而改变.存入了4个数据,于是rear=3. 再看图3,f

  • java数据结构排序算法之树形选择排序详解

    本文实例讲述了java数据结构排序算法之树形选择排序.分享给大家供大家参考,具体如下: 这里我们就来说说选择类排序之一的排序:树形选择排序 在简单选择排序中,每次的比较都没有用到上次比较的结果,所以比较操作的时间复杂度是O(N^2),想要降低比较的次数,则需要把比较过程中的大小关系保存下来.树形选择排序是对简单选择排序的改进. 树形选择排序:又称锦标赛排序(Tournament Sort),是一种按照锦标赛的思想进行选择排序的方法.首先对n个记录的关键字进行两两比较,然后在n/2个较小者之间再进

  • Java数据结构与算法之栈(Stack)实现详解

    本篇是java数据结构与算法的第2篇,从本篇开始我们将来了解栈的设计与实现,以下是本篇的相关知识点: 栈的抽象数据类型顺序栈的设计与实现链式栈的设计与实现栈的应用 栈的抽象数据类型   栈是一种用于存储数据的简单数据结构,有点类似链表或者顺序表(统称线性表),栈与线性表的最大区别是数据的存取的操作,我们可以这样认为栈(Stack)是一种特殊的线性表,其插入和删除操作只允许在线性表的一端进行,一般而言,把允许操作的一端称为栈顶(Top),不可操作的一端称为栈底(Bottom),同时把插入元素的操作

  • java数据结构与算法之简单选择排序详解

    本文实例讲述了java数据结构与算法之简单选择排序.分享给大家供大家参考,具体如下: 在前面的文章中已经讲述了交换类的排序算法,这节中开始说说选择类的排序算法了,首先来看一下选择排序的算法思想: 选择排序的基本算法思想: 每一趟在 n-i+1 (i=1,2,3,--,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录. 简单选择排序: 设所排序序列的记录个数为n.i取1,2,-,n-1,从所有n-i+1个记录(Ri,Ri+1,-,Rn)中找出排序码最小的记录,与第i个记录交换.执行n-

  • Java 数据结构算法Collection接口迭代器示例详解

    目录 Java合集框架 Collection接口 迭代器 Java合集框架 数据结构是以某种形式将数据组织在一起的合集(collection).数据结构不仅存储数据,还支持访问和处理数据的操作 在面向对象的思想里,一种数据结构也被认为是一个容器(container)或者容器对象(container object),它是一个能存储其他对象的对象,这里的其他对象常被称为数据或者元素 定义一种数据结构从实质上讲就是定义一个类.数据结构类应该使用数据域存储数据,并提供方法支持查找.插入和删除等操作 Ja

  • Go Java算法之累加数示例详解

    目录 累加数 方法一:穷举法(java) 方法二:深度优先遍历(go) 累加数 累加数 是一个字符串,组成它的数字可以形成累加序列. 一个有效的 累加序列 必须 至少 包含 3 个数.除了最开始的两个数以外,序列中的每个后续数字必须是它之前两个数字之和. 给你一个只包含数字 '0'-'9' 的字符串,编写一个算法来判断给定输入是否是 累加数 .如果是,返回 true :否则,返回 false . 说明:累加序列里的数,除数字 0 之外,不会 以 0 开头,所以不会出现 1, 2, 03 或者 1

  • Go Java算法之交错字符串示例详解

    目录 交错字符串 方法一:动态规划(Java) 方法一:动态规划(GO) 交错字符串 给定三个字符串 s1.s2.s3,请你帮忙验证 s3 是否是由 s1 和 s2 交错 组成的. 两个字符串 s 和 t 交错 的定义与过程如下,其中每个字符串都会被分割成若干 非空 子字符串: s = s1 + s2 + ... + sn t = t1 + t2 + ... + tm |n - m| <= 1 交错 是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 +

  • Go Java算法之同构字符串示例详解

    目录 同构字符串 方法一:哈希表(Java) 方法一:哈希表(Go) 同构字符串 给定两个字符串 s 和 t ,判断它们是否是同构的. 如果 s 中的字符可以按某种映射关系替换得到 t ,那么这两个字符串是同构的. 每个出现的字符都应当映射到另一个字符,同时不改变字符的顺序.不同字符不能映射到同一个字符上,相同字符只能映射到同一个字符上,字符可以映射到自己本身. 示例 1: 输入:s = "egg", t = "add" 输出:true 示例 2: 输入:s = &

  • Go Java算法猜数字游戏示例详解

    目录 猜数字游戏 方法一:遍历(Java) 方法一:遍历(Go) 猜数字游戏 你在和朋友一起玩 猜数字(Bulls and Cows)游戏,该游戏规则如下: 写出一个秘密数字,并请朋友猜这个数字是多少.朋友每猜测一次,你就会给他一个包含下述信息的提示: 猜测数字中有多少位属于数字和确切位置都猜对了(称为 "Bulls",公牛), 有多少位属于数字猜对了但是位置不对(称为 "Cows",奶牛).也就是说,这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字. 给

随机推荐