一.简介
栈也是一种频繁插入和删除元素的数据结构，所以使用链表实现也是一种比较好的选择。
二.代码实现
- DummyLinkedList 链表的实现 在我的 "链表——链表的基本概念及基本实现"中介绍过有兴趣的朋友可以看一下。这里我直接是用了DummyLinkedList。
public interface Stack<E> {
//获得栈中元素总数
int getSize();
//判断是否为空
boolean isEmpty();
//查看栈顶元素
E peek();
//出栈
E pop();
//入栈
void push(E e);
}
/**
* 链表栈 时间复杂度O(1)
*/
public class LinkedListStack<E> implements Stack<E> {
private DummyLinkedList<E> linkedList;
public LinkedListStack() {
this.linkedList = new DummyLinkedList<>();
}
@Override
public int getSize() {
return linkedList.getSize();
}
@Override
public boolean isEmpty() {
return linkedList.isEmpty();
}
@Override
public E peek() {
return linkedList.getFirst();
}
@Override
public E pop() {
return linkedList.removeFirst();
}
@Override
public void push(E e) {
linkedList.addFirst(e);
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
res.append("Stack: top ");
res.append(linkedList);
return res.toString();
}
}
三.时间复杂度分析
使用链表实现的栈出栈入栈都是O(1)的操作，与数组栈的复杂度一致，只不过影响LinkedListStack的主要是对象的创建，而影响ArrayStack的主要操作是数组的移动，所以两者效率上是差不多的。
