栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

Java数据结构之队列(数组上)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Java数据结构之队列(数组上)

        我们去银行办理业务时,经常会用到排号机,每去一个人取一个号码,银行柜台办理一个业务叫一个号,其中我们排队的过程就是用到了队列。(今天先使用数组来模拟队列,后面再使用链表来实现)

队列具有以下特点

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

        我们可以先把队列看成排队的行为,所谓的入队其实跟现实中排队是一样的操作,就是在队尾追加一个元素,可参考下图(tail代表队尾)

        入队的操作很简单,但是出队呢?由于队列是遵循先进先出原则的,所以是从队头出队,也就是下标为0的位置,这也就意味着队列中多有的元素都要向前移动,以保证队列的队头,也就是下标为0的位置不为空。在现实中确实是这样排队的,可是在程序中,这样属实有点耗费性能。如下图所示

 

        我们可以这样想,为什么出列时一定要全部移动呢,如果不去限制队列的元素必须存储在数组的前个单元这一条件,拿做做核酸举例。我们如果让核酸医生一步步向队伍移动,而不是队伍整体向核酸医生移动,在现实中这样做一定会被贴上脑子缺根筋的标签,但在程序中,出队的性能会大大增加,也就是说,队头不需要一定在下标为0的位置。如下图所示

 

         为了避免当只有一个元素时,队头和队尾重合,因此引入两个变量,分别是head和tail,head代表队列头的前一个位置,tail代表队尾的位置(位置指的是下标),这样当head等于tail时,队列中不是还剩下一个元素而是空队列。 假设是长度为5的数组,初始状态,空队列如图所示。

         head和tail均为-1, 然后入队 al a2 a3 a4, head依然为-1(因为是入队操作,只要队尾动就ok),而 tail 则变为3 ,

         出队a1 a2,head变为0, tail不变。如下图所示

        出队a3 a4,head变为3,tail不变,head=tail时为空(每出队一次head向前移动一次),如下图所示

 经过上面的分析,我们知道,想要构成一个队列需要以下几个变量:

  1. 队列的最大长度:MaxSize
  2. 队列头:head
  3. 队列尾:tail
  4. 用来存放数据的数组

其中,maxsize的值是固定,head会随着出队而变化,tail会随着入队而变化。

入队操作其实就是tail+1,出队操作就算head+1;当head=tail时,该队列为空队列,当tail=maxsize-1时,该队列为满队列,无法继续添加。

代码如下:

public class ArrayQueueDemo {
    public static void main(String[] args) {
        //测试队列
        //创建一个队列
        ArrayQueue arrayQueue = new ArrayQueue(5);
        char key = ' ';//接受用户输入
        Scanner sc = new Scanner(System.in);
        boolean flag = true;
        while (flag) {
            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 = sc.next().charAt(0);
            switch (key) {
                case 's'://显示队列
                    arrayQueue.showQueue();
                    break;
                case 'e'://退出程序
                    sc.close();
                    flag = false;
                    break;
                case 'a'://添加数据到队列
                    System.out.println("请输入你要添加的一个数");
                    int num = sc.nextInt();
                    arrayQueue.addQueue(num);
                    break;
                case 'g'://从队列取出数据
                    try {
                        int goQueue = arrayQueue.goQueue();
                        System.out.println("取出的数据是" + goQueue);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }

                    break;
                case 'h'://查看队列头的数据
                    try {
                        int headData = arrayQueue.headData();
                        System.out.println("头数据是" + headData);
                    } catch (Exception e) {
                        System.out.println(e.getMessage());
                    }
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出");
    }
}

class ArrayQueue {
    private int maxsize;//队列最大长度
    private int head;//队列头
    private int tail;//队列尾
    private int[] arr;//该数组用来存放数据  模拟队列

    public ArrayQueue(int maxsize) {
        this.maxsize = maxsize;
        arr = new int[maxsize];
        head = -1;//指向队列头的前一个位置
        tail = -1;//指向队列尾的位置(不是后一位置)
    }

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

    //判断队列是否为空
    public boolean isEmpty() {
        return tail == head;
    }

    //添加数据到队列
    public void addQueue(int data) {
        //队列已满的话无法添加
        if (isFull()) {
            System.out.println("队列满了,无法继续添加数据");
            return;
        }
        tail++;//让队列尾后移
        arr[tail] = data;
    }

    //获取队列的数据  出队列
    public int goQueue() {
        //判断队列是否为空  如果为空无数据可以出
        if (isEmpty()) {
            throw new RuntimeException("队列中无数据,无法出队列");
        }
        head++;//让队列头后移
        System.out.println(head);
        return arr[head];
    }

    //显示队列的所有数据
    public void showQueue() {
        //遍历
        if (isEmpty()) {
            System.out.println("队列为空,无数据");
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.println("arr["+i+"]="+arr[i]);
        }
    }

    //显示队列的头数据  不用取出
    public int headData() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空,没有头数据");
        }
        return arr[head + 1];
    }

}

         其实,这样设计还存在很大的问题,假设这个队列的maxsize为5,入队a1 a2 a3 a4 a5后,出队a1 a2,如果继续入队的话,因为数组末尾元素已经被占用,会产生数组越界错误,可实际上,我 们的队列在下标为0和1的地方还是空闲的。我们把这种现象叫做假溢出,下一篇就来解决假溢出的问题。

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/955733.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号