线性数据结构

数组

定义

数组（Array）是一种常见的数据结构，用于存储相同类型的元素，并且这些元素在内存中是连续存储的。通过索引（Index）可以直接访问数组中的任意元素。

特点

1. 连续内存：数组的元素存储在连续的内存块中。
2. 相同类型：数组中的所有元素必须是相同的数据类型。
3. 随机访问：由于连续存储，数组支持通过索引直接访问元素，时间复杂度为 ( O(1) )。
4. 容量固定：数组的大小在创建时确定，不能动态调整。

时间复杂度分析

• 访问：通过索引访问数组中的元素时间复杂度为 ( O(1) )，因为内存地址可以通过公式直接计算：
  [
  \text{Address} = \text{Base Address} + (\text{Index} \times \text{Element Size})
  ]
• 插入：
  • 最好情况：插入到数组尾部，无需移动元素，时间复杂度为 ( O(1) )。
  • 最坏情况：插入到数组首部，需要移动所有元素，时间复杂度为 ( O(n) )。
• 删除：
  • 最好情况：删除数组尾部的元素，无需移动其他元素，时间复杂度为 ( O(1) )。
  • 最坏情况：删除数组首部的元素，需要移动后续所有元素，时间复杂度为 ( O(n) )。

示例代码

以下是一个简单的 Java 示例，展示数组的基本操作：

public class ArrayExample {
    public static void main(String[] args) {
        // 创建数组
        int[] array = {10, 20, 30, 40, 50};

        // 访问元素
        System.out.println("访问第三个元素: " + array[2]); // 输出: 30

        // 插入元素（创建新数组模拟插入）
        int[] newArray = new int[array.length + 1];
        System.arraycopy(array, 0, newArray, 0, 2); // 复制前两个元素
        newArray[2] = 25; // 插入新元素
        System.arraycopy(array, 2, newArray, 3, array.length - 2); // 复制剩余元素
        System.out.println("插入后数组: " + java.util.Arrays.toString(newArray));

        // 删除元素（创建新数组模拟删除）
        int[] smallerArray = new int[array.length - 1];
        System.arraycopy(array, 0, smallerArray, 0, 2); // 复制前两个元素
        System.arraycopy(array, 3, smallerArray, 2, array.length - 3); // 跳过要删除的第三个元素
        System.out.println("删除后数组: " + java.util.Arrays.toString(smallerArray));
    }
}

应用场景

• 用于需要快速随机访问的场景，例如表格数据。
• 常作为底层实现其他数据结构的基础，例如哈希表、栈、队列等。

通过数组的简单分析，我们可以清楚它的高效访问能力和对插入删除操作的限制，这也是在实际开发中选择合适数据结构的关键依据。

链表

简介

链表（LinkedList）是一种动态数据结构，不使用连续内存存储数据，而是通过节点（Node）和指针（Pointer）组成。每个节点包含数据部分和指向下一个节点（或上一个节点）的指针部分。

特点

1. 动态内存分配：链表大小不固定，可根据需要动态扩展。
2. 插入与删除高效：插入或删除操作只需要调整指针，不需要移动其他元素，时间复杂度为 ( O(1) )。
3. 访问效率较低：链表不支持随机访问，要访问特定位置的元素需要从头节点遍历，时间复杂度为 ( O(n) )。
4. 额外空间开销：由于存储指针信息，链表占用的内存空间比数组更多。

链表分类

1. 单链表

• 结构：节点包含数据部分和指向后继节点的指针。
• 特点：
  • 单向遍历，每个节点只能访问后继节点。
  • 尾节点的指针指向 null。
• 操作复杂度：
  • 插入、删除：( O(1) )（需要先定位到目标位置）。
  • 查找：( O(n) )。

Java 实现：

class Node {
    int data;
    Node next;
    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class SinglyLinkedList {
    Node head; // 头节点

    // 插入节点到链表头部
    public void insertAtHead(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    // 打印链表
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

2. 循环链表

• 结构：尾节点的指针指向头节点，形成闭环。
• 特点：
  • 适合需要循环遍历的场景。
  • 操作逻辑类似单链表，但要额外注意处理尾节点的指针。

3. 双向链表

• 结构：每个节点包含三个部分：数据部分、指向前驱节点的指针 prev 和指向后继节点的指针 next。
• 特点：
  • 支持从任意节点双向遍历。
  • 插入和删除操作更灵活。
  • 比单链表占用更多内存。

Java 实现：

class DoublyNode {
    int data;
    DoublyNode prev, next;
    DoublyNode(int data) {
        this.data = data;
        this.prev = this.next = null;
    }
}

public class DoublyLinkedList {
    DoublyNode head, tail;

    // 插入节点到链表尾部
    public void insertAtTail(int data) {
        DoublyNode newNode = new DoublyNode(data);
        if (tail == null) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
    }

    // 打印链表从头到尾
    public void printForward() {
        DoublyNode current = head;
        while (current != null) {
            System.out.print(current.data + " <-> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

4. 双向循环链表

• 结构：双向链表的扩展，尾节点的 next 指向头节点，头节点的 prev 指向尾节点。
• 特点：适用于需要频繁循环遍历和双向操作的场景。

---

数组与链表对比

特性	数组	链表
内存布局	连续内存	不连续，通过指针连接
访问效率	( O(1) ) 随机访问	( O(n) ) 需遍历
插入与删除	( O(n) ) 需要移动元素	( O(1) ) 调整指针即可
空间开销	仅存储数据	需额外存储指针，开销较大
扩展能力	固定大小，需重新分配内存	动态扩展，灵活性更高

---

应用场景

• 链表：适用于数据量动态变化、不需要随机访问、频繁插入和删除操作的场景。

  • 实现栈、队列、图的邻接表等数据结构。
  • 适合处理大量动态数据，如操作系统中的内存管理。

• 数组：适用于数据量固定或变化较少、需要高效随机访问的场景。

  • 数组在实现查找、排序等算法时性能更优。

栈

3.1 栈简介

栈（Stack）是一种线性数据结构，只允许在一端（栈顶）进行数据的插入（Push）和删除（Pop）操作，遵循**后进先出（LIFO, Last In First Out）**原则。

特点

1. 操作限制：仅允许从栈顶操作。
2. 实现方式：可以基于数组（顺序栈）或链表（链式栈）。
3. 时间复杂度：
   • 访问：( O(n) )（最坏情况需要遍历所有元素）。
   • 插入与删除：( O(1) )（只在栈顶操作）。

---

3.2 栈的常见应用场景

3.2.1 实现浏览器的回退和前进功能

利用两个栈（stack1 和 stack2）存储已访问页面和回退页面：

• 回退：从 stack1 弹出页面，压入 stack2。
• 前进：从 stack2 弹出页面，压入 stack1。

3.2.2 检查符号是否成对出现

通过栈检查括号是否匹配：

• 遇到左括号入栈。
• 遇到右括号时，栈顶元素与当前括号匹配则弹栈，否则返回不匹配。

示例代码：

public boolean isValid(String s) {
    Map<Character, Character> mappings = Map.of(')', '(', '}', '{', ']', '[');
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray()) {
        if (mappings.containsKey(c)) {
            char top = stack.isEmpty() ? '#' : stack.pop();
            if (top != mappings.get(c)) return false;
        } else {
            stack.push(c);
        }
    }
    return stack.isEmpty();
}

3.2.3 反转字符串

利用栈实现字符串反转：

• 将字符依次压栈。
• 再依次弹栈，构成反转后的字符串。

3.2.4 维护函数调用

栈用于记录递归调用的上下文：

• 每次函数调用会将当前状态压栈。
• 函数返回时，从栈顶恢复状态。

3.2.5 深度优先遍历（DFS）

在图或树的深度优先搜索中，使用栈记录访问路径，用于回溯到上一级。

---

3.3 栈的实现

基于数组的栈实现

以下是一个简单的数组实现的栈，支持常见的操作：

• push()：入栈。
• pop()：出栈并返回栈顶元素。
• peek()：返回栈顶元素但不出栈。
• isEmpty()：检查栈是否为空。
• size()：返回栈中元素的个数。

import java.util.Arrays;

public class MyStack {
    private int[] storage;
    private int capacity;
    private int count;
    private static final int GROW_FACTOR = 2;

    // 默认构造函数
    public MyStack() {
        this(8); // 默认容量为8
    }

    // 带初始容量的构造函数
    public MyStack(int initialCapacity) {
        if (initialCapacity < 1) throw new IllegalArgumentException("Capacity too small.");
        this.capacity = initialCapacity;
        this.storage = new int[initialCapacity];
        this.count = 0;
    }

    // 入栈
    public void push(int value) {
        if (count == capacity) ensureCapacity();
        storage[count++] = value;
    }

    // 出栈
    public int pop() {
        if (count == 0) throw new IllegalArgumentException("Stack is empty.");
        return storage[--count];
    }

    // 查看栈顶元素
    public int peek() {
        if (count == 0) throw new IllegalArgumentException("Stack is empty.");
        return storage[count - 1];
    }

    // 判断是否为空
    public boolean isEmpty() {
        return count == 0;
    }

    // 获取栈中元素个数
    public int size() {
        return count;
    }

    // 扩容
    private void ensureCapacity() {
        capacity *= GROW_FACTOR;
        storage = Arrays.copyOf(storage, capacity);
    }
}

验证代码

public static void main(String[] args) {
    MyStack stack = new MyStack(3);
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);

    System.out.println("栈顶元素: " + stack.peek()); // 输出: 4
    System.out.println("栈大小: " + stack.size()); // 输出: 4

    while (!stack.isEmpty()) {
        System.out.println("弹出: " + stack.pop());
    }
    System.out.println("栈是否为空: " + stack.isEmpty()); // 输出: true
}

---

3.4 数组栈 vs 链表栈

特性	数组栈	链表栈
实现	使用连续数组存储数据	使用链表存储数据
扩容	需要重新分配内存，耗时较大	动态内存分配，扩展方便
空间利用	更节省内存	需要额外存储指针，开销更大
操作复杂度	( O(1) )	( O(1) )
使用场景	数据量较小且固定	数据量动态变化，扩展性更好

栈是一种功能单一但应用广泛的数据结构，其基于 LIFO 的特性在算法、系统和程序设计中都有重要地位。

队列

4.1 队列简介

队列（Queue）是一种**先进先出（FIFO, First In, First Out）**的线性数据结构，只允许在队尾（rear）插入数据（enqueue），在队头（front）移除数据（dequeue）。它可以基于数组（顺序队列）或链表（链式队列）实现。

特点

1. FIFO 特性：最早进入队列的元素最先被移除。
2. 操作位置固定：插入操作在队尾，删除操作在队头。
3. 时间复杂度：
   • 插入和删除：( O(1) )（在队尾插入或队头删除不需要额外遍历）。
   • 访问元素：( O(n) )（最坏情况下需遍历所有元素）。

---

4.2 队列分类

4.2.1 单队列

单队列是最基础的队列，分为顺序队列（数组实现）和链式队列（链表实现）。

• 问题：顺序队列可能出现假溢出问题，即数组未满但队尾指针到达数组末端，导致无法继续插入。
• 解决方案：循环队列。

4.2.2 循环队列

循环队列通过让队尾指针 rear 回绕到数组开头解决假溢出问题，形成头尾相接的逻辑结构。

• 满队列判断：(rear + 1) % QueueSize == front
• 空队列判断：front == rear
• 特点：高效利用内存，但需要注意指针的循环回绕处理。

4.2.3 双端队列（Deque）

双端队列支持在两端进行插入和删除操作，具有更高的灵活性。

• 典型操作：addFirst、addLast、removeFirst、removeLast。
• Java 中的 Deque 接口提供了双端队列的实现。

4.2.4 优先队列

优先队列（Priority Queue）按照元素的优先级进行操作：

• 入队：根据优先级插入元素。
• 出队：每次返回优先级最高的元素。
• 实现：常通过堆结构实现。

---

4.3 队列的常见应用场景

1. 阻塞队列：

   • 当队列为空时，出队操作阻塞。
   • 当队列满时，入队操作阻塞。
   • 常用于生产者-消费者模型。

2. 线程池任务队列：

   • 未处理的任务存放在队列中。
   • 支持无界队列（如 LinkedBlockingQueue）和有界队列（如 ArrayBlockingQueue）。

3. 广度优先搜索（BFS）：

   • 使用队列存储待访问的节点，按层次遍历图。

4. 消息队列：

   • 用于异步通信，消息按顺序存放并处理。

5. 现实场景：

   • 操作系统任务调度。
   • 客户排队服务。
   • 音乐播放器的播放列表。

---

4.4 队列的实现

基于数组的循环队列实现

以下是一个基于数组的循环队列实现，支持基础操作如入队、出队、检查队列是否满或为空。

public class CircularQueue {
    private int[] queue;
    private int front;
    private int rear;
    private int size;

    // 构造函数
    public CircularQueue(int capacity) {
        queue = new int[capacity + 1]; // 多留一个位置区分队满和队空
        front = 0;
        rear = 0;
        size = capacity + 1;
    }

    // 入队
    public boolean enqueue(int value) {
        if (isFull()) {
            return false; // 队列已满
        }
        queue[rear] = value;
        rear = (rear + 1) % size;
        return true;
    }

    // 出队
    public int dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("Queue is empty");
        }
        int value = queue[front];
        front = (front + 1) % size;
        return value;
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return front == rear;
    }

    // 判断队列是否为满
    public boolean isFull() {
        return (rear + 1) % size == front;
    }
}

验证代码

public static void main(String[] args) {
    CircularQueue queue = new CircularQueue(5);

    // 入队
    queue.enqueue(1);
    queue.enqueue(2);
    queue.enqueue(3);
    queue.enqueue(4);

    // 出队
    System.out.println(queue.dequeue()); // 输出: 1
    System.out.println(queue.dequeue()); // 输出: 2

    // 再次入队
    queue.enqueue(5);
    queue.enqueue(6);
    queue.enqueue(7); // 入队失败（队列满）

    // 依次出队
    while (!queue.isEmpty()) {
        System.out.println(queue.dequeue());
    }
}

---

4.5 队列 vs 栈

特性	队列	栈
操作原则	先进先出（FIFO）	后进先出（LIFO）
操作位置	队头出队，队尾入队	栈顶进栈、出栈
实现方式	链表、数组、循环队列	链表、数组
应用场景	BFS、任务调度、消息队列等	DFS、函数调用、反转等

队列是一种简单但功能强大的数据结构，特别适合需要按顺序处理数据的场景，广泛应用于各种计算机系统和算法中。