1. 如何实现一个栈（Stack）？请使用数组和链表分别实现，并比较它们的优缺点。

PangHu大约 4 分钟

栈（Stack）是一种常用的数据结构，它遵循“后进先出”（LIFO, Last In First Out）的原则。栈的基本操作包括入栈（push）和出栈（pop），即在栈顶插入元素和从栈顶移除元素。下面分别使用数组和链表实现栈，并对它们的优缺点进行比较。

1. 使用数组实现栈

使用数组实现栈时，我们需要一个指针来跟踪栈顶的位置。

1.1 数组实现栈的代码示例

public class ArrayStack {
    private int[] stack;
    private int top;
    private int maxSize;

    public ArrayStack(int size) {
        maxSize = size;
        stack = new int[maxSize];
        top = -1; // 初始时栈为空
    }

    // 入栈操作
    public void push(int value) {
        if (isFull()) {
            throw new RuntimeException("Stack is full");
        }
        stack[++top] = value;
    }

    // 出栈操作
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stack[top--];
    }

    // 查看栈顶元素
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return stack[top];
    }

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

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

1.2 数组实现栈的优缺点

优点：

访问速度快：数组在内存中是连续存储的，访问元素时可以直接通过索引访问，时间复杂度为 O(1)。
实现简单：数组的结构简单，易于理解和实现。

缺点：

固定大小：数组在初始化时需要指定大小，一旦达到容量限制，就无法再存储更多的元素。如果需要扩展容量，则需要创建一个更大的数组，并将元素复制到新数组中，这会消耗额外的时间和空间。
浪费空间：如果栈的使用量远小于数组的大小，会造成空间浪费。

2. 使用链表实现栈

使用链表实现栈时，每次入栈或出栈操作都会在链表的头部进行。

2.1 链表实现栈的代码示例

public class LinkedListStack {
    private Node top;

    // 节点内部类
    private static class Node {
        int value;
        Node next;

        Node(int value) {
            this.value = value;
        }
    }

    // 入栈操作
    public void push(int value) {
        Node newNode = new Node(value);
        newNode.next = top;
        top = newNode;
    }

    // 出栈操作
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        int value = top.value;
        top = top.next;
        return value;
    }

    // 查看栈顶元素
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return top.value;
    }

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

2.2 链表实现栈的优缺点

优点：

动态大小：链表实现的栈没有固定大小限制，可以根据需要动态扩展，无需担心栈的容量问题。
内存利用率高：链表的内存使用是动态的，没有数组实现中的固定大小问题，不会浪费空间。

缺点：

访问速度较慢：由于链表的节点不在内存中连续存储，访问节点时需要逐个遍历，时间复杂度为 O(n)。
额外的空间开销：链表的每个节点都需要额外的指针空间来存储指向下一个节点的引用，增加了内存使用。

3. 数组和链表实现栈的比较

特性	数组实现栈	链表实现栈
内存使用	固定大小，可能会浪费空间	动态大小，内存利用率高
时间复杂度（访问）	O(1)	O(n)
时间复杂度（插入/删除）	O(1)	O(1)
实现复杂度	简单	略复杂，需要管理指针
扩展性	受限于初始大小，需要手动扩展	动态扩展，无需额外操作
适用场景	适用于已知大小、访问频繁的场景	适用于大小不确定、动态变化的场景

4. 总结

数组实现的栈 适合在大小固定或可预估的场景下使用，访问速度快，结构简单，但存在容量限制和可能的空间浪费问题。
链表实现的栈 适合在大小不确定或需要频繁动态扩展的场景下使用，内存利用率高，但由于每个节点的额外指针空间，内存开销稍大，访问速度较慢。

在选择实现方式时，应根据具体应用场景的需求权衡性能和空间的取舍。