【Java数据结构】详解Stack与Queue（一）

E绵绵

发布于 2024-06-04 08:25:54

690

发布于 2024-06-04 08:25:54

1.❤️❤️前言~🥳🎉🎉🎉

Hello, Hello~ 亲爱的朋友们👋👋，这里是E绵绵呀✍️✍️。 如果你喜欢这篇文章，请别吝啬你的点赞❤️❤️和收藏📖📖。如果你对我的内容感兴趣，记得关注我👀👀以便不错过每一篇精彩。 当然，如果在阅读中发现任何问题或疑问，我非常欢迎你在评论区留言指正🗨️🗨️。让我们共同努力，一起进步！ 加油，一起CHIN UP！💪💪

2.栈(Stack) 的概念

栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（Last In First Out）的原则。

在集合框架中，Stack（栈）是一个普通的类，具体框架图如下：

3.栈的模拟实现

我们能用顺序存储或链式存储来实现栈。 采用顺序存储的栈称为顺序栈，它利用一组地址连续的存储单元存放自栈底到栈顶的数据元素（也就是用数组去实现） 采用链式存储的栈称为链式栈，通常采用双向链表实现（之所以用双向链表我们后面将会说）
栈的方法如下，接下来我们要模拟顺序栈和链式栈的实现

3.1顺序栈的模拟实现

由于顺序栈是由顺序存储实现的，所以其底层是一个动态数组 。以下是其模拟实现的代码。

这样我们就实现了一个去存放整形数据的顺序栈。下图是对于该顺序栈的使用代码：

3.2 链式栈的模拟实现

底层是链表需要满足的条件： 先进后出 入栈和出栈的时间复杂度为O(1) 链表可以头插也可以尾插，那么入栈是使用头插法还是使用尾插法呢？ 假设我们是用单链表为底层：如果入栈使用尾插法，那么时间复杂度是O(n)，因为尾插法每次都要找最后一个结点。假设：如果入栈使用头插法，那么时间复杂度是O(1)；出栈的时候只需要删除头结点，时间复杂度也是O(1) 经过推导得出，用单链表使用头插法实现栈能满足条件，但是如果非要使用尾插法呢？假设给一个last引用指向尾巴结点，此时入栈的时间复杂度为O(1)。但是出栈的时间复杂度还是O(n)。因为，虽然知道了最后一个结点，但是去掉尾巴结点后还要知道它的前一个结点，那么就要遍历单链表去找尾巴结点的前驱结点。此时时间复杂度又是O(n)。 最终的解决办法就是用双向链表使用尾插法来实现一个栈。（双向链表可以知道一个结点的前驱结点与后继结点）。 自然双向链表也就能用头插法去实现一个栈。
所以我们可以用单链表使用头插法去实现栈，也可以用双链表使用头插法或尾插法去实现栈

这里我们用双向链表使用尾插法去实现一个链式栈：

这样我们就用双链表使用尾插法实现了一个栈，下图是该栈的使用代码：

3.3顺序栈和链式栈的区别

对比一下顺序栈与链式栈,它们在时间复杂度上是一样的,均为O(1)。对于空间性能,顺序栈需要事先确定一个固定的长度,可能会存在内存空间浪费的问题,但它的优势是存取时定位很方便,而链栈则要求每个元素都有指针域,这同时也增加了一些内存开销,但对于栈的长度无限制,不会存在内存空间浪费的情况。所以它们的区别和线性表中讨论的一样,如果栈的使用过程中元素变化不可预料,有时很小,有时非常大,那么最好是用链栈,反之,如果它的变化在可控范围内,建议使用顺序栈会更好一些。