滚雪球学Java(18)：Java 的堆栈

🏆本文收录于「滚雪球学Java」专栏，专业攻坚指数级提升，助你一臂之力，带你早日登顶🚀，欢迎大家关注&&收藏！持续更新中，up！up！up！！

前言

在 Java 编程中，堆栈是非常常见的数据结构。堆栈是一种线性数据结构，它具有后进先出 (Last In First Out, LIFO) 的特性。在 Java 中，堆栈可以使用数组或链表实现。本文旨在介绍 Java 的堆栈的实现方式，并提供一些相关的代码示例。

摘要

本文主要介绍了 Java 中堆栈的实现方式以及相关的代码示例。首先，我们介绍了堆栈的基本概念以及其操作。接着，我们分别介绍了使用数组和链表实现堆栈的方法，并提供了相应的代码示例。最后，我们总结了本文的内容，并提出了一些进一步的思考。

内容

1. 堆栈的基本概念和操作

堆栈是一种线性数据结构，它具有后进先出 (Last In First Out, LIFO) 的特性。堆栈通常支持两种基本操作：

• 入栈 (push)：将一个元素放入堆栈顶部；
• 出栈 (pop)：将堆栈顶部的元素移除；

除此之外，堆栈还可以支持一些其他的操作，例如：

• 获取栈顶元素 (peek)：查看堆栈顶部的元素，但不将其移除；
• 判断堆栈是否为空 (isEmpty)：判断堆栈是否为空；
• 获取堆栈中元素的个数 (size)：获取堆栈中元素的个数；

2. 使用数组实现堆栈

使用数组实现堆栈非常简单，我们只需要定义一个数组和一个指针，指针指向堆栈顶部元素的下一个位置。入栈操作就是将元素放入数组的当前指针位置，然后指针加一；出栈操作就是将指针减一，然后返回当前指针位置的元素。

public class ArrayStack<E> {

    private int top; // 栈顶指针
    private E[] array;

    public ArrayStack(int capacity) {
        array = (E[]) new Object[capacity];
        top = 0;
    }

    public void push(E element) {
        if (top >= array.length) {
            throw new StackOverflowError();
        }
        array[top++] = element;
    }

    public E pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return array[--top];
    }

    public E peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return array[top - 1];
    }

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

    public int size() {
        return top;
    }
}

上面的代码中，我们使用泛型来定义了 ArrayStack 类，它可以存储任意类型的元素。在构造方法中，我们创建了一个指定容量的数组和一个初始值为 0 的栈顶指针。在 push 方法中，如果栈已满，就抛出一个 StackOverflowError 异常；否则，就将元素放入数组当前指针位置，然后指针加一。在 pop 方法中，如果栈为空，就抛出一个 EmptyStackException 异常；否则，就将指针减一，然后返回当前指针位置的元素。peek、isEmpty 和 size 方法也是类似的实现。

3. 使用链表实现堆栈

使用链表实现堆栈也是一种常见的方式。链表的头部代表堆栈顶部元素，因此入栈操作就是在链表头部插入元素，出栈操作就是从链表头部移除元素。

public class LinkedStack<E> {

    private Node top; // 栈顶节点
    private int size; // 元素个数

    private class Node {
        E element;
        Node next;

        public Node(E element, Node next) {
            this.element = element;
            this.next = next;
        }
    }

    public void push(E element) {
        top = new Node(element, top);
        size++;
    }

    public E pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        E element = top.element;
        top = top.next;
        size--;
        return element;
    }

    public E peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return top.element;
    }

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

    public int size() {
        return size;
    }
}

上面的代码中，我们定义了一个 Node 类作为链表的节点，每个节点包含一个元素和一个指向下一个节点的指针。在类中，我们定义了一个头节点 top 和一个元素个数 size。在 push 方法中，我们创建一个新的节点，并将它作为新的头节点；在 pop 方法中，我们移除当前头节点，并将下一个节点作为新的头节点。peek、isEmpty 和 size 方法也是类似的实现。

4. 测试用例

为了验证我们的实现是否正确，我们编写了以下测试用例：

@Test
public void testArrayStack() {
    ArrayStack<Integer> stack = new ArrayStack<>(10);
    assertTrue(stack.isEmpty());
    assertEquals(0, stack.size());

    stack.push(1);
    stack.push(2);
    stack.push(3);
    assertFalse(stack.isEmpty());
    assertEquals(3, stack.size());
    assertEquals(3, (int) stack.pop());
    assertEquals(2, (int) stack.peek());
    assertEquals(2, (int) stack.pop());
    assertEquals(1, (int) stack.pop());

    assertThrows(EmptyStackException.class, stack::pop);
    assertThrows(EmptyStackException.class, stack::peek);
}

@Test
public void testLinkedStack() {
    LinkedStack<Integer> stack = new LinkedStack<>();
    assertTrue(stack.isEmpty());
    assertEquals(0, stack.size());

    stack.push(1);
    stack.push(2);
    stack.push(3);
    assertFalse(stack.isEmpty());
    assertEquals(3, stack.size());
    assertEquals(3, (int) stack.pop());
    assertEquals(2, (int) stack.peek());
    assertEquals(2, (int) stack.pop());
    assertEquals(1, (int) stack.pop());

    assertThrows(EmptyStackException.class, stack::pop);
    assertThrows(EmptyStackException.class, stack::peek);
}

在测试用例中，我们先分别创建了一个数组栈和一个链表栈，并进行了一系列 push、pop、peek、isEmpty 和 size 操作的验证。最后，我们使用 assertThrows 方法验证了在栈为空时，pop 和 peek 操作是否会抛出 EmptyStackException 异常。

5. 小结

本文介绍了 Java 中堆栈的基本概念和操作，以及使用数组和链表分别实现堆栈的方法。我们还提供了相应的代码示例和测试用例。在实际编程中，我们可以根据实际情况选择不同的堆栈实现方式。在使用堆栈时，我们需要确保堆栈中的元素满足后进先出的原则。

附录源码

  如上涉及所有源码均已上传同步在Gitee，提供给同学们一对一参考学习，辅助你更迅速的掌握。

☀️建议/推荐你

  无论你是计算机专业的学生，还是对编程有兴趣的小伙伴，都建议直接毫无顾忌的学习此专栏「滚雪球学Java」，bug菌郑重承诺，凡是学习此专栏的同学，均能获取到所需的知识和技能，全网最快速入门Java编程，就像滚雪球一样，越滚越大，指数级提升。

📣关于我

我是bug菌，CSDN | 掘金 | infoQ | 51CTO 等社区博客专家，历届博客之星Top30，掘金年度人气作者Top40，51CTO年度博主Top12，华为云 | 阿里云| 腾讯云等社区优质创作者，全网粉丝合计15w+ ；硬核微信公众号「猿圈奇妙屋」，欢迎你的加入！免费白嫖最新BAT互联网公司面试题、4000G pdf电子书籍、简历模板等海量资料。