Java-自定义队列

约定不等于承诺〃 2023-10-02 17:37 10阅读 0赞

### 队列的概述 ###

![在这里插入图片描述][8e1021b4da744cb99c0f3047d247cef5.png]

队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。 队列的工作原理与现实生活中的队列完全相同。假设你与朋友一起在公交车站排队，如果你排在他前面，你将先上车，而后来的人将会排在你朋友后面。队列的工作原理与此相同。

队列是一种先进先出（First In First Out）的线性表，简称FIFO。 允许插入的一端称为队尾，允许删除的一端称为队头。假设队列是q=(a1,a2,…,an)，那么a1就是队头元素，而an是队尾元素。这样我们就可以删除时，总是从a1开始，而插入时，列在最后。  
![在这里插入图片描述][18c9af3e3c7c45afbaacc930b6c03c45.png]  
因为队列属于线性表，因此队列也可以采用顺序存储结构和链式存储结构来实现。Java中已经提供了很多线程的队列的实现，比如JUC中的各种阻塞、非阻塞队列。在生产环境中，各种消息队列比如kafka底层都使用了最基本的队列的特性。队列的使用频率是要高于栈的。

### 队列接口 ###

package com.lineardatastructure.queue;
    /**
     * @author huanmin
     * @param <T>
     */
    /**
     * 自定义队列接口定义
     **/
    public interface Queue<T> {
        
    
        /**
         * 向队列中添加元素
         *
         * @param e
         */
        void push(T e);
    
        /**
         * 从队列中删除元素
         */
        T pop();
    
        /**
         * 获取队列顶元素
         *
         * @return
         */
        T peek();
    
        /**
         * 获取队列中元素个数
         *
         * @return
         */
        int getSize();
    
        /**
         * 判断队列中是否为空
         *
         * @return
         */
        boolean isEmpty();
    
        /**
         * 判断队列是否满
         * @return
         */
        boolean isFull();
    
        /**
         * 销毁队列
         */
        void queueDestroy();
    }

### 队列数组储结构 ###

队列的入队和出队操作在不同端。采用数组来实现时，如果队头在数组元素最小索引处，那么入队列就是将元素添加到最大索引后的索引处，不需要移动元素，此时时间复杂度为Ｏ(1), 但是出队列就要在数组头部了，此时将会移动全部元素，时间复杂度为O(n)(但是也是有优化办法看下图)。  
![在这里插入图片描述][056c7faa51d44b63bed1f55f4e96c8d9.png]  
当浪费到指定数量内存后我们进行迁移数据  
![在这里插入图片描述][e7469dec2f8c4662ad37168430ce9fcf.png]  
当队列满了,我们就进行扩容  
![在这里插入图片描述][fb4ee32d0e764850aab419a189117791.png]

package com.lineardatastructure.queue;
    /**
     * @author huanmin
     * @param <T>
     */
    public class ArrayQueue<T> implements Queue<T> {
        
    
        private Object[] arrayQueue;//队列数组
        private int end = 0;//队尾下标
        private int begin=0;//队列开头
        private final int CLEARTRASH = 1000; //垃圾个数
        private  int length;
    
        public ArrayQueue(int size) {
        
            arrayQueue = new Object[size];
        }
    
        public ArrayQueue() {
        
            arrayQueue = new Object[30];
        }
    
        @Override
        public synchronized void push(T e) {
        
            if (!this.isFull()) {
        
                this.arrayQueue[this.end++] = e;
            } else {
        
                //队列满了进行扩容
                this.length = this.arrayQueue.length + (int) (this.arrayQueue.length * 0.75 + 1);
                Object[] target = new Object[this.length];
                //java最快数组copy方式
                System.arraycopy(this.arrayQueue, 0, target, 0, this.arrayQueue.length);
                this.arrayQueue = target;//将原数组替换
    
                this.arrayQueue[this.end++] = e;
            }
    
        }
    
        @Override
        public synchronized T pop() {
        
            if (this.isEmpty()) {
        
                System.out.println("队列为空,请先向队列中添加元素");
                return null;
            } else {
        
                T t = (T) this.arrayQueue[this.begin];
                if (this.begin == CLEARTRASH) {
        
                    //队列向前移动,清理垃圾
                    int i = this.CLEARTRASH + 1;
                    int i1 =this.end-i ;
                    Object[] target = new Object[this.length];
                    System.arraycopy(this.arrayQueue, i, target, 0, i1);
                    this.arrayQueue = target;
                    this.begin = -1;
                    this.end=this.end-i;
                }
                this.begin++;
    
    
                return t;
            }
    
        }
    
    
        @Override
        public synchronized T peek() {
        
            return (T) this.arrayQueue[this.begin];
        }
    
        @Override
        public synchronized int getSize() {
        
            return this.end;
        }
    
        @Override
        public synchronized boolean isEmpty() {
        
            if (this.arrayQueue == null) {
        
                return true;
            }
            return this.arrayQueue[this.begin] == null;
        }
    
        @Override
        public synchronized boolean isFull() {
        
            return this.arrayQueue.length == this.end;
        }
    
        @Override
        public synchronized void queueDestroy() {
        
            this.arrayQueue = null;
            this.end = 0;
        }
    }

### 队列链表储结构 ###

队列的入队和出队操作在不同端。采用链表来实现时，队列头和队列尾部, 时间复杂度都是Ｏ(1) 使用链式结构实现队列相比顺序结构的实现更加简单。

队列的链式存储结构，其实就是线性表的单链表，只不过它只是尾进头出而已，我们把它简称为链队列。为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端节点  
![在这里插入图片描述][4fdec03120fa458e88b8ed59347cd820.png]  
空队列时，头指针front和尾指针rear都指向头结点。

![在这里插入图片描述][a364dc4fe70448ab836d3f8cf203103c.png]

**插入**  
![在这里插入图片描述][f7c130b8fa064a82aa5ac608daea40f9.png]

**取值**  
![在这里插入图片描述][0dce41f8bd964fbe8c5f6f65c29c5c0a.png]

package com.lineardatastructure.queue;
    
    /**
     * @author huanmin
     * @param <T>
     */
    public class LinkedQueue<T> implements  Queue<T>{
        
        /**
         * 指向队头结点的引用
         */
        private Node<T> first;
    
    
        /**
         * 指向队尾结点的引用
         */
        private Node<T> end;
        /**
         * 元素个数
         */
        private int size;
        private static class Node<T> {
        
            //下一个结点的引用
            Node<T> next;
            //结点数据
            T data;
    
            //节点构造器
            public Node(T data, Node<T> next) {
        
                this.data = data;
                this.next = next;
            }
        }
    
    
        @Override
        public void push(T e) {
        
            //创建新节点
            Node<T> newNode = new Node<>(e, null);
            if (this.end == null) {
        
                this.end = newNode;
                this.first = newNode;
                this.size++;
                return;
    
            }
            //改变头节点,和尾节点 ,A-b-c-d
            this.end.next=newNode;// 这个动作其实是添加this.first的下一个节点 ,1,2,3,4
            this.end=newNode;    //存放最后节点元素
            this.size++;
    
        }
    
        @Override
        public T pop() {
        
            if (this.isEmpty()) {
        
               return  null;
            }
            T e = this.first.data;
            //改变队头节点引用,将下一个节点引用替换当前引用
            this.first = this.first.next;
            //如果元素为0,则将队尾节点引用置空
            if (--this.size == 0) {
        
                this.end = null;
            }
            return e;
    
        }
    
        @Override
        public T peek() {
        
            return this.first.data;
        }
    
        @Override
        public int getSize() {
        
            return this.size;
        }
    
        @Override
        public boolean isEmpty() {
        
            return this.first == null;
        }
    
        @Override
        public boolean isFull() {
        
            return false;
        }
    
        @Override
        public void queueDestroy() {
        
            this.first=null;
            this.end=null;
            this.size=0;
        }
    }

点赞 -收藏-关注-便于以后复习和收到最新内容有其他问题在评论区讨论-或者私信我-收到会在第一时间回复如有侵权，请私信联系我感谢,配合,希望我的努力对你有帮助^\_^

![ceaefc422a4745479fc1e8cfd2bdb74e.jpg][]

[8e1021b4da744cb99c0f3047d247cef5.png]: https://img-blog.csdnimg.cn/8e1021b4da744cb99c0f3047d247cef5.png
[18c9af3e3c7c45afbaacc930b6c03c45.png]: https://img-blog.csdnimg.cn/18c9af3e3c7c45afbaacc930b6c03c45.png
[056c7faa51d44b63bed1f55f4e96c8d9.png]: https://img-blog.csdnimg.cn/056c7faa51d44b63bed1f55f4e96c8d9.png
[e7469dec2f8c4662ad37168430ce9fcf.png]: https://img-blog.csdnimg.cn/e7469dec2f8c4662ad37168430ce9fcf.png
[fb4ee32d0e764850aab419a189117791.png]: https://img-blog.csdnimg.cn/fb4ee32d0e764850aab419a189117791.png
[4fdec03120fa458e88b8ed59347cd820.png]: https://img-blog.csdnimg.cn/4fdec03120fa458e88b8ed59347cd820.png
[a364dc4fe70448ab836d3f8cf203103c.png]: https://img-blog.csdnimg.cn/a364dc4fe70448ab836d3f8cf203103c.png
[f7c130b8fa064a82aa5ac608daea40f9.png]: https://img-blog.csdnimg.cn/f7c130b8fa064a82aa5ac608daea40f9.png
[0dce41f8bd964fbe8c5f6f65c29c5c0a.png]: https://img-blog.csdnimg.cn/0dce41f8bd964fbe8c5f6f65c29c5c0a.png
[ceaefc422a4745479fc1e8cfd2bdb74e.jpg]: https://img-blog.csdnimg.cn/ceaefc422a4745479fc1e8cfd2bdb74e.jpg