http://www.cnblogs.com/leefreeman/archive/2013/05/16/3082400.html
http://www.cnblogs.com/leefreeman/archive/2013/05/16/3082400.html
众所周知Stack（栈）是一种先进后出的数据结构。当中有两个重要的方法：push（进栈）和pop（出栈）。
几乎所有语言在实现栈时，都会实现这两个方法，进栈和出栈。而栈这种数据结构在多数时候用来插入和删除元素（进栈则是在顶部插入元素，出栈则是从顶部删除元素），较少情况会用来查找元素。所以从实现方式上，大多是以链表方式实现而非数值方式实现（在插入删除方法上，链表效率优于数组效率）。
1: public class Stack<E> extends Vector<E> {
2: /**
3: * Creates an empty Stack.
4: */
5: public Stack() {
6: }
7:
8: /**
9: * Pushes an item onto the top of this stack. This has exactly
10: * the same effect as:
11: * <blockquote><pre>
12: * addElement(item)</pre></blockquote>
13: *
14: * @param item the item to be pushed onto this stack.
15: * @return the <code>item</code> argument.
16: * @see java.util.Vector#addElement
17: */
18: public E push(E item) {
19: addElement(item);
20:
21: return item;
22: }
23:
24: /**
25: * Removes the object at the top of this stack and returns that
26: * object as the value of this function.
27: *
28: * @return The object at the top of this stack (the last item
29: * of the <tt>Vector</tt> object).
30: * @exception EmptyStackException if this stack is empty.
31: */
32: public synchronized E pop() {
33: E obj;
34: int len = size();
35:
36: obj = peek();
37: removeElementAt(len - 1);
38:
39: return obj;
40: }
41:
42: /**
43: * Looks at the object at the top of this stack without removing it
44: * from the stack.
45: *
46: * @return the object at the top of this stack (the last item
47: * of the <tt>Vector</tt> object).
48: * @exception EmptyStackException if this stack is empty.
49: */
50: public synchronized E peek() {
51: int len = size();
52:
53: if (len == 0)
54: throw new EmptyStackException();
55: return elementAt(len - 1);
56: }
57:
58: /**
59: * Tests if this stack is empty.
60: *
61: * @return <code>true</code> if and only if this stack contains
62: * no items; <code>false</code> otherwise.
63: */
64: public boolean empty() {
65: return size() == 0;
66: }
67:
68: /**
69: * Returns the 1-based position where an object is on this stack.
70: * If the object <tt>o</tt> occurs as an item in this stack, this
71: * method returns the distance from the top of the stack of the
72: * occurrence nearest the top of the stack; the topmost item on the
73: * stack is considered to be at distance <tt>1</tt>. The <tt>equals</tt>
74: * method is used to compare <tt>o</tt> to the
75: * items in this stack.
76: *
77: * @param o the desired object.
78: * @return the 1-based position from the top of the stack where
79: * the object is located; the return value <code>-1</code>
80: * indicates that the object is not on the stack.
81: */
82: public synchronized int search(Object o) {
83: int i = lastIndexOf(o);
84:
85: if (i >= 0) {
86: return size() - i;
87: }
88: return -1;
89: }
可以看到Stack继承Vector，而Vector是由数组实现的集合类，他包含了大量集合处理的方法。而Stack之所以继承Vector，是为了复用Vector中的方法，来实现进栈（push）、出栈(pop)等操作。
这里就是质疑Stack的地方，既然只是为了实现栈，为什么不用链表来单独实现，只是为了复用简单的方法而迫使它继承Vector（Stack和Vector本来是毫无关系的）。这使得Stack在基于数组实现上效率受影响，另外因为继承Vector类，Stack可以复用Vector大量方法，这使得Stack在设计上不严谨，当我们看到Vector中的：
1: public void add(int index, E element) {
2: insertElementAt(element, index);
3: }
可以在指定位置添加元素，这与Stack 的设计理念相冲突（栈只能在栈顶添加或删除元素）。
所以Java中的Stack实现确实值得商榷。
使用链表模拟Stack
一个单纯的栈，其实可以只包含以下方法：
boolean empty()
测试堆栈是否为空。
T peek()
查看堆栈顶部的对象，但不从堆栈中移除它。
T pop()
移除堆栈顶部的对象，并作为此函数的值返回该对象。
void push(T item)
把项压入堆栈顶部。
测试堆栈是否为空。
T peek()
查看堆栈顶部的对象，但不从堆栈中移除它。
T pop()
移除堆栈顶部的对象，并作为此函数的值返回该对象。
void push(T item)
把项压入堆栈顶部。
我们使用链表来模拟一个栈：
1: public class Stack<T> {
2: private Node<T> top;
3:
4: /**
5: * 返回栈顶元素
6: *
7: * @return
8: */
9: public T peek() {
10: return top.getData();
11: }
12:
13: /**
14: * 从栈中弹出项
15: * @return
16: */
17: public T pop() {
18: T data = null;
19: if (top != null) {
20: data = top.getData();
21: top = top.getNextNode();
22: }
23: return data;
24: }
25:
26: /**
27: * 向栈内压入项
28: *
29: * @param data
30: */
31: public void push(T data) {
32: Node<T> node = new Node<T>();
33: node.setData(data);
34: if (top == null) {
35: top = node;
36: } else {
37: node.setNextNode(top);
38: top.setPreNode(node);
39: top = node;
40: }
41: }
42:
43: /**
44: * 是否是空栈
45: *
46: * @return
47: */
48: public boolean isEmpty() {
49: return top == null;
50: }
51: }
1: public class Node<T> {
2: private T data;
3: // 前驱节点
4: private Node<T> preNode;
5: // 后继节点
6: private Node<T> nextNode;
7:
8: public T getData() {
9: return data;
10: }
11:
12: public void setData(T data) {
13: this.data = data;
14: }
15:
16: public Node<T> getPreNode() {
17: return preNode;
18: }
19:
20: public void setPreNode(Node<T> preNode) {
21: this.preNode = preNode;
22: }
23:
24: public Node<T> getNextNode() {
25: return nextNode;
26: }
27:
28: public void setNextNode(Node<T> nextNode) {
29: this.nextNode = nextNode;
30: }
31:
32: }
