数据结构与算法-队列-蒲公英云

数据结构与算法-队列

Bertha 。 2024-03-31 11:31 227阅读 0赞

什么是队列
队列是一种特殊的线性表，说特殊是因为它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。例如我们去商店收银排队结账一样，就是一个队列，是一种FIFO先入先出的数据结构。

算法原理
1、初始化定长队列
2、插入元素需要先判断队列是否已经达到上限，达到上限进行扩容，否则进行队尾指针增加并插入元素
3、移除元素需要判断队列是否已经为空，为空抛出异常，否则将队首置空并重新规划队列

小试牛刀
1、创建队列模拟类，并提供入队、出队方法

/**
 * 队列
 * @author senfel
 * @version 1.0
 * @date 2022/11/25 16:07
 */
@Slf4j
public class Queue {
    /**
     * 队列数组
     */
    private Object[] elementList;
    /**
     * 队头
     */
    private int head;
    /**
     * 队尾
     */
    private int tail;
    /**
     * 队列长度
     */
    private int capacity;
    public Queue(int capacity) {
        this.capacity = capacity;
        this.elementList = new Object[capacity];
        this.head = 0;
        this.tail = -1;
    }
    /**
     * 元素个数
     * @return
     */
    public int size(){
        return tail-head+1;
    }
   /**
     * 队列是否为空
     * @return
     */
    public Boolean isEmpty(){
        return tail == -1;
    }
    /**
     * 队列长度
     * @return
     */
    public int queueLength(){
        return elementList.length;
    }
    /**
     * 入队
     * @param element
     * @author senfel
     * @date 2022/11/25 16:26
     * @return void
     */
    public void add(Object element){
        //队列满了扩容至两倍大小
        if(tail+1 >= elementList.length){
            log.error("队列达到最大容量：{}",capacity);
            int length = 0;
            if(elementList.length << 1 > Integer.MAX_VALUE){
                length = Integer.MAX_VALUE;
            }else{
                length = elementList.length << 1;
            }
            capacity = length;
            log.error("队列达到最大容量扩容至：{}",capacity);
            elementList = Arrays.copyOf(elementList,length);
        }
        //尾部索引增加并赋值
        elementList[++tail] = element;
        log.error("入队元素：{}",elementList[tail]);
        log.error("当前队列详情：{}",Arrays.toString(elementList));
        log.error("当前队列元素个数:{}",size());
    }
    /**
     * 出队
     * @author senfel
     * @date 2022/11/25 16:36
     * @return void
     */
    public void remove(){
        if(isEmpty()){
            throw new RuntimeException("队列为空");
        }
        log.error("出队元素：{}",elementList[head]);
        elementList[head] = null;
        //队列重排
        Object[] newQueue = new Object[capacity];
        System.arraycopy(elementList,head+1,newQueue,0,size());
        elementList = newQueue;
        tail--;
        log.error("当前队列详情：{}",Arrays.toString(elementList));
        log.error("当前队列元素个数:{}",size());
    }
}

2、提供测试方法

public static void main(String[] args) {
        Queue queue = new Queue(5);
        for(int i = 0;i<7;i++){
            queue.add(i);
        }
        log.error("队列长度为：{}",queue.queueLength());
        //模拟出队
        queue.remove();
        queue.remove();
        log.error("队列长度为：{}",queue.queueLength());
    }

3、加粗样式查看测试结果并展示出入队详情

17:01:13.028 - 入队元素：0
17:01:13.031 - 当前队列详情：[0, null, null, null, null]
17:01:13.031 - 当前队列元素个数:1
17:01:13.031 - 入队元素：1
17:01:13.031 - 当前队列详情：[0, 1, null, null, null]
17:01:13.031 - 当前队列元素个数:2
17:01:13.031 - 入队元素：2
17:01:13.031 - 当前队列详情：[0, 1, 2, null, null]
17:01:13.031 - 当前队列元素个数:3
17:01:13.031 - 入队元素：3
17:01:13.031 - 当前队列详情：[0, 1, 2, 3, null]
17:01:13.031 - 当前队列元素个数:4
17:01:13.031 - 入队元素：4
17:01:13.031 - 当前队列详情：[0, 1, 2, 3, 4]
17:01:13.031 - 当前队列元素个数:5
17:01:13.031 - 队列达到最大容量：5
17:01:13.031 - 队列达到最大容量扩容至：10
17:01:13.031 - 入队元素：5
17:01:13.031 - 当前队列详情：[0, 1, 2, 3, 4, 5, null, null, null, null]
17:01:13.031 - 当前队列元素个数:6
17:01:13.031 - 入队元素：6
17:01:13.031 - 当前队列详情：[0, 1, 2, 3, 4, 5, 6, null, null, null]
17:01:13.031 - 当前队列元素个数:7
17:01:13.031 - 队列长度为：10

17:01:13.031 - 出队元素：0
17:01:13.031 - 当前队列详情：[1, 2, 3, 4, 5, 6, null, null, null, null]
17:01:13.031 - 当前队列元素个数:6
17:01:13.031 - 出队元素：1
17:01:13.031 - 当前队列详情：[2, 3, 4, 5, 6, null, null, null, null, null]
17:01:13.031 - 当前队列元素个数:5
17:01:13.031 - 队列长度为：10