- 通過底層維護一個鏈表實現(xiàn)的棧筷屡；
- 相對于底層維護一個動態(tài)數(shù)組實現(xiàn)的棧剃根，鏈表實現(xiàn)的棧不需要擴容縮容的消耗菲宴；
- 不過由于向鏈表中添加節(jié)點，每次都要new一個新的節(jié)點出來度秘，在棧中元素過大時顶伞，每次入棧都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
