java语言中用LinkList实现堆栈

一、java语言中用LinkList实现堆栈

1、栈和队列是两种特殊的线性表，它们的逻辑结构和线性表相同，只是其运算规则较线性表有更多的限制，故又称它们为运算受限的线性表。

2、 LinkedList数据结构是一种双向的链式结构，每一个对象除了数据本身外，还有两个引用，分别指向前一个元素和后一个元素，和数组的顺序存储结构（如：ArrayList）相比，插入和删除比较方便，但速度会慢一些。

3、栈（Stack）是限制仅在表的一端进行插入和删除运算的线性表。

4、(1)通常称插入、删除的这一端为栈顶（Top），另一端称为栈底（Bottom）。

5、(3)栈为后进先出（Last In First Out）的线性表，简称为LIFO表。

6、栈的修改是按后进先出的原则进行。每次删除（退栈）的总是当前栈中"最新"的元素，即最后插入（进栈）的元素，而最先插入的是被放在栈的底部，要到最后才能删除。

7、 package com.weisou.dataStruct;

8、@SuppressWarnings("unchecked")

9、 LinkedList linkList= new LinkedList<Object>();

10、 public void push(Object object){

11、//移除并返回此列表的第一个元素

12、 return linkList.removeFirst();

13、 public static void main(String[] args){

14、 MyStack myStack= new MyStack();

15、 System.out.println(myStack.pop());

16、 System.out.println(myStack.pop());

17、队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表

18、（1）允许删除的一端称为队头（Front）。

19、（2）允许插入的一端称为队尾（Rear）。

20、（3）当队列中没有元素时称为空队列。

21、（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。

22、 package com.weisou.dataStruct;

23、 LinkedList linkedList= new LinkedList();

24、 return linkedList.removeFirst();

25、 public static void main(String[] args){

26、 MyQueue myQueue= new MyQueue();

27、 System.out.println(myQueue.get());

二、arraylist和linklist的区别

1、ArrayList实现了长度可变的数组，在内存中分配连续空间。ArrayList的查询效率比较高，增删动作的效率比较差，适用于查询比较频繁，增删动作较少的元素管理的集合。

2、LinkedList采用链表存储方式。LinkedList的查询效率低，但是增删效率很高。适用于增删动作的比较频繁，查询次数较少的元素管理集合。

三、java中ArrayList和LinkedList有什么区别,分别怎么使用呢

1、ArrayList和LinkedList都实现了List接口，ArrayList的实现用的是数组，LinkedList是基于链表，ArrayList适合查找，LinkedList适合增删。

2、ArrayList与LinkList两者的区别：

3、ArrayList是基于索引的数据接口，它的底层是数组。它可以以O(1)时间复杂度对元素进行随机访问。

4、相对于ArrayList，LinkedList的插入，添加，删除操作速度更快，因为当元素被添加到集合任意位置的时候，不需要像数组那样重新计算大小或者是更新索引。

5、LinkedList比ArrayList更占内存，因为LinkedList为每一个节点存储了两个引用，一个指向前一个元素，一个指向下一个元素。

6、但是要删除数据却是开销很大的，因为这需要重排数组中的所有数据。

7、2)相对于 ArrayList， LinkedList插入是更快的。因为 LinkedList不像 ArrayList一样，不需要改变数组的大小，也不需要在数组装满的时候要将所有的数据重新装入一个新的数组，这是 ArrayList最坏的一种情况，时间复杂度是 O(n)，而 LinkedList中插入或删除的时间复杂度仅为 O(1)。 ArrayList在插入数据时还需要更新索引（除了插入数组的尾部）。

8、3)类似于插入数据，删除数据时， LinkedList也优于 ArrayList。

9、4) LinkedList需要更多的内存，因为 ArrayList的每个索引的位置是实际的数据，而 LinkedList中的每个节点中存储的是实际的数据和前后节点的位置(一个 LinkedList实例存储了两个值： Node<E> first和 Node<E> last分别表示链表的其实节点和尾节点，每个 Node实例存储了三个值： E item,Node next,Node pre)。

10、什么场景下更适宜使用 LinkedList，而不用ArrayList

11、1)你的应用不会随机访问数据。因为如果你需要LinkedList中的第n个元素的时候，你需要从第一个元素顺序数到第n个数据，然后读取数据。

12、2)你的应用更多的插入和删除元素，更少的读取数据。因为插入和删除元素不涉及重排数据，所以它要比ArrayList要快。