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

队列

程序员文章站 2022-03-05 12:40:35
...

队列介绍

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

数组模拟队列

队列本身是有序列表,若使用数组的结构来存储队列的数据,则队列数组的最大容量就是数组的长度。
因为队列的输出、输入是分别从前后端来处理,因此需要两个变量front及rear分别记录队列前后端的下表,front会随着数据输出而改变,rear则是随着数据输入而改变。

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

  1. 将尾指针往后移:rear+1,当front==rear 【空】
  2. 若尾指针rear小于队列的最大下表maxSize-1,则将数据存入rear所指的数据元素中,否则无法存入数据。rear==maxSize-1 【队列满】

代码实现

class ArrayQueue{
    private int maxSize; //队列的最大容量
    private int front; //队列头
    private int rear; // 队列尾
    private int[] arr; //模拟队列的数组,用于存数据

    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        arr = new int[this.maxSize];
        this.front = -1; //指向队列头部,指向队列头的前一个位置。
        this.rear = -1; // 指向队列尾,即队列最后一个数据
    }


    public boolean isFull(){
        return rear==this.maxSize-1;
    }

    public boolean isempty(){
        return rear==front;
    }


    public void addQueue(int n){
        if (isFull()){
            System.out.println("队列已满");
            return;
        }
        rear ++; //让rear后移
        arr[rear] = n;
    }

//    获取队列的数据,出队列
    public int getQueue(){
        if (isempty()){
            throw  new RuntimeException("队列为空");
        }
        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 headQueue(){
        if (isempty()){
            throw  new RuntimeException("队列没有数据");
        }
        return arr[++front];
    }

}

环形队列实现


/**
 * 可循环使用的数组环绕队列
 * 1、front变量的含义做一个调整:front就指向队列的第一个元素,也就是说arr[front]就是队列的第一元素,
 *      front的初始值=0
 *  2、rear变量的含义做一个调整,rear指向队列的最后一个元素的后一个位置,因为希望空出一个空间做为约定
 *      rear的初始值=0
 *  3、当队列满时,条件是:(rear+1)% maxSize == front [满]
 *  4、 对队列为空的条件,rear==front 【空】
 *  5、 队列中有效的数据个数 (rear + maxSize - front)%maxSize
 */
class ArrayQueue2{
    private int maxSize; //队列的最大容量
    private int front; //队列头
    private int rear; // 队列尾
    private int[] arr; //模拟队列的数组,用于存数据

    public ArrayQueue2(int maxSize) {
        this.maxSize = maxSize;
        arr = new int[maxSize];
    }


    public boolean isFull(){
        return (rear+1)%maxSize==front;
    }

    public boolean isempty(){
        return rear==front;
    }


    public void addQueue(int n){
        if (isFull()){
            System.out.println("队列已满");
            return;
        }
        arr[rear] = n;
        rear = (rear+1)%maxSize;

    }

//    获取队列的数据,出队列
    public int getQueue(){
        if (isempty()){
            throw  new RuntimeException("队列为空");
        }
        int result = arr[front];
        front = (front+1)%maxSize;
        return result;
    }

    //显示队列所有数据
    public void showQueue(){
        if (isempty()){
            System.out.println("队列为空");
            return;
        }
        //获取有效个数数据
        int count = size();
        for (int i=front;i<front+count;i++){
            System.out.printf("arr[%d]=%d\n",(i%maxSize),arr[i%maxSize]);
        }
    }

    public int size(){
        return (rear+maxSize-front) % maxSize;
    }


    public int headQueue(){
        if (isempty()){
            throw  new RuntimeException("队列没有数据");
        }
        return arr[front];
    }

}