5天速成数据结构与算法-Day3

线性数据结构

在计算机科学中，线性数据结构是最基础也最重要的数据组织方式。今天我们将深入探讨三种核心的线性结构：链表、栈和队列。理解它们的特性、实现方式与应用场景，是掌握更复杂算法的必经之路。

链表（Linked List）

介绍

链表是一种物理存储单元上非连续、非顺序的存储结构。它通过指针将一组零散的内存块串联起来，每个内存块称为节点（Node）。每个节点包含两部分：数据域和指针域。

与数组相比，链表的最大优势在于插入和删除操作的时间复杂度为O(1)（在已知前驱节点的情况下），且不需要预先分配固定大小的内存空间。但链表的缺点也很明显：无法像数组一样通过索引随机访问元素，查找特定元素需要从头遍历。

常见链表类型

• 单链表：每个节点只包含一个指向后继节点的指针
• 双链表：每个节点包含前驱和后继两个指针，支持双向遍历
• 循环链表：尾节点的指针指向头节点，形成环状结构

单链表基础实现

#include <iostream>
using namespace std;

// 定义链表节点
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

// 在链表头部插入节点
void insertAtHead(ListNode*& head, int val) {
    ListNode* newNode = new ListNode(val);
    newNode->next = head;
    head = newNode;
}

// 删除指定值的节点
void deleteNode(ListNode*& head, int val) {
    if (!head) return;
    
    if (head->val == val) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
        return;
    }
    
    ListNode* cur = head;
    while (cur->next && cur->next->val != val) {
        cur = cur->next;
    }
    
    if (cur->next) {
        ListNode* temp = cur->next;
        cur->next = cur->next->next;
        delete temp;
    }
}

// 打印链表
void printList(ListNode* head) {
    while (head) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "nullptr" << endl;
}

int main() {
    ListNode* head = nullptr;
    
    insertAtHead(head, 3);
    insertAtHead(head, 2);
    insertAtHead(head, 1);
    
    cout << "初始链表: ";
    printList(head);
    
    deleteNode(head, 2);
    cout << "删除节点2后: ";
    printList(head);
    
    return 0;
}

链表经典技巧：快慢指针

快慢指针是解决链表问题的利器。快指针每次走两步，慢指针每次走一步：

• 找中点：当快指针到达末尾时，慢指针正好在链表中间
• 判环：如果链表有环，快慢指针必定相遇
• 找倒数第K个节点：快指针先走K步，然后快慢指针同步前进

栈（Stack）

介绍

栈是一种后进先出（LIFO, Last In First Out）的线性数据结构。它只允许在一端（称为栈顶）进行插入和删除操作。生活中栈的例子比比皆是：一叠盘子、浏览器的后退按钮、函数调用的内存模型。

核心操作

• push：将元素压入栈顶
• pop：将栈顶元素弹出
• top/peek：查看栈顶元素，但不弹出
• isEmpty：判断栈是否为空

基于数组的栈实现

#include <iostream>
#include <vector>
using namespace std;

class Stack {
private:
    vector<int> data;

public:
    void push(int x) {
        data.push_back(x);
    }
    
    int pop() {
        if (isEmpty()) {
            throw runtime_error("Stack is empty");
        }
        int topVal = data.back();
        data.pop_back();
        return topVal;
    }
    
    int top() {
        if (isEmpty()) {
            throw runtime_error("Stack is empty");
        }
        return data.back();
    }
    
    bool isEmpty() {
        return data.empty();
    }
    
    int size() {
        return data.size();
    }
};

int main() {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);
    
    cout << "栈顶元素: " << s.top() << endl;
    cout << "弹出: " << s.pop() << endl;
    cout << "当前大小: " << s.size() << endl;
    
    return 0;
}

栈的经典应用：括号匹配

给定一个只包含括号的字符串，判断其是否合法。基本思路：遇到左括号就入栈，遇到右括号就与栈顶匹配，若匹配成功则出栈，最后栈为空则合法。

bool isValid(string s) {
    vector<char> stack;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push_back(c);
        } else {
            if (stack.empty()) return false;
            char top = stack.back();
            if ((c == ')' && top == '(') ||
                (c == ']' && top == '[') ||
                (c == '}' && top == '{')) {
                stack.pop_back();
            } else {
                return false;
            }
        }
    }
    return stack.empty();
}

队列（Queue）

介绍

队列是一种先进先出（FIFO, First In First Out）的线性数据结构。它只允许在一端（队尾）插入元素，在另一端（队头）删除元素。生活中的排队买票、打印任务调度、CPU进程调度都是队列的典型应用。

核心操作

• enqueue：在队尾插入元素
• dequeue：从队头移除元素
• front：查看队头元素
• isEmpty：判断队列是否为空

基于数组的循环队列实现

#include <iostream>
using namespace std;

class CircularQueue {
private:
    int* data;
    int front, rear;
    int capacity;
    int count;

public:
    CircularQueue(int k) {
        capacity = k;
        data = new int[k];
        front = 0;
        rear = -1;
        count = 0;
    }
    
    bool enqueue(int value) {
        if (count == capacity) return false;
        rear = (rear + 1) % capacity;
        data[rear] = value;
        count++;
        return true;
    }
    
    bool dequeue() {
        if (count == 0) return false;
        front = (front + 1) % capacity;
        count--;
        return true;
    }
    
    int Front() {
        if (count == 0) return -1;
        return data[front];
    }
    
    int Rear() {
        if (count == 0) return -1;
        return data[rear];
    }
    
    bool isEmpty() {
        return count == 0;
    }
    
    bool isFull() {
        return count == capacity;
    }
};

int main() {
    CircularQueue q(3);
    q.enqueue(1);
    q.enqueue(2);
    q.enqueue(3);
    
    cout << "队头: " << q.Front() << endl;
    q.dequeue();
    q.enqueue(4);
    cout << "队尾: " << q.Rear() << endl;
    
    return 0;
}

队列的经典应用：BFS的底层支撑

在Day2中，我们学习了广度优先搜索（BFS）。BFS之所以能够层层推进，正是因为它使用了队列来存储待访问的节点。每次从队头取出一个节点访问，同时将其未访问的邻居加入队尾，保证了距离起点近的节点优先被处理。

三种结构的对比总结

结语

链表、栈和队列是构建更复杂数据结构与算法的基石。链表让我们摆脱了连续内存的束缚；栈的LIFO特性完美适配了递归和回溯问题；队列的FIFO特性则是层级遍历和任务调度的核心支撑。掌握它们，你就为后续学习树、图、哈希表等高级结构打下了坚实的基础。

下一篇预告：5天速成数据结构与算法-Day4——树与二叉树。