java 链表实现堆栈_介绍堆栈两种实现方式

Java语言中的栈(stack)与堆(heap)都是java用来在Ram中存放数据的地方，属于计算机的内存区域，与C++不同，java自动管理栈和堆，java程序员不能直接地设置栈或堆，相关的java堆栈的知识在前面的文章中都有学习过，今天我们来看看堆栈两种实现方式，下面来介绍一下两种java堆栈实现方式。

Java堆栈两种实现方式分别是基于向量和基于列表的：

堆栈两种实现方式之一：基于向量的堆栈

可以先来考虑一个传统的基于堆栈的比拟：快餐店中盘子的存放。用餐开始的时候，获得从堆栈中取出的盘子。删除一个盘子的过程就是从堆栈中弹出一个盘子的过程。当盘子归还后，它们被压回到堆栈中。现在，假设盛放盘子的容器被标上刻度，可能是用来计算堆栈中盘子的数量。观察一下，这看起来像一个斜向一边的向量(如图)

采用这个比拟，基于向量的堆栈实现可以通过将堆栈的“顶”与向量的“尾”对齐来完成，可以参见上图。我们提供了两个构造函数，其中一个提供向量的初始容量：

下面这个图说明一个包含n个元素的基于向量的堆栈，栈顶是由底层向量的长度隐含说明的，箭头表明增长方向。

为了向堆栈中添加元素，只需要简单地使用Vector类的add方法。当需要从堆栈中删除一个元素的时候，将最后一个元素删除，并返回它的值。

add方法将元素添加到向量的尾部，如果必要的话对向量大小进行扩展。注意，如果向量具有n个元素，这个元素被加入到第n个位置，并将元素的数量增加到n+l。删除一个元素的过程与此相反：它删除并返回最后一个元素(我们在这里使用了对称的原理。我们将基于这个概念设计几对增加和删除方法)。除了不修改堆栈之外，get方法与remove类似。通过查询底层向量的大小信息，堆栈的大小很容易确定。当然，当向量为空的时候，它所支持的堆栈也是空的。

堆栈两种实现方式之二：基于列表的堆栈

只有栈顶一端可以被修改。因此，使用单链表寻求一个堆栈的高效实现是明智的选择。因为单链表处理列表头的效率比处理列表尾的效率要高，我们将栈顶与单链表的头对齐(见下图)。

add方法仅仅执行addFirst,remove

操作仅仅执行removeFirst。因为已经实现了列表的remove操作，使之返回被删除的值，所以这个值可以通过堆栈的remove方法被传递。

其余的方法就是来自于单链表的类似方法的包装器。由于堆栈操作是链表操作的平凡表示，它们的复杂度与链表中对应的操作是相同的，每一个方法的运行时间都是常量时间。

应该注意，任何实现List接口的结构都足以实现堆栈。然而，已经见过的各种列表之间的区别集中体现在提供对列表尾的快速访问上。由于不需要访问堆栈的栈底，列表的其他实现不会有优越性，因此使用单链表实现。

总之基于向量和列表就是java堆栈两种实现方式，希望大家可以好好学习上面对堆栈两种实现方式的内容，相信有了以上实际例子的列举，会对大家理解学习这两种堆栈实现方式有所帮助。另外可以在java教程中更深入的学习堆栈的实现方式。