[数据结构与算法]Day552.队列 -数据结构和算法Java

队列

一、队列定义

队列是一个有序列表，可以用数组或是链表来实现。

遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出

二、简单队列实现

该方式会出现队列无法重复使用的问题

当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：思路分析

• 将尾指针往后移：rear+1 , 当front == rear 【空】

• 若尾指针 rear 小于队列的最大下标 maxSize-1，则将数据存入 rear所指的数组元素中，否则无法存入数据。 rear == maxSize - 1[队列满]

• 代码实现

package com.achang.queue;

/**
 * @Author Achang
 * @Date 2022/3/7 20:38
 *  通过数组模拟队列
 *  这方式会出现数组只能使用一次就不能再使用了
 **/
public class ArrayQueue {

    private int maxSize;//数组最大容量
    private int front;//指向队列头的前一个元素
    private int rear;//队列尾部
    private int[] arr;//数据

    public ArrayQueue(int maxSize){
        this.maxSize = maxSize;
        this.front = -1;
        this.rear = -1;
        this.arr = new int[maxSize];
    }

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

    public boolean isFree(){
        return this.front == this.rear;
    }

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

    public int getQueue(){
        if (isFree()){
            throw new RuntimeException("队列为空");
        }else {
            front++;
            return arr[front];
        }
    }

    public void showArr(){
        if (isFree()){
            System.out.println("队列为空，无法遍历");
            return;
        }
        for (int i : this.arr) {
            System.out.print(i);
        }
    }

    public int headQueue(){
        if (isFree()){
            throw new RuntimeException("队列为空");
        }
        return arr[front+1];
    }


    public static void main(String[] args) {
        ArrayQueue arrayQueue = new ArrayQueue(3);
    }

}

三、循环队列

package com.achang.queue;

/**
 * @Author Achang
 * @Date 2022/3/7 21:36
 * 通过算法 实现环形队列，解决上面一个数组只能用一次的问题
 **/
public class CircleArrayQueue {

    private int maxSize;//数组最大容量
    private int front;//指向队列头
    private int rear;//队列尾部的后一个元素
    private int[] arr;//数据

    public CircleArrayQueue(int maxSize) {
        this.maxSize = maxSize+1;
        this.front = 0;
        this.rear = 0;
        this.arr = new int[maxSize];
    }

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

    public boolean isFree() {
        return this.front == this.rear;
    }

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

    public int getQueue() {
        if (isFree()) {
            throw new RuntimeException("队列为空");
        } else {
            int temp = arr[front];
            front = (front + 1) % maxSize;
            return temp;
        }
    }

    public void showArr() {
        if (isFree()) {
            System.out.println("队列为空，无法遍历");
            return;
        }
        for (int i = front; i < rear + size(); 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 (isFree()) {
            throw new RuntimeException("队列为空");
        }
        return arr[front];
    }

    public static void main(String[] args) {
        CircleArrayQueue circleArrayQueue = new CircleArrayQueue(3);
    }
}