在 Java 中实现栈

简介

栈（Stack）是一种重要的数据结构，遵循后进先出（LIFO, Last In First Out）的原则。在 Java 中，实现栈有多种方式，理解如何实现栈以及其应用场景对于开发高效的程序至关重要。本文将详细介绍在 Java 中实现栈的基础概念、使用方法、常见实践以及最佳实践。

栈的基础概念

栈是一种线性数据结构，它的操作主要有两个：入栈（push）和出栈（pop）。入栈是将元素添加到栈的顶部，而出栈则是从栈顶移除元素。此外，还有一些辅助操作，如查看栈顶元素（peek）、判断栈是否为空（isEmpty）以及获取栈的大小（size）。

在 Java 中实现栈的方法

使用数组实现栈

使用数组实现栈是一种简单直观的方式。以下是一个基本的实现代码：

public class ArrayStack {
    private int[] stackArray;
    private int top;

    public ArrayStack(int capacity) {
        stackArray = new int[capacity];
        top = -1;
    }

    public void push(int item) {
        if (isFull()) {
            System.out.println("Stack is full.");
            return;
        }
        stackArray[++top] = item;
    }

    public int pop() {
        if (isEmpty()) {
            System.out.println("Stack is empty.");
            return -1;
        }
        return stackArray[top--];
    }

    public int peek() {
        if (isEmpty()) {
            System.out.println("Stack is empty.");
            return -1;
        }
        return stackArray[top];
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == stackArray.length - 1;
    }

    public int size() {
        return top + 1;
    }
}

使用链表实现栈

使用链表实现栈具有更好的灵活性，因为链表的大小可以动态变化。以下是实现代码：

class Node {
    int data;
    Node next;

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

public class LinkedListStack {
    private Node top;

    public LinkedListStack() {
        top = null;
    }

    public void push(int item) {
        Node newNode = new Node(item);
        newNode.next = top;
        top = newNode;
    }

    public int pop() {
        if (isEmpty()) {
            System.out.println("Stack is empty.");
            return -1;
        }
        int popped = top.data;
        top = top.next;
        return popped;
    }

    public int peek() {
        if (isEmpty()) {
            System.out.println("Stack is empty.");
            return -1;
        }
        return top.data;
    }

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

    public int size() {
        int count = 0;
        Node current = top;
        while (current != null) {
            count++;
            current = current.next;
        }
        return count;
    }
}

常见实践

表达式求值

栈在表达式求值中非常有用，特别是对于后缀表达式（逆波兰表达式）。以下是一个简单的后缀表达式求值示例：

import java.util.Stack;

public class PostfixEvaluation {
    public static int evaluatePostfix(String exp) {
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < exp.length(); i++) {
            char ch = exp.charAt(i);
            if (Character.isDigit(ch)) {
                stack.push(ch - '0');
            } else {
                int val2 = stack.pop();
                int val1 = stack.pop();
                switch (ch) {
                    case '+':
                        stack.push(val1 + val2);
                        break;
                    case '-':
                        stack.push(val1 - val2);
                        break;
                    case '*':
                        stack.push(val1 * val2);
                        break;
                    case '/':
                        stack.push(val1 / val2);
                        break;
                }
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        String exp = "345+*";
        System.out.println(evaluatePostfix(exp));
    }
}

深度优先搜索（DFS）

在图的深度优先搜索中，栈可以用来记录待访问的节点。以下是一个简单的基于栈的 DFS 实现：

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class DFSUsingStack {
    private List<List<Integer>> adj;

    public DFSUsingStack(int vertices) {
        adj = new ArrayList<>();
        for (int i = 0; i < vertices; i++) {
            adj.add(new ArrayList<>());
        }
    }

    public void addEdge(int u, int v) {
        adj.get(u).add(v);
    }

    public void dfs(int start) {
        boolean[] visited = new boolean[adj.size()];
        Stack<Integer> stack = new Stack<>();
        stack.push(start);

        while (!stack.isEmpty()) {
            int vertex = stack.pop();
            if (!visited[vertex]) {
                System.out.print(vertex + " ");
                visited[vertex] = true;
                List<Integer> neighbors = adj.get(vertex);
                for (int i = neighbors.size() - 1; i >= 0; i--) {
                    int neighbor = neighbors.get(i);
                    if (!visited[neighbor]) {
                        stack.push(neighbor);
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        DFSUsingStack graph = new DFSUsingStack(4);
        graph.addEdge(0, 1);
        graph.addEdge(0, 2);
        graph.addEdge(1, 2);
        graph.addEdge(2, 0);
        graph.addEdge(2, 3);
        graph.addEdge(3, 3);

        System.out.println("Depth First Traversal starting from vertex 2:");
        graph.dfs(2);
    }
}

最佳实践

选择合适的实现方式

如果栈的大小在初始化后基本固定，并且需要快速访问元素，使用数组实现栈是一个不错的选择。如果栈的大小需要动态变化，并且频繁进行插入和删除操作，链表实现栈更为合适。

异常处理

在实现栈的操作时，应适当处理异常情况，如栈满或栈空。可以抛出自定义异常，或者在方法中进行提示（如上述代码中的打印提示信息）。

性能优化

对于数组实现的栈，可以考虑动态扩容以避免栈满的情况。对于链表实现的栈，可以使用双向链表来提高某些操作的性能。

小结

在 Java 中实现栈有多种方式，每种方式都有其优缺点和适用场景。通过理解栈的基础概念、掌握不同的实现方法以及常见实践和最佳实践，开发者可以在实际项目中灵活运用栈这种数据结构，提高程序的效率和质量。

参考资料

《Effective Java》
Oracle Java 官方文档
《数据结构与算法分析 - Java 语言描述》