Java数据结构与算法之栈(Stack)实现详解

Java数据结构与算法之栈(Stack)实现详解

1. 栈的概念及用途

栈(Stack)是一种线性数据结构，它具有“后进先出（Last In First Out, LIFO）”的特点。栈可以看成是一种特殊的列表，列表中的元素只能通过栈顶加入或删除，称为入栈和出栈。

栈的应用非常广泛，例如在函数调用时，系统会自动为每个函数创建一个栈，用于存储函数调用过程中产生的临时数据，当函数返回时，系统会自动弹出栈顶元素，恢复上一层的函数调用。此外，栈还可以用于解决很多算法问题，例如表达式求值、括号匹配、图搜索等等。

2. 栈的实现

栈的实现方式有多种，例如使用数组和使用链表等。在本文中，我们将主要介绍使用数组实现栈的方法。

2.1 栈的定义

首先，我们需要定义一个栈类，表示一个栈对象。一个简单的栈类定义如下：

public class MyStack {
    private int[] stackArray; // 存储栈元素的数组
    private int top; // 栈顶指针

    // 构造方法，创建指定大小的栈
    public MyStack(int size) {
        stackArray = new int[size];
        top = -1;
    }

    // 将元素压入栈顶
    public void push(int element) {
        stackArray[++top] = element;
    }

    // 弹出栈顶元素
    public int pop() {
        return stackArray[top--];
    }

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

    // 获取栈大小
    public int size() {
        return top + 1;
    }

    // 获取栈顶元素
    public int peek() {
        return stackArray[top];
    }
}

以上代码定义了一个名为MyStack的栈类，包含了栈的主要操作，例如push、pop、isEmpty、size和peek等。在这个类中，我们使用一个整型数组stackArray来存储栈中的元素，使用一个整数top来表示栈顶的指针，初始值为-1。

2.2 栈的使用

接下来，我们来演示一下如何使用MyStack类。假设我们需要将一个整数数组中的元素反转，即将数组中的最后一个元素放到最前面，倒数第二个元素放到第二个位置，以此类推。我们可以使用栈来实现这个功能，代码如下：

public static void reverseArray(int[] array) {
    MyStack stack = new MyStack(array.length);
    // 将元素压入栈中
    for (int i = 0; i < array.length; i++) {
        stack.push(array[i]);
    }
    // 将栈中元素依次弹出，赋给原数组
    for (int i = 0; i < array.length; i++) {
        array[i] = stack.pop();
    }
}

以上代码定义了一个名为reverseArray的方法，该方法接受一个整数数组作为参数，然后使用MyStack类将数组中的元素倒序排列。在这个方法中，我们首先创建了一个MyStack对象，并将原数组的元素依次压入栈中。然后，我们再依次弹出栈中的元素，赋给原数组即可。

下面，我们再演示一个栈的应用，检查字符串中的括号是否匹配。如果匹配，返回true，否则返回false。

public static boolean checkBrackets(String str) {
    MyStack stack = new MyStack(str.length());
    // 遍历字符串中的字符
    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        switch (c) {
            case '(':
            case '[':
            case '{':
                // 将左括号压入栈中
                stack.push(c);
                break;
            case ')':
                // 如果栈顶元素是左圆括号，则弹出栈顶元素
                if (stack.peek() == '(') {
                    stack.pop();
                } else {
                    return false; // 括号不匹配
                }
                break;
            case ']':
                // 如果栈顶元素是左方括号，则弹出栈顶元素
                if (stack.peek() == '[') {
                    stack.pop();
                } else {
                    return false; // 括号不匹配
                }
                break;
            case '}':
                // 如果栈顶元素是左花括号，则弹出栈顶元素
                if (stack.peek() == '{') {
                    stack.pop();
                } else {
                    return false; // 括号不匹配
                }
                break;
        }
    }
    // 如果栈为空，则括号匹配
    return stack.isEmpty();
}

以上代码定义了一个名为checkBrackets的方法，该方法接受一个字符串作为参数，然后检查字符串中的括号是否匹配。在这个方法中，我们首先创建了一个MyStack对象，然后遍历字符串中的每个字符。如果当前字符是左括号，就将其压入栈中。如果当前字符是右括号，则与栈顶元素进行匹配，如果可以匹配就弹出栈顶元素，否则就返回false。如果遍历完整个字符串之后，栈为空，则说明括号匹配，返回true，否则返回false。

3. 总结

本文介绍了栈的基本概念和使用方法，实现了一个简单的栈类，并演示了栈的两个常见应用——数组反转和括号匹配。栈是一种简单而有用的数据结构，熟练掌握栈的使用方法对程序员来说非常重要。