数据结构之数组、链表、栈和队列_数组是连续存储的数据类型,常被用来实现数据的顺序存储结构

1.数组

1.1：概念

数组是一种线性表数据结构，它用一组连续的内存空间，来存储一组具有相同类型的数据。这里我们要抽取出三个跟数组相关的关键词：线性表，连续内存空间，相同数据类型；数组具有连续的内存空间，存储相同类型的数据，正是该特性使得数组具有一个特性：随机访问。但是有利有弊，这个特性虽然使得访问数组边得非常容易但是也使得数组插入和删除操作会变得很低效，插入和删除数据后为了保证连续性，要做很多数据搬迁工作。

1.2：逻辑结构和物理结构

所谓的数组的逻辑结构指的是我们可以用什么的表示方式来描述数组元素，比如有一个数组 a,数组中有 n 个元素，我们可以用(a1,a2,a3,.....an)来描述数组中的每个元素，当然后面我们会将具体如何访问数组中的每个元素。数组的物理结构指的是数组元素实际的存储形式，当然了从概念我们可以看出数组的物理存储空间是一块连续的内存单已，为了说明白这个事情，这里给大家准备了一副图

 

从图中我们可以看出访问数组中的元素是通过下标来访问的，那是如何做到的呢？

1.2.1：数组元素的访问

我们拿一个长度为 10 的数组来举例，int [] a= new int[10]，在下面的图中，计算机给数组分配了一块连续的空间，100-139，其中内存的起始地址为baseAddress=100

 

我们知道，计算机给每个内存单元都分配了一个地址，通过地址来访问其数据，因此要访问数组中的某个元素时，首先要经过一个寻址公式计算要访问的元素在内存中的地址：

a[i] = baseAddress + i * dataTypeSize

其中 dataTypeSize 代表数组中元素类型的大小，在这个例子中，存储的是 int 型的数据，因此 dataTypeSize=4 个字节

1.2.2：数组下标为什么从 0 开始

数组的下标为什么要从 0 开始而不是从 1 开始呢？

从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。前面也讲到，如果用 array 来表示数组的首地址，array[0] 就是偏移为 0 的位置，也就是首地址，array[k] 就表示偏移 k 个 type_size 的位置，所以计算 array[k] 的内存地址只需要用这个公式:

array[k]_address = base_address + k * type_size

但是如果下标从 1 开始，那么计算 array[k]的内存地址会变成：

array[k]_address = base_address + (k-1)*type_size

对比两个公式，不难发现从数组下标从 1 开始如果根据下标去访问数组元素，对于 CPU 来说，就多了一次减法指令。

当然另一方面也是由于历史原因，c 语言设计者使用 0 开始作为数组的下标，后来的高级语言沿用了这一设计。

1.3：数组的特点

1.3.1：高效的随机访问

通过前面的学习我们已经知道，数组元素的访问是通过下标来访问的，计算机通过数组的首地址和寻址公式能够很快速的找到想要访问的元素

1.3.2：低效插入和删除

前面我们已经讲到数组是一段连续的内存空间，因此为了保证数组的连续性会使得数组的插入和删除的效率变的很低，下面我们来分析一下

• 插入

假设数组的长度为 n，现在如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来给新来的数据，我们需要将第 k～n 这部分的元素都顺序地往后挪一位。如下图所示：

 

那数组插入有没有相对优化的方案呢？

如果数组中的数据是有序的，我们在某个位置插入一个新的元素时，就必须按照刚才的方法搬移 k 之后的数据。但是，如果数组中存储的数据并没有任何规律，数组只是被当作一个存储数据的集合。在这种情况下，如果要将某个数组插入到第 k 个位置，为了避免大规模的数据搬移，我们还有一个简单的办法就是，直接将第 k 位的数据搬移到数组元素的最后，把新的元素直接放入第 k 个位置。这种处理思想会在快排中用到

• 删除

如果我们要删除第 k 个位置的数据，为了内存的连续性，也需要搬移数据，不然中间就会出现空洞，内存就不连续了。

实际上，在某些特殊场景下，我们并不一定非得追求数组中数据的连续性。如果我们将多次删除操作集中在一起执行，删除的效率是不是会提高很多呢？举个例子

数组 a[6] 中存储了 6 个元素：a1,a2,a3,a4,a5,a6。现在，我们要依次删除 a1,a2 这两个元素

 

为了避免 a3,a4,a5,a6 这几个数据会被搬移两次，我们可以先记录下已经删除的数据。每次的删除操作并不是真正地搬移数据，只是记录数据已经被删除。当数组没有更多空间存储数据时，我们再触发执行一次真正的删除操作，这样就大大减少了删除操作导致的数据搬移。

如果你了解 JVM，你会发现，这不就是 JVM 标记清除垃圾回收算法的核心思想吗？没错，数据结构和算法的魅力就在于此，很多时候我们并不是要去死记硬背某个**数据结构或者算法，而是要学习它背后的思想和处理技巧，这些东西才是最有价值的**。如果你细心留意，不管是在软件开发还是架构设计中，总能找到某些算法和数据结构的影子

1.4：数组的应用

针对数组类型，很多语言都提供了容器类，比如 Java 中的 ArrayList、C++ STL 中 的 vector。在项目开发中，什么时候适合用数组，什么时候适合用容器呢？

这里我拿 Java 语言来举例。如果你是 Java 工程师，几乎天天都在用 ArrayList，对它应该非常熟悉。那它与数组相比，到底有哪些优势呢？

我个人觉得，ArrayList 最大的优势就是可以将很多数组操作的细节封装起来。比如前面提到的数组插入、删除数据时需要搬移其他数据等。另外，它还有一个优势，就是 支持动态扩容 。数组本身在定义的时候需要预先指定大小，因为需要分配连续的内存空间。如果我们申请了大小为 10 的数组，当第 11 个数据需要存储到数组中时我们就需要重新分配一块更大的空间，将原来的数据复制过去，然后再将新的数据插入。如果使用 ArrayList，我们就完全不需要关心底层的扩容逻辑，ArrayList 已经帮我们实现好了。每次存储空间不够的时候，它都会将空间自动扩容为 1.5 倍大小。不过，这里需要注意一点，因为扩容操作涉及内存申请和数据搬移，是比较耗时的。所以，如果事先能确定需要存储的数据大小，最好在创建**ArrayList** 的时候事先指定数据大小。

作为高级语言编程者，是不是数组就无用武之地了呢？当然不是，有些时候，用数组会更合适些，我总结了几点自己的经验。

1.Java ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类，而 Autoboxing、Unboxing 则有一定的性能消耗，所以如果特别关注性能，或者希望使用基本类型，就可以选用数组。

2.如果数据大小事先已知，并且对数据的操作非常简单，用不到 ArrayList 提供的大部分方法，也可以直接使用数组。

我总结一下，对于业务开发，直接使用容器就足够了，省时省力。毕竟损耗一丢丢性能，完全不会影响到系统整体的性能。但如果你是做一些非常底层的开发，比如开发网络框架，性能的优化需要做到极致，这个时候数组就会优于容器，成为首选。

2.链表

2.1：概念

链表（Linked list）是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。读完这段对链表的解释之后我们可能还是不太明白链表到底是怎么一回事，那接下来我们从底层的存储结构开始解开链表的面纱

2.2：存储结构

相比数组，链表是一种稍微复杂一点的数据结构。对于初学者来说，掌握起来也要比数组稍难一些。这两个非常基础、非常常用的数据结构，我们常常将会放到一块儿来比较。所以我们先来看，这两者有什么区别。

首先我们从底层存储结构来看：

数组：需要一块连续的存储空间，对内存的要求比较高，比如我们要申请一个1000M 的数组，如果内存中没有连续的足够大的存储空间则会申请失败，即便内存的剩余可用空间大于 1000M，仍然会申请失败。

链表：与数组相反，它并不需要一块连续的内存空间，它通过指针将一组零散的**内存块**串联起来使用，所以如果我们申请一个 1000M 大小的链表，只要内存剩余的可用空间大于 1000M，便不会出现问题。

下方图片对比了链表和数组的存储结构

 

此时我们在来回顾我们刚刚提到的链表的概念：物理存储单元上非连续、非顺序，元素的逻辑顺序是通过链表中的指针链接次序实现的，链表由一系列结点组成，每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域

当然了这只是我们提到的链表的最基本的存储形式，其实链表有很多种不同的类型，分别对应了不同的结构，接下来我们就来分析不同的链表类型

2.3：链表类型

2.3.1：单链表

所谓的单链表就是我们刚刚讲到的链表的最基本的结构，链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的结点。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。如图所示，我们把这个记录下个结点地址的指针叫作后继指针 next ，如果链表中的某个节点为 p，p 的下一个节点为 q，我们可以表示为：p->next=q

下面的图更加详细的描述了单链表的存储结构

 

从单链表图中，你应该可以发现，其中有两个结点是比较特殊的，它们分别是第一个结点和最后一个结点。我们习惯性地把第一个结点叫作头结点，把最后**一个结点叫作尾结点。其中，头结点用来记录链表的基地址,有了它，我们就可以遍历得到整条链表。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址** NULL，表示这是链表上最后一个结点。

与数组一样，链表也支持数据的查找、插入和删除操作。

我们知道，在进行数组的插入、删除操作时，为了保持内存数据的连续性，需要做大量的数据搬移。而在链表中插入或者删除一个数据，我们并不需要为了保持内存的连续性而搬移结点，因为链表的存储空间本身就不是连续的。所以，在链表中插入和删除一个数据是非常快速的。

从下图中我们可以看出，针对链表的插入和删除操作，我们只需要考虑相邻结点的指针改变

 

但是，有利就有弊。链表要想随机访问第 k 个元素，就没有数组那么高效了。因为链表中的数据并非连续存储的，所以无法像数组那样，根据首地址和下标，通过寻址公式就能直接计算出对应的内存地址，而是需要根据针一个结点一个结点地依次遍历，直到找到相应的结点，所以，链表随机访问的性能没有数组好。

2.3.2：循环链表

循环链表是一种特殊的单链表。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。从我画的循环链表图中，你应该可以看出来，它像一个环一样首尾相连，所以叫作“循环”链表，和单链表相比，循环链表的优点是从链尾到链头比较方便。当要处理的数据具有环型结构特点时，就特别适合采用循环链表，循环链表的结构如图所示

 

2.3.3：双向链表

单向链表只有一个方向，结点只有一个后继指针 next 指向后面的结点。而双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针 next 指向后面的结点，还有一个前驱指针 prev 指向前面的结点，如图所示

 

从图中可以看出来，双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历，这样也带来了双向链表操作的灵活性。

2.3.4：双向循环链表

了解了循环链表和双向链表，如果把这两种链表整合在一起就是一个双向循环链表

 

2.4：链表和数组性能比较

通过前面内容的学习，你应该已经知道，数组和链表是两种截然不同的内存组织方式。正是因为内存存储的区别，它们插入、删除、随机访问操作的性能正好相反数组简单易用，在实现上使用的是连续的内存空间,缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。

链表本身没有大小的限制，天然地支持动态扩容，我觉得这也是它与数组最大的区别。你可能会说，我们 Java 中的 ArrayList 容器，也可以支持动态扩容啊？我们上一节课讲过，当我们往支持动态扩容的数组中插入一个数据时，如果数组中没有空闲空间了，就会申请一个更大的空间，将数据拷贝过去，而数据拷贝的操作是非常耗时的。

所以：数组的优势是查询速度非常快，但是增删改慢；链表的优势是增删改快，但是查询慢。

2.5：面试题

⑴、LinkedList 和 ArrayList 的比较

前面我们分析过 ArrayList 的源码，现在又分析了 LinkedList 源码，接下来将二者进行比较：

1：ArrayList 的实现基于数组，LinkedList 的实现基于双向链表

2：对于随机访问，ArrayList 优于 LinkedList，ArrayList 可以根据下标对元素进行随机访问。而 LinkedList 的每一个元素都依靠地址指针和它后一个元素连接在一起，在这种情况下，查找某个元素只能从链表头开始查询直到找到为止

3：对于插入和删除操作，LinkedList 优于 ArrayList，因为当元素被添加到LinkedList 任意位置的时候，不需要像 ArrayList 那样重新计算大小或者是更新索引。

4：LinkedList 比 ArrayList 更占内存，因为 LinkedList 的节点除了存储数据，还存储了两个引用，一个指向前一个元素，一个指向后一个元素。

⑵、反转单链表

 

public class Li
    stNode {
    int val;
    ListNode next;
​
    ListNode(int x) {
        val = x;
    }
}
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null; //前指针节点
        ListNode curr = head; //当前指针节点
        //每次循环，都将当前节点指向它前面的节点，然后当前节点和前节点后移
        while (curr != null) {
            ListNode nextTemp = curr.next; //临时节点，暂存当前节点的下一节点，用于后移
            curr.next = prev; //将当前节点指向它前面的节点
            prev = curr; //前指针后移
            curr = nextTemp; //当前指针后移
        }
        return prev;
    }
}

3.栈

3.1：概念

关于“栈”这种数据结构，它有一个典型的特点：先进后出，后进先出；只要满足这种特点的数据结构我们就可以说这是典型的“栈”数据结构，我们一般将这个特点归纳为一个：后进先出,英文表示为：Last In First Out 即 LIFO。为了更好的理解栈这种数据结构，我们以一幅图的形式来表示，如下：

 

我们从栈的操作特点上来看，似乎受到了限制，的确，栈就是一种操作受限的线性表，只允许在栈的一端进行数据的插入和删除，这两种操作分别叫做入栈和出栈。当某个数据集合如果只涉及到在其一端进行数据的插入和删除操作，并且满足先进后出，后进先出的特性时，我们应该首选栈这种数据结构来进行数据的存储。

3.2：栈的实现

从对栈的定义中我们发现栈主要包含两个操作，入栈和出栈，也就是在栈顶插入一个元素和在栈底删除一个元素，那理解了这个定义之后，我们来思考一个问题，如何来手动实现一个栈呢？

实际上，栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈叫顺序栈，用链表实现的叫链式栈。接下来我们就这两种形式分别去实现一下。

支持动态扩容的顺序栈

public class ArrayStack {
    // 栈大小
    private int size;
    // 默认栈容量
    private int DEFAULT_CAPACITY = 10;
    // 栈数据
    private Object[] elements;
​
    private int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
​
    /**
     * 默认构造创建大小为 10 的栈
     */
    public ArrayStack() {
        elements = new Object[DEFAULT_CAPACITY];
    }
​
    /**
     * 通过指定大小创建栈
     *
     * @param capacity
     */
    public ArrayStack(int capacity) {
        elements = new Object[capacity];
    }
​
    /**
     * 入栈
     *
     * @param element
     * @return
     */
    public boolean push(Object element) {
        try {
            checkCapacity(size + 1);
            elements[size++] = element;
            return true;
        } catch (RuntimeException e) {
            return false;
        }
    }
​
    /**
     * 检查栈容量是否还够
     */
    private void checkCapacity(int minCapacity) {
        if (elements.length - minCapacity < 0) {
            //throw new RuntimeException("栈容量不够!");
            grow(elements.length);
        }
    }
​
    /**
     * 扩容
     *
     * @param oldCapacity 原始容量
     */
    private void grow(int oldCapacity) {
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - oldCapacity < 0) {
            newCapacity = DEFAULT_CAPACITY;
        }
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            newCapacity = hugeCapacity(newCapacity);
        }
        elements = Arrays.copyOf(elements, newCapacity);
    }
​
    private int hugeCapacity(int newCapacity) {
​
        return (newCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : newCapacity;
    }
​
    /**
     * 出栈
     *
     * @return
     */
    public Object pop() {
        if (size <= 0) {
            return null;//栈为空则直接返回 null
        }
        Object obj = elements[size - 1];
        elements[--size] = null;
        return obj;
    }
​
    /**
     * 获取栈的大小
     *
     * @return
     */
    public int size() {
        return size;
    }
​
}

添加测试代码如下：

public class ArrayStackTest {
    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack(5);
        for (int i = 0; i < 40; i++) {
            boolean push = stack.push(i);
            System.out.println("第" + (i + 1) + "次存储数据为:" + i + ",存储结果是: " + push);
        }
        // stack.push(1);
        for (int i = 0; i < 11; i++) {
            Object pop = stack.pop();
            System.out.println(pop);
        }
    }
}

基于链表的链式栈

public class StackBasedOnLinkedList {
    // 存储链表头节点
    private Node head;
​
    public StackBasedOnLinkedList() {
        this.head = null;
    }
​
    /**
     * 入栈
     *
     * @param data
     * @return
     */
    public boolean push(Object data) {
        Node newNode = new Node(data, head);
        head = newNode;
        return true;
    }
​
    /**
     * 出栈
     *
     * @return
     */
    public Object pop() {
        if (head == null) {
            return null;
        }
        Node topNode = head;
        head = topNode.next;
        topNode.next = null;
        return topNode.data;
    }
​
    /**
     * 节点对象
     */
    private static class Node {
        //节点数据
        private Object data;
        // next 指针
        private Node next;
​
        public Node(Object data, Node next) {
            this.data = data;
            this.next = next;
        }
​
        public Object getData() {
            return data;
        }
    }
}

​

添加测试代码如下：

public class TestStackBasedOnLinkedList {
    public static void main(String[] args) {
        StackBasedOnLinkedList stack = new StackBasedOnLinkedList();
        for (int i = 0; i < 6; i++) {
            stack.push(i + "");
            System.out.println("第" + (i + 1) + "次入栈,入栈的值为:" + i);
        }
​
        for (int i = 0; i < 8; i++) {
            Object pop = stack.pop();
            System.out.println("取出的结果:" + pop);
        }
    }
}

​

4.队列

4.1：概念

队列的概念非常容易理解，我们拿日常生活中的一个场景来举例说明，我们去车站的窗口买票，那就要排队，那先来的人就先买，后到的人就后买，先来的人排到队头，后来的人排在队尾，不允许插队，先进先出，这就是典型的队列。 队列先进先出的特点英文表示为：First In First Out 即 FIFO,为了更好的理解队列这种数据结构，我们以一幅图的形式来表示，并且我们将队列的特点和栈进行比较，如下：

 

从图中我们可以发现，队列和栈一样都属于一种操作受限的线性表，栈只允许在一端进行操作，分别是入栈 push()和出栈 pop()，而队列跟栈很相似，支持的操作也有限，最基本的两个操作一个叫入队列 enqueue()，将数据插入到队列尾部，另一个叫出队列 dequeue()，从队列头部取出一个数据。

队列的概念很好理解，基本操作也很容易掌握。作为一种非常基础的数据结构，队列的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存都用到了循环并发队列，在 java 中，concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。

4.2：常见队列及实现

4.2.1：顺序队列的实现

 

跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的栈叫作顺序栈，用链表实现的栈叫作链式栈。同样，用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。

对于栈来说，我们只需要一个栈顶指针就可以了。但是队列需要两个指针(数组下标)：一个是 head 指针，指向队头；一个是 tail 指针，指向队尾。每一次元素入队列操作，我们的 tail 指针就需要向后移动一位；每一次出队列操作，我们的 head指针就要向后移动一位。

但是当 tail 指针移动到数组末尾之后，由于入队列操作都是从数组尾部存入数据，那此时数组尾部已不能在插入数据了，我们就要根据情况采取不同的措施，第一种情况是数组中已经没有位置可以存储数据了那就要对数组进行扩容，第二种情况是数组中还有位置可以存储数据，只不过是数组尾端已不能再插入数据了，那此时就要将数组中的数据依次向前挪动，将数组尾部的位置空出来供入队列操作。

下面进行代码实现：

public class ArrayQueue {
    // 存储数据的数组
    private Object[] elements;
    //队列大小
    private int size;
    // 默认队列容量
    private int DEFAULT_CAPACITY = 10;
    // 队列头指针
    private int head;
    // 队列尾指针
    private int tail;
​
    private int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
​
    /**
     * 默认构造函数 初始化大小为 10 的队列
     */
    public ArrayQueue() {
        elements = new Object[DEFAULT_CAPACITY];
        initPointer(0, 0);
    }
​
    /**
     * 通过传入的容量大小创建队列
     *
     * @param capacity
     */
    public ArrayQueue(int capacity) {
        elements = new Object[capacity];
        initPointer(0, 0);
    }
​
    /**
     * 初始化队列头尾指针
     *
     * @param head
     * @param tail
     */
    private void initPointer(int head, int tail) {
        this.head = head;
        this.tail = tail;
    }
​
    /**
     * 元素入队列
     *
     * @param element
     * @return
     */
    public boolean enqueue(Object element) {
        ensureCapacityHelper();
        elements[tail++] = element;//在尾指针处存入元素且尾指针后移
        size++;//队列元素个数加 1
        return true;
    }
​
    private void ensureCapacityHelper() {
        if (tail == elements.length) {//尾指针已越过数组尾端
            //判断队列是否已满 即判断数组中是否还有可用存储空间
            //
            if (size < elements.length) {
                if (head == 0) {
                    //扩容
                    grow(elements.length);
                } else {
                    //进行数据搬移操作 将数组中的数据依次向前挪动直至顶部
                    for (int i = head; i < tail; i++) {
                        elements[i - head] = elements[i];
                    }
                    //数据搬移完后重新初始化头尾指针
                    initPointer(0, tail - head);
                }
            }
        }
    }
​
    /**
     * 扩容
     *
     * @param oldCapacity 原始容量
     */
    private void grow(int oldCapacity) {
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - oldCapacity < 0) {
            newCapacity = DEFAULT_CAPACITY;
        }
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            newCapacity = hugeCapacity(newCapacity);
        }
        elements = Arrays.copyOf(elements, newCapacity);
    }
​
    private int hugeCapacity(int newCapacity) {
        return (newCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : newCapacity;
    }
​
    /**
     * 出队列
     *
     * @return
     */
    public Object dequeue() {
        if (head == tail) {
            return null;//队列中没有数据
        }
        Object obj = elements[head++];//取出队列头的元素且头指针后移
        size--;//队列中元素个数减 1
        return obj;
    }
​
    /**
     * 获取队列元素个数
     *
     * @return
     */
    public int getSize() {
        return size;
    }
}

4.2.2：链式队列的实现

我们知道队列是先进先出的，对于链表，我们能采用单链表尽量采用单链表，能方便尽量方便，同时还要兼顾效率。

• 方案一 如果队头设在链表尾，队尾设在链表头。那么队尾进队插入在链表头部插入没问题。容易实现，但是如果队头删除在尾部进行，如果不设置尾指针要遍历到队尾，但是设置尾指针删除需要将它指向前驱节点那么就需要双向链表。都挺麻烦的。

• 方案二 但是如果队头设在链表头，队尾设在链表尾部，那么队尾进队插入在链表尾部插入没问题(用尾指针可以直接指向next)。容易实现，如果队头删除在头部进行也很容易，就是我们前面常说的头节点删除节点。

• 所以我们最终采取的是方案2的带头节点，带尾指针的单链表!

 

 

下面进行代码实现：

public class LinkedListQueue {
    //队列元素个数
    private int size;
    //头节点
    private Node head;
    //尾节点
    private Node tail;
​
    public LinkedListQueue() {
        this.head = null;
        this.tail = null;
    }
​
    /**
     * 入队列
     *
     * @param data
     * @return
     */
    public boolean enqueue(Object data) {
        Node newNode = new Node(data, null);
        if (tail == null) {
            tail = newNode;
            head = newNode;
        } else {
            tail.next = newNode;
            tail = newNode;
        }
        size++;
        return true;
    }
​
    /**
     * 出队列
     *
     * @return
     */
    public Object dequeue() {
        if (head == null) {
            return null;
        }
        Object data = head.data;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        size--;
        return data;
    }
​
​
    private static class Node {
        //节点数据
        private Object data;
        //后继节点
        private Node next;
​
        public Node(Object data, Node next) {
            this.data = data;
            this.next = next;
        }
    }
​
    public int getSize() {
        return size;
    }
}