Java中的栈

共计 1253 个字符，预计需要花费 4 分钟才能阅读完成。

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();
}
}