前言

本文收录于专辑：http://dwz.win/HjK，点击解锁更多数据结构与算法的常识。

你好，我是彤哥，一个每天爬二十六层楼还不忘读源码的硬核男人。

数组、链表、队列、栈，是数据结构中最根底的四大构造，数组和链表更是根底中的根底，后续所有简单的数据结构都是在它们的根底上演变而来的。

本节，咱们就来重温这四大构造。

数组

对于数组，大家都比拟相熟了。

它是一种线性数据结构，应用一组间断的内存空间存储一组具备雷同类型的数据。

这个概念中有三个关键词：线性、间断、雷同类型。

线性，示意没有分叉，任意元素的前后元素最多只有一个，同样是线性构造的还有链表、队列等。

间断，它在内存空间中的存储是间断的，不间断的，前后两个元素紧挨着，不存在间隙。

雷同类型，数组中存储的元素的类型肯定是雷同的，当然，在Java中，你能够应用Object代表所有类型，实质上，它们仍然是雷同类型。

正是有了下面三个个性，才使得数组具备了随机拜访的个性，那么，什么是随机拜访呢？

简略点说，你能够通过下标疾速定位到数组中的元素，且工夫复杂度是O(1)，它是怎么做到的呢？

咱们晓得，计算机中只有0和1，所有的所有都能够看作是0和1的各种组合，内存也是一样。

当咱们创立一个数组，比方int[] array = new int[]{2, 5, 8, 7};时，它其实返回的是这个数组在内存中的地位（地址），咱们晓得，一个int类型占用4个字节，也就是32位的0或1，当咱们拜访数组下标为0的元素时，间接返回数组地址处取32位转成int即可，同样地，当咱们拜访数组下标为1的元素时，返回数组地址加上(32*1)的地址处取32位转成int，依此类推。

这也是大部分语言中数组下标从0开始的起因，试想如果下标从1开始，那么，计算内存地址的时候就变成了address + 32 * (i - 1)，这显然会造成肯定的性能损耗。

链表

链表，它也是一种线程数据结构，与数组不同的是，它在内存空间中不肯定是顺序存储的，为了保障链表中元素的连续性，个别应用一个指针来找到下一个元素。

上图是典型的单链表构造，在单链表中，只有一个指向下一个元素的指针。

如果要用Java类来示意单链表中的元素节点的话，大略看起来像这样子：

class Node {    int value;    Node next;}

所以，链表不具备随机拜访的个性，在链表中依据索引来查找元素只能从头开始（单链表），它的工夫复杂度是O(n)。

下面咱们说的是单链表，如果在单链表的根底上再减少一个前驱指针（指向前一个元素的指针），就变成了双向链表。

Java中的LinkedList就是典型的双向链表构造，双向链表既能够当作队列应用，又能够当作栈来应用，十分不便。

如果在双向链表的根底上再减少HashMap的性能，就变成了LinkedHashMap了，咳咳，扯远了。

心愿学习LinkedList和LinkedHashMap源码解析的同学，能够关注我的公号主“彤哥读源码”。

这里提到了队列，那么，什么是队列呢？

队列

所谓队列，其实跟事实中的排队是一样的，其中的元素从一端进入，从另一端进来，英文叫做：First In，First Out，简写FIFO。

从这张图，也能够看进去，实现队列最简略的形式就是应用链表，把上图中的箭头倒过去即可。

入队时，将元素退出到链表尾端，出队时，将第一个元素删除并将头节点指向下一个节点即可。

让咱们来看看应用链表实现队列的简略代码实现：

public class LinkedQueue {    Node head;    Node tail;    void offer(Integer value) {        if (value == null) {            throw new NullPointerException();        }        Node node = new Node(value);        if (head == null) {            head = tail = node;        } else {            tail.next = node;            tail = node;        }    }    Integer poll() {        Node first = head;        if (first != null) {            head = first.next;            first.next = null;            return first.value;        } else {            return null;        }    }    static class Node {        int value;        Node next;        public Node(int value) {            this.value = value;        }    }}

是不是很简略呢？

那么，数组能不能实现队列呢？

答案是必定的，应用数组实现队列有很多种形式，其中一种是应用两个指针：入指针、出指针，它们别离指向下一个入队列和下一个出队列的地位。

入队时，在入指针处放入元素，同时入指针后移。

出队时，取出出指针处的元素返回，同时出指针后移。

当指针达到数组开端时，返回数组开始的地位。

这样就造成了一个能够循环应用的数组，俗称环形数组。

此时，咱们思考一个问题，队列空和队列满时，两个指针都是指向同一个地位，仿佛不太好解决。

其实，很简略，引入一个size变量标识队列中有多少个元素即可。

所以，这玩意儿要怎么实现呢？Show me the code!

public class ArrayQueue {    int[] array;    int offerIndex;    int pollIndex;    int size;    public ArrayQueue(int capacity) {        this.array = new int[capacity];        this.offerIndex = this.pollIndex = 0;        this.size = 0;    }    boolean offer(Integer value) {        if (value == null) {            throw new NullPointerException();        }        if (size == array.length) {            return false;        }        array[offerIndex] = value;        offerIndex = (offerIndex + 1) % array.length;        size++;        return true;    }    Integer poll() {        if (size == 0) {            return null;        }        int value = array[pollIndex];        pollIndex = (pollIndex + 1) % array.length;        size--;        return value;    }}

OK，以上就是应用数组实现的队列，能够看到，与链表实现的队列相比，它须要指定容量，这叫做有界队列，如果须要应用数组实现无界队列，则须要退出扩容的机制，有趣味的同学能够本人实现看看。

上面，咱们再来看另一种根底的数据结构——栈。

栈

栈，它是与队列体现齐全相同的数据结构，它的元素是先进的后进去，就像咱们往一个杯子外面放货色一样，先放进去的放在最上面，只有把下面的货色拿进去后能力拿出上面压着的货色，这种行为用英文叫做：First In，Last Out，简称FILO。

栈，具备很多用途，计算机中很多解决都是通过栈这种数据结构来进行的，比方算术运算，筹备两个栈，一个栈存储数字，一个栈存储符号，从头开始顺次把字符压入到这两个栈中，当遇到符号优先级比栈顶元素低时，则取出栈顶符号，并从数字栈中取出两个数字进行运算，运算的后果再压回数字栈中，持续以此运行，当所有字符都放入栈之后，顺次从数字栈中取出两个元素，并从符号栈中取出一个元素，进行计算，后果压回数字栈，持续以此运行，直到符号栈为空，或者数字栈只剩下一个元素为止，弹出这个数字即为最初的后果。

以3 + 2 * 4 -1为例：

好了，对于栈，咱们就简略介绍到这里，前面，咱们还会大量遇到这个数据结构。

后记

本节，咱们一起重温了数组、链表、队列、栈这四种最根底的数据结构。

说起数组，咱们看到，内存自身就是一张大数组，它外面的元素就是0和1，那么，咱们能不能间接操作这些0和1呢？

答案是必定的。

下一节，咱们将介绍位运算，以及位图这种数据结构，彼时，咱们将具体介绍如何应用位图来实现12306的抢票逻辑，关注我，及时获取最新推文。

关注公号主“彤哥读源码”，解锁更多源码、根底、架构常识。