利用数组实现栈（Java实现）

下面就详细讲解一下“利用数组实现栈（Java实现）”的完整攻略。

一、栈的概念

栈是一种具有特殊性质的线性结构，它只允许在一端进行插入和删除操作，这一端被称为栈顶。具体来说，栈的特点是后进先出（Last In First Out，LIFO）。

二、栈的实现

栈可以使用数组实现，这里我们介绍一种基于数组的简单栈实现方法：

public class MyStack {
    private int[] data; // 存放栈元素的数组
    private int topIndex; // 栈顶元素的下标

    // 构造函数，初始化栈
    public MyStack() {
        data = new int[100];
        topIndex = -1;
    }

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

    // 判断栈是否已满
    public boolean isFull() {
        return topIndex == data.length - 1;
    }

    // 入栈操作
    public void push(int element) throws Exception {
        if (isFull()) {
            throw new Exception("Stack is full");
        }
        data[++topIndex] = element;
    }

    // 出栈操作
    public int pop() throws Exception {
        if (isEmpty()) {
            throw new Exception("Stack is empty");
        }
        return data[topIndex--];
    }

    // 获取栈顶元素
    public int peek() throws Exception {
        if (isEmpty()) {
            throw new Exception("Stack is empty");
        }
        return data[topIndex];
    }
}

上面的代码实现了栈的基本操作，包括创建栈、入栈、出栈、获取栈顶元素等功能。

三、示例说明

1. 用栈判断字符串表达式中的括号是否匹配

假如我们有一个字符串表达式，其中包括左右括号。我们需要判断这个字符串中的括号是否是成对出现的（比如“()”、“（）{}[]”这种形式就是合法的，而“{[}”这种形式则是不合法的）。

解决方法：可以利用栈来解决。遍历整个字符串，在遇到左括号时，将其入栈。当遇到右括号时，从栈中弹出一个元素，如果这个元素恰好对应这个右括号，则继续判断字符串的下一个字符；否则，说明这个字符串表达式不合法。

详细代码示例：

public boolean isValid(String s) {
    MyStack stack = new MyStack();
    for (int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if (c == '(' || c == '{' || c == '[') { // 如果是左括号，入栈
            stack.push(c);
        } else if (c == ')' || c == '}' || c == ']') { // 如果是右括号，判断栈顶元素是否匹配
            if (stack.isEmpty()) {
                return false;
            }
            char top = (char) stack.pop();
            if ((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) {
                return false;
            }
        }
    }
    return stack.isEmpty(); // 如果栈为空，说明所有的左括号都已经找到了与之相匹配的右括号
}

2. 计算逆波兰式

逆波兰式（Reverse Polish Notation，RPN）是一种将运算符置于操作数之后的表达式，例如“3 4 +”，即为3 + 4。

采用栈来计算逆波兰式。具体方法为：遍历整个表达式，遇到数字时，将数字保存入栈中；遇到运算符时，将栈顶的两个元素弹出，进行运算，再将运算结果保存入栈中。

详细代码示例：

public int evalRPN(String[] tokens) {
    MyStack stack = new MyStack();
    for (String token : tokens) {
        if (token.equals("+")) {
            stack.push(stack.pop() + stack.pop());
        } else if (token.equals("-")) {
            int a = stack.pop();
            int b = stack.pop();
            stack.push(b - a);
        } else if (token.equals("*")) {
            stack.push(stack.pop() * stack.pop());
        } else if (token.equals("/")) {
            int a = stack.pop();
            int b = stack.pop();
            stack.push(b / a);
        } else {
            stack.push(Integer.parseInt(token));
        }
    }
    return stack.pop();
}

以上就是利用数组实现栈的完整攻略。