JavaScript中的数据结构与算法应用

描述
在JavaScript开发中，数据结构与算法是解决复杂问题的核心基础。虽然JavaScript内置了Array、Object等数据结构，但实际开发中经常需要实现栈、队列、链表等高级数据结构，以及排序、搜索等经典算法。理解这些概念能帮助你写出更高效、可维护的代码。

知识讲解

一、栈（Stack）的实现与应用
栈是一种LIFO（后进先出）的数据结构，只允许在栈顶进行插入和删除操作。

class Stack {
    constructor() {
        this.items = [];
    }
    
    // 入栈
    push(element) {
        this.items.push(element);
    }
    
    // 出栈
    pop() {
        if (this.isEmpty()) return null;
        return this.items.pop();
    }
    
    // 查看栈顶元素
    peek() {
        return this.items[this.items.length - 1];
    }
    
    // 判断是否为空
    isEmpty() {
        return this.items.length === 0;
    }
    
    // 获取栈大小
    size() {
        return this.items.length;
    }
}

// 应用示例：括号匹配检查
function isBalancedParentheses(str) {
    const stack = new Stack();
    const pairs = { ')': '(', ']': '[', '}': '{' };
    
    for (let char of str) {
        if (['(', '[', '{'].includes(char)) {
            stack.push(char);
        } else if ([')', ']', '}'].includes(char)) {
            if (stack.isEmpty() || stack.pop() !== pairs[char]) {
                return false;
            }
        }
    }
    
    return stack.isEmpty();
}

二、队列（Queue）的实现与应用
队列是FIFO（先进先出）的数据结构，支持在队尾添加元素，在队首移除元素。

class Queue {
    constructor() {
        this.items = [];
    }
    
    // 入队
    enqueue(element) {
        this.items.push(element);
    }
    
    // 出队
    dequeue() {
        if (this.isEmpty()) return null;
        return this.items.shift();
    }
    
    // 查看队首元素
    front() {
        return this.items[0];
    }
    
    isEmpty() {
        return this.items.length === 0;
    }
    
    size() {
        return this.items.length;
    }
}

// 应用示例：击鼓传花游戏
function hotPotato(elements, num) {
    const queue = new Queue();
    elements.forEach(element => queue.enqueue(element));
    
    while (queue.size() > 1) {
        for (let i = 0; i < num; i++) {
            queue.enqueue(queue.dequeue());
        }
        queue.dequeue(); // 淘汰当前持有"花"的人
    }
    
    return queue.front(); // 最后的胜者
}

三、链表（Linked List）的实现
链表通过节点间的指针连接，相比数组在插入删除操作上更高效。

class ListNode {
    constructor(value) {
        this.value = value;
        this.next = null;
    }
}

class LinkedList {
    constructor() {
        this.head = null;
        this.length = 0;
    }
    
    // 在尾部添加节点
    append(value) {
        const newNode = new ListNode(value);
        
        if (!this.head) {
            this.head = newNode;
        } else {
            let current = this.head;
            while (current.next) {
                current = current.next;
            }
            current.next = newNode;
        }
        this.length++;
    }
    
    // 在指定位置插入节点
    insert(position, value) {
        if (position < 0 || position > this.length) return false;
        
        const newNode = new ListNode(value);
        
        if (position === 0) {
            newNode.next = this.head;
            this.head = newNode;
        } else {
            let current = this.head;
            let previous = null;
            let index = 0;
            
            while (index++ < position) {
                previous = current;
                current = current.next;
            }
            
            newNode.next = current;
            previous.next = newNode;
        }
        
        this.length++;
        return true;
    }
}

四、排序算法的JavaScript实现

快速排序（分治思想）

function quickSort(arr) {
    if (arr.length <= 1) return arr;
    
    const pivot = arr[Math.floor(arr.length / 2)];
    const left = [];
    const right = [];
    const equal = [];
    
    for (let element of arr) {
        if (element < pivot) left.push(element);
        else if (element > pivot) right.push(element);
        else equal.push(element);
    }
    
    return [...quickSort(left), ...equal, ...quickSort(right)];
}

归并排序（稳定排序）

function mergeSort(arr) {
    if (arr.length <= 1) return arr;
    
    const mid = Math.floor(arr.length / 2);
    const left = mergeSort(arr.slice(0, mid));
    const right = mergeSort(arr.slice(mid));
    
    return merge(left, right);
}

function merge(left, right) {
    const result = [];
    let i = 0, j = 0;
    
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            result.push(left[i++]);
        } else {
            result.push(right[j++]);
        }
    }
    
    return [...result, ...left.slice(i), ...right.slice(j)];
}

五、搜索算法的实现

二分查找（要求数组有序）

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (arr[mid] === target) return mid;
        else if (arr[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    
    return -1;
}

六、实际应用场景

1. 栈的应用：函数调用栈、撤销操作、路由历史记录
2. 队列的应用：任务调度、消息队列、广度优先搜索
3. 链表的应用：LRU缓存实现、大数相加运算
4. 排序算法选择：小数据用插入排序，大数据用快速排序，需要稳定用归并排序

学习建议

• 理解每种数据结构的时间复杂度特点
• 结合实际场景选择合适的数据结构
• 多练习LeetCode等平台的算法题目
• 掌握空间换时间的优化思想