1、结合之前实现的链表这个数据结构，如果只对链表的头部进行增加和删除，时间复杂度是O(1)的，只对链表的头部进行查询的话，时间复杂度是O(1)的。那么，满足这样的数据结构是什么呢，就是栈，栈这种数据结构是后入先出的，或者先进后出的，只对栈的一端，就是栈顶进行操作，无论是添加元素、删除元素、查询元素，都是在栈顶进行的。所以对于链表来说，可以将链表的头部当作栈顶，用链表做为栈的底层实现来实现一个栈。
创建一个栈的接口，可以使用数组的方式或者链表的方式进行实现栈的功能哦！
1 package com.stack; 2 3 /** 4 * @param <E> 使用泛型，可以接受任何数据类型的 5 */ 6 public interface Stack<E> { 7 8 /** 9 * 获取到栈里面的大小 10 * 11 * @return 12 */ 13 public int getSize(); 14 15 /** 16 * 判断栈是否为空 17 * 18 * @return 19 */ 20 public boolean isEmpty(); 21 22 /** 23 * 向栈中添加一个元素，即入栈 24 * 25 * @param e 26 */ 27 public void push(E e); 28 29 /** 30 * 从栈中取出栈顶的元素，即出栈 31 * 32 * @return 33 */ 34 public E pop(); 35 36 /** 37 * 查看栈顶的元素 38 * 39 * @return 40 */ 41 public E peek(); 42 43 }
由于之前已经使用过数组实现栈，所以这里使用的是链表实现栈的功能，具体代码，如下所示：
转播
