Java栈应用实例

一、栈的简介

栈是一种非常常用的数据结构，它是一种线性结构，具有后进先出（LIFO）的性质，即最后入栈的元素最先出栈。栈通常只允许在栈顶进行插入和删除操作，其它位置均不可访问。

在Java中，栈通常指的是调用栈（call stack），是用来保存函数调用状态的内存区域。在函数调用时，每一个函数都会在栈上开辟一块用于保存该函数的局部变量、参数、返回地址等信息，函数返回时再将对应的信息出栈，使得程序可以回到函数被调用的位置。

二、栈的应用场景

栈作为一种常用的数据结构，在许多场景下都有应用。以下是一些典型的栈的应用场景：

1. 表达式求值

在计算机中，算术表达式往往是以中缀表达式的形式出现的，而计算时往往需要将其转化为后缀表达式，然后通过栈来计算。具体的实现方式是，遍历中缀表达式并依次将各个元素入栈，当遇到操作符时，将前面两个元素出栈，计算后的结果再入栈。最后栈中剩下的元素即为计算后的结果。

2. 括号匹配

在编程中，经常需要判断一个字符串中的括号是否匹配。此时可以利用栈的后进先出的特性，将遇到的左括号依次入栈，遇到右括号时如果栈顶是对应的左括号则弹出，否则说明括号不匹配。

3. 浏览器的前进和后退

当用户在浏览器中访问不同的页面时，浏览器会将每个页面的URL保存在一个历史记录栈中。当用户点击后退按钮时，浏览器将从栈顶弹出一个URL并加载该页面，当用户点击前进按钮时，则将栈顶的URL入栈并打开对应的页面。

/**
 * 表达式求值
 * 
 * @param exp 中缀表达式数组
 * @return 表达式的计算结果
 */
public static int evaluateExpression(String[] exp) {
    Stack
    stack = new Stack<>();
    for (String s : exp) {
        if (isNumber(s)) {
            stack.push(Integer.parseInt(s));
        } else {
            int x = stack.pop();
            int y = stack.pop();
            switch (s) {
                case "+":
                    stack.push(y + x);
                    break;
                case "-":
                    stack.push(y - x);
                    break;
                case "*":
                    stack.push(y * x);
                    break;
                case "/":
                    stack.push(y / x);
                    break;
            }
        }
    }
    return stack.pop();
}

/**
 * 判断字符串是否为数字
 */
private static boolean isNumber(String s) {
    try {
        Integer.parseInt(s);
        return true;
    } catch (NumberFormatException e) {
        return false;
    }
}

   

三、栈的实现

Java中的栈可以通过继承Vector（或ArrayList）来实现，也可以通过构造一个由数组支持的小容量的堆栈来实现。以下是一个基于链表的栈的实现示例：

/**
 * 基于链表的栈的实现
 * 
 * @param 
    栈中元素的类型
 */
public class LinkedStack<T> {

    private Node<T> top;  // 栈顶节点

    // 入栈操作
    public void push(T data) {
        Node<T> newNode = new Node<>(data);
        newNode.next = top;
        top = newNode;
    }

    // 出栈操作
    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        T data = top.data;
        top = top.next;
        return data;
    }

    // 获取栈顶元素
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return top.data;
    }

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

    // 栈中节点定义
    private static class Node<T> {
        T data;           // 节点数据
        Node<T> next;  // 指向下一个节点的引用
        Node(T data) {
            this.data = data;
        }
    }
}