如何用链表来实现栈
零 说明
我们在前面用数组这种底层数据结构来实现了栈，也用队列来实现了栈。我们学习和掌握了链表之后，就可以考虑用链表来实现栈了。
一实现思路
在我们给链表引入虚拟头结点之后，所有结点元素都拥有了前驱结点，进而，我们可以对链表的第index个位置处的结点进行增删改查操作了。尤其是对于链表头结点的插入和删除操作。
同时，我们也分析出了，对于链表头位置处的增删改查时间复杂度都是O(1)。且，如果我们用链表头充当栈顶位置的话，所有对于栈的操作：入栈push()、出栈()、查看栈顶元素peek()，就可以直接用链表的addFirst()、removeFirst()、getFirst()了，非常的方便。
比较取巧的一个地方在于，对于栈而言，入栈时，元素是一个一个进到栈底的；而链表的在第1个结点前添加元素，跟栈的这种入栈操作完美匹配。非常好玩儿，又有意思。
跟前面通过数组来实现栈一样：先定义栈的接口，然后，用链表来实现它。
二 代码实现
1定义栈的接口
public interface Stack<E>{
//入栈
void push(E e);
//出栈
E pop();
//查看栈顶元素
E peek();
//查看栈的大小
int getSize();
//栈是否为空
boolean isEmpty();
}2 用链表实现栈接口
/**
* @Author:asher
* @Date:2021/4/23 13:48
* @Description:PACKAGE_NAME
* @Version:1.0
*/
public class LinkedListImplementStack<E> implements Stack<E> {
//定义成员变量，用我们自己实现的链表，而不是JDK自带的链表工具类
private LinkedList<E> linkedList;
//constructor
public LinkedListImplementStack() {
linkedList = new LinkedList<>();
}
//开始复写Stack接口的方法
@Override
public void push(E e) {
linkedList.addFirst(e);
}
@Override
public E pop() {
return linkedList.removeFirst();
}
@Override
public E peek() {
return linkedList.getFirst();
}
@Override
public int getSize() {
return linkedList.getSize();
}
@Override
public boolean isEmpty() {
return linkedList.isEmpty();
}
//复写Object类的toString()
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append("Stack top:[");
stringBuilder.append(linkedList);
return stringBuilder.toString();
}
public static void main(String[] args) {
LinkedListImplementStack<Integer> linkedListImplementStack = new LinkedListImplementStack<>();
System.out.println(linkedListImplementStack.getSize());
System.out.println(linkedListImplementStack.isEmpty());
for (int i = 0; i < 3; i++) {
linkedListImplementStack.push(i);
System.out.println(linkedListImplementStack);
}
System.out.println(linkedListImplementStack.peek());
System.out.println(linkedListImplementStack.pop());
System.out.println(linkedListImplementStack);
System.out.println(linkedListImplementStack.getSize());
System.out.println(linkedListImplementStack.isEmpty());
}
}
//结果
0
true
Stack top:[LinkedList:size 1
0
Stack top:[LinkedList:size 2
1->0
Stack top:[LinkedList:size 3
2->1->0
2
2
Stack top:[LinkedList:size 2
1->0
2
false三 对比数组实现的栈和链表实现的栈
/**
* @Author:asher
* @Date:2021/4/23 15:11
* @Description:PACKAGE_NAME
* @Version:1.0
*/
public class StackTest{
//传入的参数Stack是1个接口，是数组实现栈和链表实现栈的公共接口；
public static void test(Stack stack,int count){
long beginTime = System.currentTimeMillis();
for (int i = 0; i < count; i++) {
stack.push(i);
}
for (int i = 0; i < count; i++) {
stack.pop();
}
long endTime = System.currentTimeMillis();
//用反射来获取实现类的名字
System.out.println(stack.getClass().getName()+" "+count + " elements push() and pop() Time:" + (endTime - beginTime) + " ms.");
}
public static void main(String[] args) {
ArrayStack<Integer> arrayStack=new ArrayStack<>();
LinkedListImplementStack<Integer> linkedListImplementStack = new LinkedListImplementStack<>();
int count=100000;
test(arrayStack, count);
test(linkedListImplementStack, count);
}
}
//结果
ArrayStack:100000 elements push() and pop() Time:23 ms.
LinkedListImplementStack:100000 elements push() and pop() Time:13 ms.
========================================================
ArrayStack:10000000 elements push() and pop() Time:3150 ms.
LinkedListImplementStack:10000000 elements push() and pop() Time:6604 ms.1 测试结果
数据量100000时，链表实现的栈耗时要小一些。原因可能是数组实现栈的入栈、出栈操作耗时可能在底层数组的动态扩容上；
数据量为10000000时，数组实现栈的耗时小一些。原因可能是链表实现栈每次在链表头添加结点时，都要new Node()的操作，比较耗时。
当然，这个只是一个测试，并没有孰优孰劣的绝对性。
2 对比数组实现栈和链表实现栈
入栈：数组实现栈调用底层数组的addLast()；链表实现栈调用底层链表的addFirst();
出栈：数组实现栈调用底层数组的removeLast()；链表实现栈调用底层链表的removeFirst();
栈底：数组存放的是第1个元素；链表存放的最后1个元素；
至此，我们用数组实现了栈，也用队列实现了栈，还用链表实现了栈。
