数据结构与算法-队列

Bertha 。 2024-03-31 11:31 89阅读 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