欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

队列

程序员文章站 2022-03-08 18:59:40
...

队列是一个有序列表,可以用数组或是链表来实现。遵循先入先出的原则。

数组模拟环形队列


【1】队列本身是有序列表,若使用数组的结构来存储队列数据,队列数组的声明如下,其中 maxSize 是该队列的最大容量;
 队列
【2】因为队列的输入输出是分别从头和尾来处理的,因此需要两个变量 front(头)=0 和 tail(尾)=0 ,tail会随着数据的输入而变化,front 会随着数据的输出而变化。
【3】为了充分利用数组,例如上图:当tail == maxSize 时,可以继续向 index = 0 的空下标中存放数据。此时就将数组看做一个环形数组(通过取模的方式来实现)。

分析环形数组实现思路:【1】尾(tail)索引的下一个为头(front)索引表示队列为满(因为判断空和判断满冲突,因此需要空出一个格子来做一个约定,相当于最多只能存放 maxSize - 2 的数据,浪费一个格子)这里判断队列满的公式:(tail+1)%maxSize == front ;用一张图来说明问题:
队列

代码实现如下:

package com.algorithms;

import java.util.Scanner;

/**
 * Created by Administrator on 2019/11/2 0002.
 */
public class CircleQueue {
    //定义一个数组
    private int[] arr;
    //数组的最大值
    private int maxSize;
    //头指针
    private int front;
    //尾指针
    private int tail;

    //创建一个带参的构造器,出入队列的大小
    public CircleQueue(int maxSize){
        this.maxSize = maxSize;
        arr = new int[maxSize];
    }

    //数据测试
    public static void main(String[] args) {
        CircleQueue circleQueue = new CircleQueue(5);
        System.out.println("根据提示输入相关值");
        Scanner in = new Scanner(System.in);
        while (true){
            System.out.println("s:显示");
            System.out.println("o:输入");
            System.out.println("p:输出");
            System.out.println("h:头出");
            String next = in.next();
            switch (next){
                case "s" : circleQueue.list(); break;
                case "o" :
                    System.out.println("请输入一个数");
                    int i = in.nextInt();
                    circleQueue.offer(i);
                    break;
                case "p" :
                    int poll = circleQueue.poll();
                    System.out.println(poll);
                    break;
                case "h" :
                    int peek = circleQueue.peek();
                    System.out.println(peek);
                    break;
            }
        }
    }

    //判断队列是否已满,根据我们的约定来,虽然它还能存放一个元素。
    //这里面没几个难点。。。这算一个**********************
    public boolean isFull(){
        return (tail + 1) % maxSize == front;
    }
    //插入方法
    public void offer(int num){
        if(isFull()){
            throw  new RuntimeException("队列已满");
        }
        arr[tail]=num;
        //不能直接 ++ 否则可以数据越界
        //这里面没几个难点。。。这算一个**********************
        tail = (tail + 1) % maxSize;
    }

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

    public int poll(){
        if(isEmpty()){
            throw new RuntimeException("队列为空");
        }
        int temp = arr[front];
        //不能直接 ++ 否则可以数据越界
        front = (front + 1) % maxSize;
        return temp;
    }

    //查看队列的大小
    public int size(){
        //tail+maxSize 是防止队列存满后,tail=2 在 front=3 的前面这种为负数的情况
        // %maxSize 是防止计算的结果大于 maxSize
        //这里面没几个难点。。。这算一个**********************
        return (tail+maxSize-front)%maxSize;
    }

    //循环查看所有元素信息
    public void list(){
        for(int i = front;i< front + size();i++){
            System.out.printf("arr[%d]==%d\n",i%maxSize,arr[i%maxSize]);
        }
    }

    //查看栈顶元素
    public int peek(){
        return arr[front];
    }
}

----如果喜欢,点个  红心♡  支持以下,谢谢----

相关标签: 队列