JavaScript 使用链表实现栈

在本章中，我们将深入探讨如何使用链表来实现栈这种数据结构。栈是一种后进先出（LIFO）的数据结构，其主要操作包括入栈（push）和出栈（pop）。通过链表实现栈不仅能够高效地执行这些操作，还能灵活地扩展栈的大小。

链表的基本概念

在开始之前，我们先简要回顾一下链表的基础知识。链表是由一系列节点组成的线性数据结构，每个节点包含数据部分以及一个指向下一个节点的引用。链表可以分为单向链表、双向链表和循环链表等类型。对于栈的实现，我们通常使用单向链表，因为栈只需要关注插入和删除操作，而不需要访问中间节点。

节点类的定义

为了实现栈，我们需要首先定义一个节点类（Node），该类至少需要包含两个属性：data 用于存储节点的数据，next 用于指向下一个节点。示例代码如下：

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

栈的实现

接下来，我们将基于上述节点类创建一个栈类（Stack），该类将提供基本的栈操作方法，如 push、pop 和 peek。

栈类的定义

栈类需要包含一些基本属性，例如一个指向栈顶元素的引用 top，以及一个表示栈大小的属性 size。栈类的定义如下：

class Stack {
    constructor() {
        this.top = null;
        this.size = 0;
    }
}

入栈操作

入栈操作是指向栈顶添加一个新元素的过程。在这个过程中，我们首先创建一个新的节点，然后将其与当前的栈顶节点链接起来，并更新栈顶指针。

// www.javascriptcn.com code example
class Stack {
    // 其他方法...

    push(data) {
        const newNode = new Node(data);
        if (!this.top) {
            this.top = newNode;
        } else {
            newNode.next = this.top;
            this.top = newNode;
        }
        this.size++;
    }
}

出栈操作

出栈操作是从栈顶移除一个元素的过程。在执行此操作时，我们需要保存当前栈顶的元素，更新栈顶指针为下一个节点，并返回被移除的元素。

// www.javascriptcn.com code example
class Stack {
    // 其他方法...

    pop() {
        if (!this.top) return null;

        const removedNode = this.top;
        this.top = this.top.next;
        this.size--;
        return removedNode.data;
    }
}

查看栈顶元素

查看栈顶元素的操作不需要改变栈的状态。我们只需返回当前栈顶节点的数据即可。

class Stack {
    // 其他方法...

    peek() {
        if (!this.top) return null;
        return this.top.data;
    }
}

测试栈的功能

最后，我们可以编写一些简单的测试代码来验证栈的各项功能是否正常工作。

// www.javascriptcn.com code example
const stack = new Stack();

stack.push(1);
stack.push(2);
stack.push(3);

console.log(stack.peek()); // 输出: 3

console.log(stack.pop()); // 输出: 3
console.log(stack.pop()); // 输出: 2

console.log(stack.size); // 输出: 1

通过以上步骤，我们成功地利用链表实现了栈这一数据结构，并且验证了其基本操作的正确性。这种方式不仅易于理解和维护，而且非常适用于动态变化的场景。