滚雪球学Java(18)：解密JavaSE中的堆栈：你真的了解Java内存吗？
原创滚雪球学Java(18)：解密JavaSE中的堆栈：你真的了解Java内存吗？
原创
??咦咦咦，各位小可爱，我是你们的好伙伴——bug菌，今天又来给大家普及Java SE相关知识点了，别躲起来啊，听我讲干货还不快点赞，赞多了我就有动力讲得更嗨啦！所以呀，养成先点赞后阅读的好习惯，别被干货淹没了哦~
?本文收录于 **[「滚雪球学Java」 ](https://blog.csdn.net/weixin_43970743/category_9600553.html)专栏，专业攻坚指数级提升，希望能够助你一臂之力，帮你早日登顶实现财富自由?；同时，欢迎大家关注&&收藏&&订阅**！持续更新中，up！up！up！！
环境说明：Windows 10 + IntelliJ IDEA 2021.3.2 + Jdk 1.8前言
??在 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 方法也是类似的实现。
拓展：
??此代码实现了一个基于数组的栈结构。具体分析如下：
- 类定义：
public class ArrayStack<E>表示这是一个泛型类，使用泛型类型参数 E 表示栈中元素的类型。 - 私有字段：
private int top;表示栈顶指针，标识当前栈顶元素的位置。private E[] array;表示存储栈元素的数组。 - 构造方法：
public ArrayStack(int capacity)接受一个整型参数 capacity，表示栈的容量。在构造方法内部，通过(E[]) new Object[capacity]创建了一个数组，并将其赋值给array字段。此处使用类型转换(E[])是因为 Java 的泛型不允许直接创建泛型数组。 push(E element)方法：将元素element入栈。首先检查栈是否已满，即top >= array.length，如果已满则抛出StackOverflowError异常。否则，将element存储到array[top]，并将top指针向上移动一位。pop()方法：出栈操作，即移除并返回栈顶元素。首先检查栈是否为空，即isEmpty()方法返回true，如果为空则抛出EmptyStackException异常。否则，将top指针向下移动一位，并返回array[top]。peek()方法：返回栈顶元素，但不移除它。首先检查栈是否为空，即isEmpty()方法返回true，如果为空则抛出EmptyStackException异常。否则，返回array[top - 1]。isEmpty()方法：判断栈是否为空，即top == 0。size()方法：返回栈的元素个数，即top的值。
??需要注意的是，该代码实现没有对栈的容量进行动态扩容，如果栈满时继续入栈会抛出 StackOverflowError 异常。在使用时需要注意栈的容量是否足够。还有，由于使用了泛型，需要在创建栈对象时传入具体的元素类型参数。
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 方法也是类似的实现。
拓展：
??该代码实现了一个基于链表的栈数据结构。栈是一种特殊的线性数据结构，具有先进后出（LIFO）的特点。
??该类中有两个内部类：Node和LinkedStack。Node类用于表示栈中的节点，保存元素和下一个节点的引用；LinkedStack类是栈的实现类，包括栈顶节点和元素个数。
代码中的主要方法包括：
- push方法：将元素压入栈顶。创建一个新的节点，将该节点设置为栈顶节点的下一个节点，并将栈顶节点更新为新节点。同时，元素个数加一。
- pop方法：弹出栈顶元素。如果栈为空，则抛出EmptyStackException异常。否则，获取栈顶节点的元素，并将栈顶节点更新为其下一个节点。同时，元素个数减一。
- peek方法：返回栈顶元素，但不弹出。如果栈为空，则抛出EmptyStackException异常。
- isEmpty方法：判断栈是否为空。如果栈顶节点为null，则认为栈为空。
- size方法：返回栈中元素的个数。
??这个实现基于链表的栈相比于基于数组的栈，具有动态性，可以根据实际情况调整栈的大小。但也因此牺牲了一些性能，如访问元素的时间复杂度在最坏情况下为O(n)，而不是O(1)。
??需要注意的是，该代码中使用了泛型E表示元素的类型，可以为任意类型。
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 异常。
拓展：
??这段代码是对栈数据结构进行单元测试的代码。
??首先，定义了两个测试方法：testArrayStack()和testLinkedStack()。分别对基于数组和链表实现的栈进行测试。
??在testArrayStack()方法中，首先创建了一个容量为10的ArrayStack对象，并进行了一系列断言验证。验证了栈的初始状态应该为空，大小为0。
??然后，通过push()方法向栈中添加了三个元素：1，2和3。进行了一系列断言验证：栈不为空，大小为3。然后依次进行了pop()和peek()操作，并进行了相应的断言验证。
??最后，使用assertThrows()方法验证了在栈为空时进行pop()和peek()操作会抛出EmptyStackException异常。
??testLinkedStack()方法与testArrayStack()方法的逻辑类似，不过是使用了LinkedStack类来进行测试。
5. 小结
??本文介绍了 Java 中堆栈的基本概念和操作，以及使用数组和链表分别实现堆栈的方法。我们还提供了相应的代码示例和测试用例。在实际编程中，我们可以根据实际情况选择不同的堆栈实现方式。在使用堆栈时，我们需要确保堆栈中的元素满足后进先出的原则。
总结
??本文介绍了 Java 中堆栈的实现方式以及基本概念和操作。在 Java 中，堆栈是一种非常常见的数据结构，它具有后进先出 (Last In First Out, LIFO) 的特性。堆栈通常支持入栈、出栈、获取栈顶元素、判断堆栈是否为空以及获取堆栈中元素个数等基本操作。
??在 Java 中，我们可以使用数组或链表来实现堆栈。使用数组实现堆栈非常简单，我们只需要定义一个数组和一个指针，指针指向堆栈顶部元素的下一个位置。入栈操作就是将元素放入数组的当前指针位置，然后指针加一；出栈操作就是将指针减一，然后返回当前指针位置的元素。使用链表实现堆栈也是一种常见的方式，链表的头部代表堆栈顶部元素。入栈操作就是在链表头部插入元素，出栈操作就是从链表头部移除元素。
??在实际编程中，我们可以根据实际需求选择不同的堆栈实现方式。使用数组实现的堆栈通常需要指定一个固定的容量，而链表实现的堆栈可以根据需要动态扩展。无论使用哪种实现方式，我们都需要确保堆栈中的元素满足后进先出的原则。
??最后，我们编写了相应的测试用例来验证数组和链表实现的堆栈是否正常工作。在编写测试用例时，我们对入栈、出栈、获取栈顶元素、判断堆栈是否为空以及获取堆栈中元素个数等操作进行了验证。
??建议/推荐你
??无论你是计算机专业的学生，还是对编程有兴趣的小伙伴，都建议直接毫无顾忌的学习此专栏「滚雪球学Java」，bug菌郑重承诺，凡是学习此专栏的同学，均能获取到所需的知识和技能，全网最快速入门Java编程，就像滚雪球一样，越滚越大，指数级提升。
??码字不易，如果这篇文章对你有所帮助，帮忙给bugj菌来个一键三连(关注、点赞、收藏) ，您的支持就是我坚持写作分享知识点传播技术的最大动力。 ??同时也推荐大家关注我的硬核公众号:「猿圈奇妙屋」 ；以第一手学习bug菌的首发干货，不仅能学习更多技术硬货，还可白嫖最新BAT大厂面试真题、4000G Pdf技术书籍、万份简历/PPT模板、技术文章Markdown文档等海量资料，你想要的我都有！
?关于我
??我是bug菌，CSDN | 掘金 | infoQ | 51CTO 等社区博客专家，历届博客之星Top30，掘金年度人气作者Top40，51CTO年度博主Top12，华为云 | 阿里云| 腾讯云等社区优质创作者，全网粉丝合计15w+ ；硬核微信公众号「猿圈奇妙屋」，欢迎你的加入！免费白嫖最新BAT互联网公司面试题、4000G pdf电子书籍、简历模板等海量资料。
--End
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。