基本数据结构：数组、链表、栈、队列、哈希表

这一课你将能做到

1. 说出数组、链表、栈、队列、哈希表的核心特性和适用场景
2. 手写链表反转、栈模拟括号匹配、哈希表统计词频
3. 在判题中正确选择数据结构解决具体问题

为什么要学

这五种数据结构是编程世界的「积木」。数组是默认选择，链表解决动态插入，栈处理嵌套结构，队列保证公平顺序，哈希表实现极速查找。不会它们，就像厨师不会用刀。

人话：数组是连续停车位，链表是寻宝游戏（每个节点指向下一个），栈是叠盘子（后进先出），队列是排队买票（先进先出），哈希表是字典（拼音查字）。

先建立图像

数组:  [1][2][3][4][5]        ← 连续内存，下标直达
链表:  [1]→[2]→[3]→[4]→[5]   ← 指针串联，顺序访问
栈:    [3]← top               ← 后进先出 (LIFO)
       [2]
       [1]
队列:  [1]→[2]→[3]→[4]→[5]   ← 先进先出 (FIFO)
       front           rear
哈希表: key → hash → bucket   ← 键值对，O(1) 查找

跟着做

步骤 1：数组——最基础的结构

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 1, 9};
        Arrays.sort(arr);                    // 排序
        int idx = Arrays.binarySearch(arr, 8); // 二分查找
        System.out.println(Arrays.toString(arr)); // [1, 2, 5, 8, 9]
        System.out.println("8 在位置: " + idx);
    }
}

数组特点：查询 O(1)，插入删除 O(n)，大小固定。

步骤 2：链表——动态插入删除

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Main {
    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        
        // 反转链表
        ListNode prev = null, curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        
        // 输出: 3 -> 2 -> 1
        while (prev != null) {
            System.out.print(prev.val + " ");
            prev = prev.next;
        }
    }
}

链表特点：插入删除 O(1)，查询 O(n)，内存不连续。

步骤 3：栈——括号匹配

import java.util.Stack;

public class Main {
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if (c == ')' && top != '(') return false;
                if (c == ']' && top != '[') return false;
                if (c == '}' && top != '{') return false;
            }
        }
        return stack.isEmpty();
    }
    
    public static void main(String[] args) {
        System.out.println(isValid("()[]{}")); // true
        System.out.println(isValid("(]"));     // false
    }
}