05.Java数据结构与算法之~队列与环形队列CircleArrayQueue

队列的介绍

.

       队列(queue)是只允许在一端进行插入操作,而在另一端进行删除操作的线性表

       插入的一端称为队尾,删除的一端称为队头

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

队列的缺点：

       出队复杂度高 O(n),容易假溢出

队列的链式存储及结构模式

       队列的链式存储结构,其实就是线性表的单链表，只不过它只能从尾进，从头出而已。

空队列->>

数组模拟队列

创建Queue接口

public interface Queue{
    boolean isFull();
    boolean isEmpty();
    void add(Object n);
    Object get();
    String toString();
    Object Head();
    int size();
}

数组模拟队列代码实现

//使用数组模拟队列,编写一个ArrayQueued类
public class ArrayQueue implements Queue{
    private int maxSize;                //表示数组的最大容量
    private int front;                  //队列头
    private int rear;                   //队列尾
    private Object[]arr;                //存放数据
    private int size;  //队列的大小,如果初始值是16,用户没填满，遍历时防止出现NULL
    private final int INITIAL=16;       //初始大小为16

    //创建队列的构造器
    public ArrayQueue(int arrMaxSize){
        maxSize = arrMaxSize;
        arr = new Object[maxSize];
        front = -1; //面向队列头部,指向队列头的前一个位置
        rear = -1;  //面向队列尾
    }

    //如果用户没设置大小,则默认为初始大小
    public ArrayQueue(){
        maxSize = INITIAL;
        arr = new Object[INITIAL];
        front = -1;
        rear = -1;
    }
    
    //判断队列是否已满
    public boolean isFull(){
        return rear == maxSize-1;
    }

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

    //添加数据到队列
    @Override
    public void add(Object n){
        if(isFull()){
            throw new IndexOutOfBoundsException("队列满!");
        }
        rear++; //让rear后移
        size++; //让大小增加
        arr[rear] = n;
    }
    //返回队列长度
     @Override
    public int size(){
        return size - (front + 1);
    }
    
    //获取队列数据,出队列
    @Override
    public Object get(){
        //判断队列是否空
        if(isEmpty()){
            throw new NullPointerException("队列为空!");
        }
        front++;    //让front后移
        return arr[front];
    }
    //遍历队列
    @Override
    public String toString(){
        if(isEmpty()){
            throw new NullPointerException("队列为空!");
        }
        StringBuilder stringBuilder = new StringBuilder("[");
        //循环到队列的倒数第二个位置结束循环，防止多加一个逗号妨碍美观
        for(int i = front + 1; i < size - 1; i++){
            stringBuilder.append(arr[i] + ",");
        }
        //添加最后一个数据
        stringBuilder.append(arr[size-1] + "]");
        return stringBuilder.toString();
    }
    //返回头数据
    @Override
    public Object Head(){
        //判断是否为空
        if(isEmpty()){
            throw new NullPointerException("队列空!");
        }
        return arr[front+1];
    }
}

环形数组队列模拟

把队列的这种头尾相接的顺序存储结构称为循环队列

       变量的含义做一个调整:front指向第一个元素,rear指向最后一个元素

队列的构造器

    //由于front和rear默认为0,所以不需要赋值了
    public CircleArrayQueue(int arrMaxSize){
        maxSize = arrMaxSize;
        arr = new Object[maxSize];
    }

判断队列是否已满

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

添加数据到队列

    @Override
    public void add(Object n){
        if(isFull()){
            throw new IndexOutOfBoundsException("队列满!");
        }
        arr[rear] = n;
        //将rear后移
        rear = (rear + 1) % maxSize;
    }

获取队列数据,出队列

       先把front对应的值保存到一个临时变量,将front后移,返回临时变量

  public Object get(){
        //判断队列是否空
        if(isEmpty()){
            throw new NullPointerException("队列为空!");
        }
        Object value = arr[front];
        front = (front + 1) % maxSize;
        return value;
    }

求长

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

代码实现

public class CircleArrayQueue implements Queue{
    private int maxSize;                //表示数组的最大容量
    private int front;                  //队列头
    private int rear;                   //队列尾
    private Object[]arr;                //存放数据
    private final int INITIAL=16;       //初始大小为16

    //创建队列的构造器
    public CircleArrayQueue(int arrMaxSize){
        maxSize = arrMaxSize;
        arr = new Object[maxSize];
    }

    //如果用户没设置大小,则默认为初始大小
    public CircleArrayQueue(){
        maxSize = INITIAL;
        arr = new Object[INITIAL];
    }

    //判断队列是否已满
    public boolean isFull(){
        return (rear + 1) % maxSize == front;
    }

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

    //添加数据到队列
    @Override
    public void add(Object n){
        if(isFull()){
            throw new IndexOutOfBoundsException("队列满!");
        }
        arr[rear] = n;
        //将rear后移
        rear = (rear + 1) % maxSize;
    }

    //获取队列数据,出队列
    @Override
    public Object get(){
        //判断队列是否空
        if(isEmpty()){
            throw new NullPointerException("队列为空!");
        }
        Object value = arr[front];
        front = (front + 1) % maxSize;
        return value;
    }
    //队列长度
    @Override
    public int size(){
        return (rear + maxSize - front) % maxSize;
    }

    //遍历队列
    @Override
    public String toString(){
        if(isEmpty()){
            throw new NullPointerException("队列为空!");
        }
        StringBuilder stringBuilder = new StringBuilder("[");
        //循环到队列的倒数第二个位置结束循环，防止多加一个逗号妨碍美观
        for(int i = front ; i < rear - 1; i++){
            stringBuilder.append(arr[i] + ",");
        }
        //添加最后一个数据
        stringBuilder.append(arr[rear-1] + "]");
        return stringBuilder.toString();
    }
    //返回头数据
    @Override
    public Object Head(){
        //判断是否为空
        if(isEmpty()){
            throw new NullPointerException("队列空!");
        }
        return arr[front];
    }
}