- 通过底层维护一个链表实现的栈；
- 相对于底层维护一个动态数组实现的栈，链表实现的栈不需要扩容缩容的消耗；
- 不过由于向链表中添加节点，每次都要new一个新的节点出来，在栈中元素过大时，每次入栈都new的消耗可能比缩容扩容的消耗更大；
public class LinkedListStack<E> implements Stack<E> {
private LinkedList<E> list;
public LinkedListStack(){
list = new LinkedList<>();
}
@Override
public int getSize(){
return list.getSize();
}
@Override
public boolean isEmpty(){
return list.isEmpty();
}
@Override
public void push(E e){
list.addFirst(e);
}
@Override
public E pop(){
return list.removeFirst();
}
@Override
public E peek(){
return list.getFirst();
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append("Stack: top ");
res.append(list);
return res.toString();
}
public static void main(String[] args) {
LinkedListStack<Integer> stack = new LinkedListStack<>();
for(int i = 0 ; i < 5 ; i ++){
stack.push(i);
System.out.println(stack);
}
stack.pop();
System.out.println(stack);
}
}
输出：
Stack: top 0->NULL
Stack: top 1->0->NULL
Stack: top 2->1->0->NULL
Stack: top 3->2->1->0->NULL
Stack: top 4->3->2->1->0->NULL
Stack: top 3->2->1->0->NULL
