2021 - 9 下旬 数据结构-线性表-循环队列-java实现代码

//循环队列，本质就是用动态数组实现的，且出队入队时间复杂度均O（1）的队列
//相比普通队列，增设一个front指针，代表队头，代表下一个出队的元素
//循环队列的重点在于队头队尾的元素的下标的计算（本质是映射循环队列中的真实索引），以及队列满的判断条件
//真实元素下标：(index+front)%elements.length（index为队列中下标，计算得真实数组中下标）
// 队尾：index =size-1   入队位置 index =size  出队位置（队头）：front（移动至(front+1)%elements.length）

public class CircleQueueZH {
    private int size;
    private int front;
    private  E elements[];
    private static final int DEFAULT_CAPACITY = 10;//默认数组大小，可以扩容

    public CircleQueueZH(){
        elements = (E[]) new Object[DEFAULT_CAPACITY];//构造函数，泛型这里用Object类时，别忘了强制转换为E
    }

    //计算队头队尾元素下标可以写一个函数，用来映射循环队列中的真实索引
    public int realIndexCaculate(int index){
        return (index+front)%elements.length;//!!!
        //就是要找队列中的下标为index的（第index+1个）元素，返回它在我们数组里的真实下标
        //我觉得影响以后的可读性就没用
    }


    //动态扩容函数，之前写过一个int版，现在又拿过来用了，把2倍扩容改为了位运算的1.5倍扩容
    private void ifNeedEnLarge(int needCapacity){
        int oldcapacity = elements.length;
        if (needCapacity<=oldcapacity){
            return;
        }else{
            int newcapacity = oldcapacity + (oldcapacity>>1);//位运算效率高，相当于除2
            E[] newElements = (E[]) new Object[newcapacity];
            for (int i=0;i