【Java/数据结构】栈（Stack）（图文版）

本博客将带大家一起学习基本数据结构之一——栈（Stack），虽然Java当中的Stack集合已经被Deque（双端队列）替代了，但是他的基本思想和实现还是有必要学习的。

一.初识栈

1.基本概念

        堆栈又名栈（stack），它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。

        向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；

        从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

简单来讲，栈就是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。

如下是它在Java集合框架中的位置：

ps：由于Vector设计过时，所以继承自他的Stack也被替代了。

2.特性

LIFO：即Last In First Out，后进先出原则。

类似于坐电梯，先走进去的人后出来；或者上子弹，最先进弹夹的子弹最后打出。

3.核心操作

入栈（push）、出栈（pop）、查看栈顶（peek）

二.栈的模拟实现

老规矩，先看源码：

我们不难发现栈的实现相当简单，底层就是一个数组，同时Stack类也相当简单，仅仅只有140余行。

接下来我们不考虑泛型与io，存储的数据默认为int，来实现一个简单的栈，以理解栈的底层原理。

1.经典实现

最经典的就是基于数组的实现：

（1）基本结构

public class MyStack {
    private int[] elements; // 存储元素的数组
    private int top;        // 栈顶指针（初始为-1）
    private static final int DEFAULT_CAPACITY = 10;

    // 构造方法
    public MyStack() {
        this(DEFAULT_CAPACITY);
    }

    public MyStack(int initialCapacity) {
        if (initialCapacity <= 0) {
            throw new IllegalArgumentException("容量必须为正数");
        }
        this.elements = new int[initialCapacity];
        top = -1;
    }
    
    ......

说明：

由于是基于数组实现的，所以不得不考虑动态扩容机制。

我们提供2种构造方法，一种指定初始容量，另一种不指定，使用默认容量，即DEFAULT_CAPACITY这一静态变量。

我们提供一个指针来指示栈顶，即top。

（2）动态扩容

// 动态扩容
private void resize(int newCapacity) {
    int[] newArray = new int[newCapacity];
    System.arraycopy(elements, 0, newArray, 0, top + 1);
    elements = newArray;
}

说明：

System.arraycopy(elements, 0, newArray, 0, top + 1);

复制数组参数（原数组，复制起始位置，复制目的地，目的地起始位置，复制长度）

（3）入栈（push）

// 入栈（带动态扩容）
public void push(int value) {
    // 检查是否需要扩容
    if (top == elements.length - 1) {
        resize(2 * elements.length);
    }
    elements[++top] = value;
}

（4）出栈（pop）

// 出栈
public int pop() {
    if (isEmpty()) {
        throw new IllegalStateException("栈为空");
    }
    return elements[top--];
}

（5）查看栈顶（peek）

// 查看栈顶元素
public int peek() {
    if (isEmpty()) {
        throw new IllegalStateException("栈为空");
    }
    return elements[top];
}

（6）其他

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

// 获取元素数量
public int size() {
    return top + 1;
}

（7）完整实现与测试

public class MyStack {
    private int[] elements; // 存储元素的数组
    private int top;        // 栈顶指针（初始为-1）
    private static final int DEFAULT_CAPACITY = 10;

    // 构造方法
    public MyStack() {
        this(DEFAULT_CAPACITY);
    }

    public MyStack(int initialCapacity) {
        if (initialCapacity <= 0) {
            throw new IllegalArgumentException("容量必须为正数");
        }
        elements = new int[initialCapacity];
        top = -1;
    }

    // 入栈（带动态扩容）
    public void push(int value) {
        // 检查是否需要扩容
        if (top == elements.length - 1) {
            resize(2 * elements.length);
        }
        elements[++top] = value;
    }

    // 出栈
    public int pop() {
        if (isEmpty()) {
            throw new IllegalStateException("栈为空");
        }
        return elements[top--];
    }

    // 查看栈顶元素
    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("栈为空");
        }
        return elements[top];
    }

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

    // 获取元素数量
    public int size() {
        return top + 1;
    }

    // 动态扩容
    private void resize(int newCapacity) {
        int[] newArray = new int[newCapacity];
        System.arraycopy(elements, 0, newArray, 0, top + 1);
        elements = newArray;
    }

    // 测试代码
    public static void main(String[] args) {
        MyStack stack = new MyStack(3);

        // 测试入栈和扩容
        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);  // 触发扩容到6

        System.out.println("栈顶元素: " + stack.peek()); // 输出40
        System.out.println("元素数量: " + stack.size()); // 输出4

        // 测试出栈
        System.out.println("出栈: " + stack.pop()); // 40
        System.out.println("出栈: " + stack.pop()); // 30
        System.out.println("剩余元素数量: " + stack.size()); // 2
    }
}

2.链表实现

除了使用数组存储数据，使用链表也是可以的，并且使用链表不用考虑动态扩容。

（1）基本结构

public class MyLinkedStack {
    private static class Node {
        int data;
        Node next;

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

    private Node top;   // 栈顶节点
    private int size;   // 元素数量

    ......

（2）入栈（push）

public void push(int value) {
    Node newNode = new Node(value);
    newNode.next = top; // 新节点指向原栈顶
    top = newNode;     // 更新栈顶
    size++;
}

（3）出栈（pop）

public int pop() {
    if (isEmpty()) {
        throw new IllegalStateException("栈为空");
    }
    int value = top.data;
    top = top.next; // 移动栈顶指针
    size--;
    return value;
}

特别注意栈为空时会报错，所以要检查栈是否为空。

（4）查看栈顶（peek）

public int peek() {
    if (isEmpty()) {
        throw new IllegalStateException("栈为空");
    }
    return top.data;
}

（5）其他

public boolean isEmpty() {
    return top == null;
}

public int size() {
    return size;
}

（6）完整实现与测试

public class MyLinkedStack {
    private static class Node {
        int data;
        Node next;

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

    private Node top;   // 栈顶节点
    private int size;   // 元素数量

    public void push(int value) {
        Node newNode = new Node(value);
        newNode.next = top; // 新节点指向原栈顶
        top = newNode;     // 更新栈顶
        size++;
    }

    public int pop() {
        if (isEmpty()) {
            throw new IllegalStateException("栈为空");
        }
        int value = top.data;
        top = top.next; // 移动栈顶指针
        size--;
        return value;
    }

    public int peek() {
        if (isEmpty()) {
            throw new IllegalStateException("栈为空");
        }
        return top.data;
    }

    public boolean isEmpty() {
        return top == null;
    }

    public int size() {
        return size;
    }

    // 测试代码
    public static void main(String[] args) {
        MyLinkedStack stack = new MyLinkedStack();
        stack.push(100);
        stack.push(200);
        System.out.println(stack.pop()); // 200
        System.out.println(stack.peek()); // 100
    }
}

三.栈的使用

请见以下代码:

import java.util.Stack;

public class StackDemo {
    public static void main(String[] args) {
        // 1. 创建栈对象
        Stack<Integer> stack = new Stack<>();

        // 2. 压栈操作（push）
        System.out.println("----- 压栈操作 -----");
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println("当前栈内容: " + stack);  // 输出: [10, 20, 30]

        // 3. 查看栈顶（peek）
        System.out.println("\n----- 查看栈顶 -----");
        System.out.println("栈顶元素: " + stack.peek()); // 输出: 30
        System.out.println("查看后栈内容: " + stack);    // 保持原样

        // 4. 弹栈操作（pop）
        System.out.println("\n----- 弹栈操作 -----");
        System.out.println("弹出元素: " + stack.pop());  // 输出: 30
        System.out.println("弹出后栈内容: " + stack);    // 输出: [10, 20]

        // 5. 检查空栈（empty）
        System.out.println("\n----- 检查空栈 -----");
        System.out.println("栈是否为空? " + stack.empty()); // 输出: false
        
        // 6. 搜索元素（search）
        System.out.println("\n----- 搜索元素 -----");
        int target = 20;
        int position = stack.search(target);
        System.out.println("元素 " + target + " 的位置: " + position);  // 输出: 1（栈顶为1）

        // 7. 清空栈
        System.out.println("\n----- 清空栈 -----");
        while (!stack.empty()) {
            System.out.println("弹出: " + stack.pop());
        }
        System.out.println("清空后栈是否为空? " + stack.empty()); // 输出: true
    }
}

更多信息请见官方文档说明：

Stack (Java Platform SE 8 )

四.栈的典型应用

1.括号匹配算法

该算法能自动检验输入的字符串中括号是否正确匹配：

import java.util.Stack;

public class BracketMatcher {
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {
            // 遇到左括号时，将对应的右括号压入栈
            switch (c) {
                case '(':
                    stack.push(')');
                    break;
                case '[':
                    stack.push(']');
                    break;
                case '{':
                    stack.push('}');
                    break;
                default:
                    // 遇到右括号时，检查栈顶是否匹配
                    if (stack.isEmpty() || stack.pop() != c) {
                        return false;
                    }
            }
        }
        // 最终栈必须为空才表示完全匹配
        return stack.isEmpty();
    }
}

原理请见LeetCode：20. 有效的括号 - 力扣（LeetCode）

2.逆波兰表达式（计算机的算数运算）

import java.util.Stack;

public class ReversePolishNotation {
    public static int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        
        for (String token : tokens) {
            // 遇到运算符时进行计算
            if (isOperator(token)) {
                int b = stack.pop();
                int a = stack.pop();
                stack.push(calculate(a, b, token));
            } 
            // 遇到数字时压栈
            else {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }

    // 判断是否是运算符
    private static boolean isOperator(String s) {
        return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/");
    }

    // 执行运算（注意操作数顺序）
    private static int calculate(int a, int b, String op) {
        switch (op) {
            case "+": return a + b;
            case "-": return a - b;
            case "*": return a * b;
            case "/": return a / b;  // 题目通常要求整数除法向零取整
            default: throw new IllegalArgumentException("非法运算符");
        }
    }

    public static void main(String[] args) {
        // 测试案例
        String[][] testCases = {
            {"2","1","+","3","*"},      // (2+1)*3=9
            {"4","13","5","/","+"},      // 4+(13/5)=6
            {"10","6","9","3","+","-11","*","/","*","17","+","5","+"} // 10*(6/((9+3)*-11))+17+5
        };

        for (String[] testCase : testCases) {
            System.out.println("表达式: " + String.join(" ", testCase));
            System.out.println("结果: " + evalRPN(testCase) + "\n");
        }
    }
}

详情请见：150. 逆波兰表达式求值 - 力扣（LeetCode）

结语

关于用Deque替代Stack的事，我们在队列Quque中会讲到，敬请期待！

如果有帮助不妨点个赞吧，下期就是Quque了！( ´∀｀)つt[ ]