【ShuQiHere】使用链表 (Linked List) 和数组 (Array) 实现栈 (Stack) 的深入解析与比较

使用链表 (Linked List) 和数组 (Array) 实现栈 (Stack) 的深入解析与比较 📚

在计算机科学中，**栈（Stack）是一种非常常见且重要的数据结构。栈采用后进先出（LIFO, Last In First Out）的原则，常用于解决函数调用、运算符优先级、深度优先搜索等问题。在本文中，我们将探讨如何使用链表（Linked List）和数组（Array）**两种方式来实现栈，并分析它们的优缺点、时间复杂度和适用场景。

栈的基础概念 🔹

栈是一种只允许在**栈顶（top）**进行插入和删除操作的数据结构，遵循后进先出的原则。它是一个封闭的结构，仅支持在栈顶操作，而不能在中间或底部插入或删除元素。

栈的基本操作：

1. Push：将一个元素压入栈顶。
2. Pop：从栈顶移除一个元素。
3. Top/Peek：查看栈顶的元素而不删除。
4. IsEmpty：检查栈是否为空。

为什么选择链表或数组实现栈？🔍

栈的实现可以基于链表或数组两种数据结构，每种方式在插入、删除、空间管理上各有优劣。链表为动态增长提供了天然优势，但需要额外的空间存储指针。而数组则可以直接访问任意索引位置，但容量是固定的，扩展时可能会面临内存重分配的问题。接下来，我们将分别使用数组和链表来实现栈，并分析它们的性能、空间利用率和适用场景。

使用数组实现栈 📋

使用数组来实现栈是一种直接的方式，适合容量较小或已知最大容量的情况。我们将数组的最后一个元素当作栈顶，这样每次插入、删除都能在 O(1) 时间内完成。

数组实现的栈代码 🧑‍💻

class ArrayStack {
    private int[] stack;
    private int top;
    private int capacity;

    public ArrayStack(int size) {
        stack = new int[size];
        capacity = size;
        top = -1; // 栈顶初始化为 -1，表示栈为空
    }

    // 将元素压入栈顶
    public void push(int value) {
        if (isFull()) {
            System.out.println("Stack overflow! Unable to push " + value);
            return;
        }
        stack[++top] = value;
    }

    // 移除并返回栈顶元素
    public int pop() {
        if (isEmpty()) {
            System.out.println("Stack underflow! Unable to pop.");
            return -1;
        }
        return stack[top--];
    }

    // 返回栈顶元素但不移除
    public int top() {
        if (isEmpty()) {
            System.out.println("Stack is empty.");
            return -1;
        }
        return stack[top];
    }

    // 判断栈是否为空
    public boolean isEmpty() {
        return top == -1;
    }

    // 判断栈是否已满
    public boolean isFull() {
        return top == capacity - 1;
    }
}

数组实现栈的时间复杂度分析 ⏳

数组实现栈的优缺点 ⚖️

• 优点：

  • 随机访问：可以通过索引直接访问栈中的任意元素。
  • 操作简单：所有操作都只在栈顶进行，逻辑清晰。

• 缺点：

  • 固定大小：一旦达到容量上限，需要扩容操作，这涉及到数组重新分配和复制，耗时 O(n)。
  • 内存浪费：未使用的数组空间在栈未满时会被浪费。

使用链表实现栈 🔗

链表实现栈更为灵活，适合未知或动态增长的栈大小。通常我们将链表的头节点（head）作为栈顶，这样插入和删除都可以在 O(1) 时间内完成。

链表实现的栈代码 🧑‍💻

class Node {
    int value;
    Node next;

    public Node(int value) {
        this.value = value;
        this.next = null;
    }
}

class LinkedStack {
    private Node head; // 头节点作为栈顶

    public LinkedStack() {
        this.head = null;
    }

    // 在头部插入新节点
    public void push(int value) {
        Node newNode = new Node(value);
        newNode.next = head;
        head = newNode; // 更新栈顶指向新节点
    }

    // 移除并返回头节点的值
    public Integer pop() {
        if (isEmpty()) {
            System.out.println("Stack underflow! Unable to pop.");
            return null;
        }
        int poppedValue = head.value;
        head = head.next;
        return poppedValue;
    }

    // 返回栈顶元素但不移除
    public Integer top() {
        if (isEmpty()) {
            System.out.println("Stack is empty.");
            return null;
        }
        return head.value;
    }

    // 判断栈是否为空
    public boolean isEmpty() {
        return head == null;
    }
}

链表实现栈的时间复杂度分析 ⏳

链表实现栈的优缺点 ⚖️

• 优点：

  • 动态大小：链表栈没有容量限制，随着插入增加。
  • 插入和删除高效：在链表头部进行，O(1) 时间内完成操作。

• 缺点：

  • 额外内存：每个节点需要额外指针空间。
  • 无法随机访问：链表不支持索引，需要从栈顶遍历到目标元素。

数组与链表实现栈的对比 📊

扩展知识：链表和数组实现的栈适用场景 🏷️

1. 数组实现栈的应用

在已知容量的情况下，数组实现的栈通常较为简便，适用于以下场景：

• 编译器的语法检查：括号匹配、语法符号匹配通常要求固定容量的栈。
• 函数调用栈：在编译原理中，用来存储函数调用地址的栈通常用数组实现，因为栈大小可以预先设定。
• 浏览器的前进/后退操作：通常浏览历史的数量不会无限增长，可以用数组实现栈来存储。

2. 链表实现栈的应用

当栈的大小未知或需要频繁调整时，链表实现的栈更加灵活：

• **深

度优先搜索 (DFS)**：在图遍历中，链表栈适合动态扩展的需求。

• 递归展开：递归问题的求解会创建很多临时变量和调用栈，因此链表实现的栈灵活性更高。
• 内存优化场景：动态内存环境下，链表实现的栈可以有效节约空间，因为它只在需要时分配内存。

总结 🏆

通过链表和数组实现栈各有优缺点：

• 数组实现栈适合固定大小的场景，插入和删除都很高效，并且可以快速访问任意元素。但是，当栈容量不足时，扩容会消耗 O(n) 时间。
• 链表实现栈适合动态增长的场景，push 和 pop 操作高效，不会造成内存浪费，但访问任意节点需要从栈顶遍历到目标节点，无法实现直接索引访问。

在实际开发中，选择哪种实现方式应根据栈的应用需求和场景来决定。掌握这两种实现方法可以帮助我们更灵活地解决栈相关的编程问题！