java实现数据结构03.02（队列详解代码之自定义循环队列）

淡淡的烟草味﹌ 2023-06-22 10:23 58阅读 0赞

## 队列接口 ##

/**
     * @description: 队列接口
     * @author: liangrui
     * @create: 2019-12-15 20:24
     **/
    public interface Queue<E> {
    
        /**
         * 向队列添加元素
         * @param e 添加的元素
         */
        void enqueue(E e);
    
        /**
         * 移除队首中的元素
         * @return 返回移除的元素
         */
        E dequeue();
    
        /**
         * 获取队首的元素
         * @return 返回队首的元素
         */
        E getFront();
    
        /**
         * 获取队列元素个数
         * @return 返回队列元素个数
         */
        int getSize();
    
        /**
         * 判断队列是否为空
         * @return 为空返回true,不为空返回false
         */
        boolean isEmpty();
    }

## 自定义循环队列类 ##

/**
     * @description: 循环队列
     * @author: liangrui
     * @create: 2019-12-15 21:05
     **/
    public class LoopQueue<E> implements Queue<E> {
    
        private E[] data;
        //队首对位下标
        private int front,tail;
        private int size;
    
        /**
         * 有参构造函数
         * @param capacity 容器大小
         */
        public LoopQueue(int capacity){
            //因为是循环队列，当队列满了后，front=tail,然而此时也可表示队列为空，导致冲突，使用capacity+1则可以避免这种冲突发生
            data=(E[]) new Object[capacity+1];
            front=0;
            tail=0;
            size=0;
        }
    
        /**
         * 无参构造函数
         */
        public LoopQueue(){
            this(10);
        }
    
        /**
         * 重新修改队列容量
         * @param newCapacity
         */
        private void resize(int newCapacity){
            //新数组
            E[] newData=(E[]) new Object[newCapacity+1];
            //给新数组添加数据
            for (int i = 0; i < size; i++) {
                newData[i]=data[(i+front)%data.length];
            }
            data=newData;
            //队首为0
            front=0;
            //队尾下标为元素个数
            tail=size;
        }
    
        @Override
        public void enqueue(E e) {
            //如果队尾下标+1等于队首下标
            if ((tail + 1) % data.length == front) {
                //表示队列已满，需要扩容，扩容为原来的2倍
                resize((data.length - 1) * 2);
            }
            //添加元素
            data[tail] = e;
            //队尾右移一位
            tail = (tail + 1) % data.length;
            //元素个数+1
            size++;
        }
    
        @Override
        public E dequeue() {
            //如果队列为空，没有可移除的元素，则抛出异常
            if (isEmpty()){
                throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
            }
            //获取移除的队首元素
            E e=data[front];
            //移除的队首元素
            data[front]=null;
            //队首右移一位
            front=(front+1)%data.length;
            //元素个数-1
            size--;
            //如果元素个数小于对面容量的1/4且队列容量不小于2，则缩小队列容量为原来的1/2
            if (size==(data.length-1)/4&&(data.length-1)/2!=0){
                resize((data.length-1)/2);
            }
            
            return e;
        }
    
        @Override
        public E getFront() {
            //如果队列为空，没有可获取的元素，则抛出异常
            if (isEmpty()){
                throw new IllegalArgumentException("Cannot getFront from an empty queue.");
            }
            //获取队首元素
            E e=data[front];
            return e;
        }
    
        @Override
        public int getSize() {
            return size;
        }
    
        @Override
        public boolean isEmpty() {
            //如果队首与队尾下标相同，则队列为空
            return front==tail;
        }
    
        @Override
        public String toString() {
            StringBuilder res=new StringBuilder();
            res.append(String.format("Queue: size=%d,capacity=%d\n",size,data.length-1));
            res.append("front [");
            //i = front从队首获取元素，直到队尾
            for (int i = front; i !=tail; i=(i+1)%data.length) {
                res.append(data[i]);
                //如果未到队尾，则加逗号
                if ((i+1)%data.length!=tail){
                    res.append(",");
                }
            }
            res.append("] tail");
            return res.toString();
        }
    }

## main测试 ##

public class Main {
    
        public static void main(String[] args) {
           LoopQueue<Integer> loopQueue=new LoopQueue<>();
            for (int i = 0; i < 5; i++) {
                loopQueue.enqueue(i);
                System.out.println(loopQueue);
            }
            loopQueue.dequeue();
            System.out.println(loopQueue);
        }
    }

## 测试结果： ##

> Queue: size=1,capacity=10  
> front \[0\] tail  
> Queue: size=2,capacity=10  
> front \[0,1\] tail  
> Queue: size=3,capacity=10  
> front \[0,1,2\] tail  
> Queue: size=4,capacity=10  
> front \[0,1,2,3\] tail  
> Queue: size=5,capacity=10  
> front \[0,1,2,3,4\] tail  
> Queue: size=4,capacity=10  
> front \[1,2,3,4\] tail