线性数据结构之栈结构

栈（Stack）是一种线性数据结构，遵循“后进先出”（Last In, First Out，LIFO）的原则。栈主要有两种基本操作：push（入栈）和 pop（出栈）。在栈中，最新添加的元素最先被移除，类似于一摞盘子：放在最上面的盘子是最后放上去的，但却是最先拿走的。

栈的实现可以基于数组和链表，各有优缺点，适合不同的应用场景。下面将详细介绍栈的定义、特点、优缺点、应用场景以及用数组和链表实现栈的方式。

栈的基本概念

1. 特点

LIFO：栈遵循“后进先出”原则。
基本操作：
- Push：将元素放入栈顶。
- Pop：移除栈顶元素并返回其值。
- Peek（Top）：返回栈顶元素但不移除它。
- isEmpty：检查栈是否为空。
- Size：返回栈中元素的数量。

2. 优点

操作简单：只允许在栈顶进行添加或删除操作。
快速：只需要在栈顶操作，时间复杂度为 O(1)。

3. 缺点

容量限制：基于数组的栈实现通常有固定容量，需要判断是否溢出。
仅支持栈顶操作：无法直接访问中间元素。

4. 应用场景

函数调用：程序执行时的调用栈，用来管理方法的调用和返回。
表达式求值：如计算器中的中缀表达式转后缀表达式、表达式求值。
撤销操作：用于实现文本编辑器、图片编辑器的撤销和重做功能。

一、数组实现栈

定义与实现原理

在数组实现的栈中，数组的最后一个位置作为栈顶。入栈时将元素添加到数组末尾，出栈时从数组末尾移除元素。数组实现的栈通常具有固定的大小，且在栈满时可能会引发溢出错误。

1. 优点

访问速度快：数组在内存中是连续存储的，因此访问栈顶元素非常快。
实现简单：操作简单，入栈和出栈仅涉及数组末尾元素。

2. 缺点

固定大小：数组的大小在初始化时确定，不灵活。
栈满溢出：当栈达到数组容量时，将无法继续入栈操作。

3. 适用场景

静态数据栈：如数据量固定的递归栈、调用栈等。

4. 示例代码（Java）

class ArrayStack {
    private int[] stack;
    private int top;       // 栈顶指针
    private int capacity;  // 栈的最大容量

    // 构造函数，初始化栈
    public ArrayStack(int size) {
        stack = new int[size];
        top = -1;  // 栈为空时，top 指向 -1
        capacity = size;
    }

    // 入栈操作
    public void push(int value) {
        if (isFull()) {
            throw new StackOverflowError("栈已满，无法入栈");
        }
        stack[++top] = value;
    }

    // 出栈操作
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈为空，无法出栈");
        }
        return stack[top--];
    }

    // 返回栈顶元素，但不删除
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("栈为空，无法查看栈顶");
        }
        return stack[top];
    }

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

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

    // 返回栈中元素个数
    public int size() {
        return top + 1;
    }
    
    // 打印栈元素
    public void display() {
        for (int i = 0; i <= top; i++) {
            System.out.print(stack[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        ArrayStack stack = new ArrayStack(5);
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.display(); // 输出：10 20 30

        System.out.println("栈顶元素: " + stack.peek()); // 输出：栈顶元素: 30
        stack.pop();
        stack.display(); // 输出：10 20
    }
}

二、链表实现栈

定义与实现原理

链表实现的栈使用链表的头节点作为栈顶。每次入栈时在链表头部插入一个新节点，每次出栈时删除链表的头节点。这种实现方式可以动态扩展栈的大小。

1. 优点

动态大小：链表实现的栈大小可以动态增长，不受固定容量限制。
内存管理灵活：在需要的时候才分配内存，适合大型数据或频繁变化的数据。

2. 缺点

内存开销大：链表节点需要存储数据和指针，内存消耗较大。
访问速度慢：链表节点在内存中不连续，访问时间相对较长。

3. 适用场景

动态数据栈：如大量动态数据的进出，或内存受限且数据量不确定的场景。

4. 示例代码（Java）

class LinkedListNode {
    int data;
    LinkedListNode next;

    LinkedListNode(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedListStack {
    private LinkedListNode top; // 栈顶指针

    // 构造函数，初始化栈
    public LinkedListStack() {
        top = null;
    }

    // 入栈操作
    public void push(int value) {
        LinkedListNode newNode = new LinkedListNode(value);
        newNode.next = top; // 新节点指向当前的栈顶
        top = newNode;      // 栈顶指针指向新节点
    }

    // 出栈操作
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈为空，无法出栈");
        }
        int value = top.data;
        top = top.next; // 栈顶指针指向下一个节点
        return value;
    }

    // 返回栈顶元素，但不删除
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("栈为空，无法查看栈顶");
        }
        return top.data;
    }

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

    // 返回栈中元素个数
    public int size() {
        int count = 0;
        LinkedListNode current = top;
        while (current != null) {
            count++;
            current = current.next;
        }
        return count;
    }

    // 打印栈元素
    public void display() {
        LinkedListNode current = top;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedListStack stack = new LinkedListStack();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.display(); // 输出：30 20 10

        System.out.println("栈顶元素: " + stack.peek()); // 输出：栈顶元素: 30
        stack.pop();
        stack.display(); // 输出：20 10
    }
}

总结对比

实现方式	优点	缺点	适用场景
数组实现栈	访问速度快，适合小规模、静态数据的栈	固定大小，可能导致溢出	数据量固定、性能要求高的场景，如递归栈
链表实现栈	动态大小，适合大量动态数据	内存消耗较大，访问速度稍慢	数据量不确定且变化频繁的场景，如动态堆栈