使用java自己实现一个队列

水深无声 2023-07-15 02:56 25阅读 0赞

大家好，今天和大家分享一个自定义队列的实现，这也是很多面试中，容易问到，或者直接让大家写的一个题目。围绕这个题目，那么我们首先需要分析如何实现，那就要结合队列的特点。队列这种数据结构的特点我想大家肯定随口都能说得出来，那就是“先进先出” 。 那么我们如何设计一个先进先出的数据结构呢，首先能够确定的是，它属于一个线性结构，那么线性结构的实现，其实我们可用的选择就比较多，比如数组， 比如链表。 在这两个的基础上，再来想如何设计一个队列，队列的话，无外乎两种常用的操作，一个是入队，一个是出队。 既然是先进先出的，那么入队的时候，肯定要把元素放到集合的末尾，同理，出队的时候，要把集合的头部（也就是第一个元素） 返回。所以明确了这样的需求，实现起来就好办了，同时我们还可以维护一个队列的长度。

那如果使用数组实现的话，我们就实现设置一个数组对象作为成员变量，而数组的长度我们可以设置一个随机值，当然可以通过构造方法的方式，传进来在初始化数组的长度。那如果进队的时候 ， 我们只需要把数组的最后一个元素设置为传进来的数据即可。而使用数组最麻烦的就是出队，因为出队的时候我们需要返回第一个元素， 但是需要注意的是，出队的时候，我们需要把出队的元素移除掉，所以当我们把数组第一个元素移除掉的时候，队列不可一日无头， 所以可能我们需要把从第二个元素到最后一个元素都向前移动一个位置，这种情况如果数组中数据比较多的话就比较耗费性能了，所以数组实现队列并不是一个特别好的方案，当然是可以实现的。

那么怎么样能在移动元素的时候，不调动或影响其他元素呢，这时候其实就比较容易想到链表，链表都维护了一个指向下一个元素的指针，没有绝对的位置（不像数组中的角标那么绝对） ，链表移除元素的时候，只需要把对应的指针一修改就可以 了，所以相对还是比较容易的。其实最简单的队列实现方式，就是我们完全可以在队列中使用一个LinkedList来存放元素，入队直接addLast,出队直接removeFirst , 单面试的时候如果这么写，不免有作弊嫌疑。因为我们都是调用的现成的方法，根本没有写出实现的核心所在。所以接下来我们来自己使用链表的方式来实现一个队列。 所以程序中有两个部分，一部分是链表，一部分是队列。链表怎么实现呢。其实就是一个对象中引用了一个叫做next的本身对象。然后我们在实现相应的入队，出队的方法即可。

接下来请看代码：

/**
     * 使用链表实现
     */
    public class Queue2<T> {
        // 这里的Node使用的是内部类实现的链表，Node中有一个next的Node实现了指向下一个元素
        Node<T> first; //维护队列的头元素，用于出队，出队返回头，将后一个节点置为头
        Node<T> last;  //维护队列的尾元素，用于入队，入队加入到此元素后
        int size;
    
        // 入队
        public void put(T data){
            Node<T> node = new Node(data);
            //代表此时队列为空
            if(first == null && last == null){
                first=node;
                last = node;
            }else{
                //队列不为空：
                last.next = node;
                last = node;
            }
            size++;
        }
    
        /**
         * 出队
         * 从头部获取一个元素
         * @return
         */
        public T pop(){
            if(size == 0){
                return null;
            }
            Node<T> temp = first;
            first = first.next;
            size--;
            return temp.t;
        }
    
    
        /**
         * 使用内部类自定义一个节点
         * @param <T>
         */
        class Node<T>{
            /**
             * 代表当前节点中的数据
             */
            T t;
            /**
             * 代表下一个节点
             */
            Node next;
            public Node(T t){
                this.t = t;
            }
    
            public String toString(){
                return t.toString();
            }
        }
    
        public void printAll(){
            Node temp = first;
            while(temp.next != null){
                System.out.println(temp);
                temp = temp.next;
            }
            System.out.println(temp);
        }
    
        public static void main(String[] args) {
            Queue2<String> queue2 = new Queue2<>();
            queue2.put("a");
            queue2.put("b");
            queue2.put("c");
            queue2.put("d");
            queue2.printAll();
            System.out.println(queue2.size);
            System.out.println(queue2.pop());
            System.out.println(queue2.pop());
            System.out.println(queue2.size);
            System.out.println(queue2.pop());
            System.out.println(queue2.pop());
            System.out.println(queue2.pop());
            System.out.println(queue2.size);
        }
    
    }

好了，这就是自己实现的一简单队列，使用LinkedList的实现方式如果有兴趣的同学，可以访问我的github,相关代码都已提交，上面还有springboot整合dubbo,redis,rocketmq,quartz,nacos的案例，欢迎访问交流：[https://github.com/lsqingfeng/action/][https_github.com_lsqingfeng_action]

[https_github.com_lsqingfeng_action]: https://github.com/lsqingfeng/action/