基本数据结构

栈（Stack）

栈是一种用于存储数据的简单数据结构，有点类似链表或者顺序表（统称线性表），栈与线性表的最大区别是数据的存取的操作，我们可以这样认为栈(Stack)是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行，一般而言，把允许操作的一端称为栈顶(Top)，不可操作的一端称为栈底(Bottom)，同时把插入元素的操作称为入栈(Push),删除元素的操作称为出栈(Pop)。若栈中没有任何元素，则称为空栈。

image-20210728163713795

一般情况下，栈使用数组来实现，通过一个指向栈顶索引值的整形数字来表示栈的状态。当然，也有通过链表实现栈结构的方式，称之为链栈。

在Java中，Stack继承自Vector。栈一般用于保存上下文，例如在方法调用过程中参数的保存。

image-20210728164234077

栈是一种很重要的数据结构，在计算机中有着很广泛的应用，如下一些操作都应用到了栈。

  • 符号匹配
  • 中缀表达式转换为后缀表达式
  • 计算后缀表达式
  • 实现函数的嵌套调用
  • HTML和XML文件中的标签匹配
  • 网页浏览器中已访问页面的历史记录

相对于数组、链表、散列表，栈在实际工作中使用的频率要少很多，但它在计算机的一些理论和模型中，有着十分重要的作用。

数组（Array）

数组（Array） 是日常工作中使用最多的数据结构之一。它是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

image-20210728165956104

线性表（Linear List） 就是数据排成像一条线一样的结构。每个线性表上的数据最多只有两个方向。除了数组，像链表、队列、栈也是线性表结构，而树、图等为非线性表结构。

在数组中，数据根据下标随机访问的时间复杂度为 O(1)，速度很快。而数据的插入和删除很低效：

  • 如果删除数组末尾的数据，最好情况时间复杂度为 O(1)
  • 如果删除开头的数据，则最坏情况时间复杂度为 O(n)
  • 平均情况时间复杂度也为 O(n)。

在Java语言中，可以通过下面的方式声明数组。java.util.Arrays工具类提供了一些基本的数组操作的方法。

1
2
3

String[] strings = new String[100];
Arrays.fill(strings, "XXXX");
Arrays.sort(strings);

ArrayList 类是一个可以动态修改的数组，与普通数组的区别就是它是没有固定大小的限制，我们可以添加或删除元素。其能够动态扩容的原理在于，它自动实现了一个扩容的机制，当发现数组容量不够时，会自动进行扩容，并将原有的数据拷贝到新分配的数组中。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
	// overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
    	newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
    	newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

链表（Linked List）

链表（Linked List) 是一种物理存储结构上非连续，非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

image-20210728171909728

链表有许多变形，例如双向链表、循环链表、带头循环双向链表等。

链表的优点主要表现为：

  • 插入和删除的效率高，只需要改变指针的指向就可以进行插入和删除。
  • 内存利用率高，不会浪费内存，可以使用内存中细小的不连续的空间，只有在需要的时候才去创建空间。大小不固定，拓展很灵活。

链表的缺点也很明显：

  • 查找的效率低，因为链表是从第一个节点向后遍历查找。

在java中，使用LinkedList来表示链表，其链表节点定义如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;

    /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

    /**
     * Constructs an empty list.
     */
    public LinkedList() {
    }

    //........ 
    
    // LinkedList中节点类型的定义
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
    
    //...........

堆（Heap）

堆（Heap） 就是用数组实现的完全二叉树。就是说，一个结点通常会有左，右孩子结点指针和父结点指针。但在完全二叉树中，是可以省略掉这三个指针的，因为完全二叉树的结点编号都是有规律的。给定某一个结点，假设它的下标为i，那么它的左孩子结点的下标就是2i + 1，右孩子结点的下标就是2i + 2，它的父结点为(i−1)/2。这样，我们就把可以省略去这些指针，直接将堆中的结点存储在数组中了。

image-20210728173855825

堆又分为最大堆（大根堆） 和 最小堆（小根堆）。堆的性质非常简单，如果是最大堆，对于每个结点，都有结点的值大于两个孩子结点的值。如果是最小堆，那么对于每个结点，都有结点的值小于孩子结点的值。由此，可以得到一个推论，那就是，最大堆的根结点，必然是堆中的最大值，同理，最小堆的根结点，也必然是堆中的最小值。

堆的常用方法一般包括下面一些：

  • 构建优先队列
  • 支持堆排序
  • 快速找出一个集合中的最小值（或者最大值）

在Java中，类PriorityQueue就是根据堆的性质实现的一个优先队列。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(67);
pq.add(35);
pq.add(65);
pq.add(88);

Integer peek = pq.peek();
System.out.println(peek);

// 输出35

下面是PriorityQueue的源代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {

    private static final long serialVersionUID = -7720805057305804111L;

    private static final int DEFAULT_INITIAL_CAPACITY = 11;

    /**
     * Priority queue represented as a balanced binary heap: the two
     * children of queue[n] are queue[2*n+1] and queue[2*(n+1)].  The
     * priority queue is ordered by comparator, or by the elements'
     * natural ordering, if comparator is null: For each node n in the
     * heap and each descendant d of n, n <= d.  The element with the
     * lowest value is in queue[0], assuming the queue is nonempty.
     */
    transient Object[] queue; 
    
    .....

队列（Queue）

队列(Queue) 是线性表的一种，在操作数据元素时，和栈一样，有自己的规则：使用队列存取数据元素时，数据元素只能从表的一端进入队列，另一端出队列

优先队列（Priority Queue）

循环队列（Circlue Queue）

字符串（String）

KMP算法

Rabin-Karp算法

排序

冒泡/选择/归并

堆排序*

快速排序*

散列表