Java中的栈

Java中的Stack是早期的遗留类，Sun/oracle已经不推荐使用，现在只是为了兼容遗留代码而保留.

遗留实现

如下面的代码所示，java.util.Stack中的实现是基于动态数组实现的，而Vector同样是一个被废弃的类。

个人看来，这个实现有两个问题

• 基于Vector,需要同步因而性能损失很严重
• 基于数组而非链表，栈很大时需要多次扩容，带来不必要的性能损失

public class Stack<E> extends Vector<E> {     /**      * Creates an empty Stack.      */     public Stack() {     }      public E push(E item) {         addElement(item);          return item;     }      public synchronized E pop() {         E       obj;         int     len = size();          obj = peek();         removeElementAt(len - 1);          return obj;     }      public synchronized E peek() {         int     len = size();          if (len == 0)             throw new EmptyStackException();         return elementAt(len - 1);     }       public boolean empty() {         return size() == 0;     }       public synchronized int search(Object o) {         int i = lastIndexOf(o);          if (i >= 0) {             return size() - i;         }         return -1;     }      /** use serialVersionUID from JDK 1.0.2 for interoperability */     private static final long serialVersionUID = 1224463164541339165L; }

自己简单的封装

下面是基于LinkedList封装的Stack

这里的栈是一个装饰器。

import java.util.LinkedList; import java.util.NoSuchElementException;  public class Stack<T> {     private LinkedList<T> stack;      Stack() {         stack = new LinkedList<>();     }      public void push(T o) {         stack.add(o);     }      public T pop() {         if (size() <= 0) {             throw new NoSuchElementException("Stack is Empty.");         }         return stack.removeLast();     }      public T peek() {         if (size() <= 0) {             throw new NoSuchElementException("Stack is Empty.");         }         return stack.getLast();     }      public boolean empty() {         return stack.size() == 0;     }      public int size() {         return stack.size();     } }