学会一种数据结构一：队列

怼烎@ 2022-06-05 10:10 75阅读 0赞

学习新知识的时候，经常看到源码使用了某种数据结构，如果不了解这种数据结构就很难看懂源码，所以在学习其它知识之余，花点时间学习遇到的数据结构。

今天先学习队列。

### 定义 ###

来自专家审核的百度百科：  
**队列：**  
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。  
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。  
**线性表：**  
*线性表中数据元素之间的关系是一对一的关系，即除了第一个和最后一个数据元素之外，其它数据元素都是首尾相接的（注意，这句话只适用大部分线性表，而不是全部）。*

所以队列可以用下方这个图表示：

![队列][SouthEast]

所以无论那种编程语言，要实现队列，都要满足一下特点：  
– 从头部出去  
– 从尾部进来  
– 中间的队列元素要知道后一个是谁  
– 最后一个元素，下一个为空

### 实现 ###

上面了解队列的特点，下面用java实现一个队列，要求满足上面的特性，提供增加、取出最新元素、取出指定元素、删除、size等方法。

public class CustomQueue<E> {
    
        private Node head;
        private Node end;
        private int size = 0;
    
    
        private static class Node<E> {
    
            private E value;
            private Node next;
    
            public Node () {
            }
    
            public Node (E value) {
                this.value = value;
            }
    
            public E getValue () {
                return value;
            }
    
    
    
            public Node getNext () {
                return next;
            }
    
            public void setNext (Node next) {
                this.next = next;
            }
        }
    
        /** * 在尾部增加一个元素，如果头部为空，就先构建一个头部，并把头部复制给尾部，否则把新元素添加到尾元素的下一个元素属性上 * @param obj * @return 新增的元素节点 */
        public Node add(E obj) {
            Node temp = new Node(obj);
            if (null == head) {
                head = temp;
                end = head;
                size++;
            } else {
                if (end.equals(head)) {
                    head.setNext(temp);
                    end = temp;
                } else {
                    end.setNext(temp);
                    end = temp;
                }
                size++;
            }
            return temp;
        }
    
        /** * 返回队列的元素的个数 * @return */
        public int size() {
    
            return size;
        }
    
        /** * 取出头部的元素 * @return Object */
        public E pop() {
    
            E value;
            Node temp = head;
    
            if (null != head) {
                value = (E)temp.getValue();
                if (head.equals(end)) {
                    head = null;
                    end = null;
                } else {
                    Node next = head.getNext();
                    head = next;
                }
            } else {
                value = null;
            }
            return value;
        }
    }

上面是根据队列特性，实现的一个自定义的队列，这个队列提供add(新增)、pop(取出第一个)、size(当前队列有多少个元素)三个方法。  
测试：

public class QueueTest {
    
    
        public static void main (String[] args) {
            CustomQueue<String> queue = new CustomQueue<String>();
            queue.add("123");
            queue.add("456");
            queue.add("789");
            queue.add("147");
    
            System.out.println("数量=" + queue.size());
            System.out.println("取出第一个" + queue.pop());
            System.out.println("取出第二个" + queue.pop());
            System.out.println("取出第三个" + queue.pop());
            System.out.println("取出第四个" + queue.pop());
            System.out.println("取出第五个" + queue.pop());
            System.out.println("取出第六个" + queue.pop());
        }
    
    }

测试结果：

数量=4
    取出第一个123
    取出第二个456
    取出第三个789
    取出第四个147
    取出第五个null
    取出第六个null

存了四个数据，取出了四个数据，继续取的话就会返回null（没有了）。

实际上这个实现只是简单的实现，没有提供一下常用的方法，比如判断下一个元素有没有（不取出来），多线程的情况下的并发问题等。

目前先了解到这些，后面在这个基础上，学习更多的实现。

[SouthEast]: /images/20220605/150fe851551c4fa88a8e8c9f2f7020eb.png