Java 实现栈的三种方式

下面是详细讲解“Java 实现栈的三种方式”的完整攻略。

1. 栈的概述

栈（Stack）是一种常见的操作系统模型，具有“先进后出”（Last In First Out）的特点。栈被广泛应用于函数调用、表达式求值、程序递归等领域，是算法和数据结构中必不可少的基本数据结构之一。

栈的基本操作包含了入栈（push）、出栈（pop）、获取栈顶元素（peek）等。实现栈的方式有很多，下面将介绍Java实现栈的三种方式。

2. 数组实现栈

数组实现栈的方式非常简单，只需要定义一个数组和一个指向栈顶的指针，然后对数组进行增删操作即可。具体实现请看下面的代码示例：

public class ArrayStack {
    private int[] data;
    private int top;
    private int size;

    public ArrayStack(int capacity) {
        this.data = new int[capacity];
        this.top = -1;
        this.size = capacity;
    }

    public void push(int value) {
        if (top == size - 1) {
            throw new RuntimeException("Stack is full!");
        }
        data[++top] = value;
    }

    public int pop() {
        if (top == -1) {
            throw new RuntimeException("Stack is empty!");
        }
        return data[top--];
    }

    public int peek() {
        if (top == -1) {
            throw new RuntimeException("Stack is empty!");
        }
        return data[top];
    }

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

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

上面的代码定义了一个ArrayStack类，包含了入栈(push)、出栈(pop)、获取栈顶元素(peek)、判断栈是否为空(isEmpty)、判断栈是否已满(isFull)等方法。可以通过下面的代码进行测试：

public static void main(String[] args) {
    ArrayStack stack = new ArrayStack(5);
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    stack.push(5);
    System.out.println("peek:" + stack.peek());
    while (!stack.isEmpty()) {
        System.out.print(stack.pop() + " ");
    }
}

输出结果为：

peek:5
5 4 3 2 1 

3. 链表实现栈

链表实现栈是一种常见的实现方式，它和数组实现有一定区别，它不需要事先指定大小，并且可以动态调整大小。具体实现请看下面的代码示例：

public class LinkedStack {
    class Node {
        int val;
        Node next;

        public Node(int val) {
            this.val = val;
        }
    }

    private Node top;
    private int size;

    public LinkedStack() {
        top = null;
        size = 0;
    }

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

    public int pop() {
        if (top == null) {
            throw new RuntimeException("Stack is empty!");
        }
        int res = top.val;
        top = top.next;
        size--;
        return res;
    }

    public int peek() {
        if (top == null) {
            throw new RuntimeException("Stack is empty!");
        }
        return top.val;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }
}

上面的代码定义了一个LinkedStack类，包含了入栈(push)、出栈(pop)、获取栈顶元素(peek)、判断栈是否为空(isEmpty)、获取栈大小(size)等方法。可以通过下面的代码进行测试：

public static void main(String[] args) {
    LinkedStack stack = new LinkedStack();
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    stack.push(5);
    System.out.println("peek:" + stack.peek());
    while (!stack.isEmpty()) {
        System.out.print(stack.pop() + " ");
    }
}

输出结果为：

peek:5
5 4 3 2 1 

4. Java自带Stack类

Java中已经封装好了栈的实现类——Stack，它继承自Vector类，相对于普通的Vector，Stack添加了关于操作栈的方法和特性。具体用法请看下面的代码示例：

public static void main(String[] args) {
    Stack<Integer> stack = new Stack<>();
    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);
    stack.push(5);
    System.out.println("peek:" + stack.peek());
    while (!stack.isEmpty()) {
        System.out.print(stack.pop() + " ");
    }
}

输出结果为：

peek:5
5 4 3 2 1 

5. 总结

以上就是Java实现栈的三种方式，它们各有优缺点，可以针对不同的需求进行选择。数组实现栈对内存占用比较少，但大小固定；链表实现栈对动态调整大小非常方便，但对内存占用比较大；Java自带Stack类使用简单方便，但相对于手动实现要慢一些，而且它是线程安全的。在实际工作中，需要根据实际情况进行选择。