一、Stack源码分析

1.继承结构

　栈是数据结构中一种很重要的数据结构类型，因为栈的后进先出功能是实际的开发中有很多的应用场景。Java API中提供了栈（Stacck)的实现。   Stack类继承了Vector类，而Vector类继承了AbstractList抽象类，实现了List接口，Cloneable接口，RandomAcces接口以及Serializable接口，需要指出的Vector内部还有两个内部类ListItr和Itr，Itr在继承Vector的同时实现了Iterator接口，而ListItr在继承了Itr类的同时实现了ListIterator接口。

2、图解

 

3、源码分析

Stack类里的方法：   1).public Stack() //一个无参构造方法，能直接创建一个Stack   2).public E push(E item)   //向栈顶压入一个项   3).public synchronized E pop()    //移走栈顶对象，将该对象作为函数值返回   4).public synchronized E peek()   //查找栈顶对象，而不从栈中移走。   5).public boolean empty()    //测试栈是否为空   6).public synchronized int search(Object o)  //返回栈中对象的位置，从1开始。   private static final long serialVersionUID = 1224463164541339165L; 其他值的方法是从Vector类继承而来，通过源码可以发现Vector有几个属性值：   protected Object[] elementData   //elementData用于保存Stack中的每个元素；   protected int elementCount   //elementCount用于动态的保存元素的个数，即实际元素个数   protected int capacityIncrement  //capacityIncrement用来保存Stack的容量（一般情况下应该是大于elementCount）   private static final int MAX_ARRAY_SIZE = 2147483639 ; //MAX_ARRAY_SIZE 用于限制Stack能够保存的最大值数量 通过这几属性我们可以发现，Stack底层是采用数组来实现的。 

 

1、public E push(E item)   //向栈顶压入一个项

 

[java]  

1.    //向栈顶压入一个项  
2.    public E push(E item) {  
3. //调用Vector类里的添加元素的方法  
4.        addElement(item);  
5.   
6.        return item;  
7.    }  
8.   
9.    public synchronized void addElement(E obj) {  
10. //通过记录modCount参数来实现Fail-Fast机制  
11.        modCount++;  
12. //确保栈的容量大小不会使新增的数据溢出  
13.        ensureCapacityHelper(elementCount + 1);  
14.        elementData[elementCount++] = obj;  
15.    }  
16.   
17.    private void ensureCapacityHelper(int minCapacity) {  
18.        //防止溢出。超出了数组可容纳的长度，需要进行动态扩展！！！    
19.        if (minCapacity - elementData.length > 0)  
20.            grow(minCapacity);  
21.    }  
22.   
23.    //数组动态增加的关键所在  
24.    private void grow(int minCapacity) {  
25.        // overflow-conscious code  
26.        int oldCapacity = elementData.length;  
27. //如果是Stack的话，数组扩展为原来的两倍  
28.        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?  
29.                                         capacityIncrement : oldCapacity);  
30.   
31. //扩展数组后需要判断两次  
32. //第1次是新数组的容量是否比elementCount + 1的小（minCapacity;）  
33.        if (newCapacity - minCapacity < 0)  
34.            newCapacity = minCapacity;  
35.   
36. //第1次是新数组的容量是否比指定最大限制Integer.MAX_VALUE - 8 大  
37. //如果大，则minCapacity过大，需要判断下  
38.        if (newCapacity - MAX_ARRAY_SIZE > 0)  
39.            newCapacity = hugeCapacity(minCapacity);  
40.        elementData = Arrays.copyOf(elementData, newCapacity);  
41.    }  
42.   
43.    //检查容量的int值是不是已经溢出   
44.    private static int hugeCapacity(int minCapacity) {  
45.        if (minCapacity < 0) // overflow  
46.            throw new OutOfMemoryError();  
47.        return (minCapacity > MAX_ARRAY_SIZE) ?  
48.            Integer.MAX_VALUE :  
49.            MAX_ARRAY_SIZE;  
50.    }  

2、public synchronized E peek()   //查找栈顶对象，而不从栈中移走

 

 

[java]  

1.    //查找栈顶对象，而不从栈中移走。  
2.    public synchronized E peek() {  
3.        int len = size();  
4.   
5.        if (len == 0)  
6.            throw new EmptyStackException();  
7.        return elementAt(len - 1);  
8.    }  
9.   
10.    //Vector里的方法，获取实际栈里的元素个数  
11.    public synchronized int size() {  
12.        return elementCount;  
13.    }  
14.   
15.    public synchronized E elementAt(int index) {  
16.        if (index >= elementCount) {  
17.     //数组下标越界异常  
18.            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);  
19.        }  
20.   
21. //返回数据下标为index的值  
22.        return elementData(index);  
23.    }  
24.   
25.    @SuppressWarnings("unchecked")  
26.    E elementData(int index) {  
27.        return (E) elementData[index];  
28.    }  

 

3、public synchronized E pop()    //移走栈顶对象，将该对象作为函数值返回

 

[java]  

1.    //移走栈顶对象，将该对象作为函数值返回  
2.    public synchronized E pop() {  
3.        E obj;  
4.        int len = size();  
5.   
6.        obj = peek();  
7. //len-1的得到值就是数组最后一个数的下标  
8.        removeElementAt(len - 1);  
9.   
10.        return obj;  
11.    }  
12.   
13.    //Vector里的方法  
14.    public synchronized void removeElementAt(int index) {  
15.        modCount++;  
16. //数组下标越界异常出现的情况  
17.        if (index >= elementCount) {  
18.            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);  
19.        } else if (index < 0) {  
20.            throw new ArrayIndexOutOfBoundsException(index);  
21.        }  
22.   
23.  //数组中index以后的元素个数，由于Stack调用的该方法，j始终为0  
24.        int j = elementCount - index - 1;  
25.        if (j > 0) {  
26.     // 数组中index以后的元素，整体前移，（这个方法挺有用的！！）    
27.            System.arraycopy(elementData, index + 1, elementData, index, j);  
28.        }  
29.        elementCount--;  
30.        elementData[elementCount] = null; /* to let gc do its work */  
31.    }  

 

4.public boolean empty()    //测试栈是否为空

 

[java]  

1. public boolean empty() {  
2.     return size() == 0;  
3. }  

 

5.public synchronized int search(Object o)  //返回栈中对象的位置，从1开始。

[java]  

1.    // 返回栈中对象的位置，从1开始。如果对象o作为项在栈中存在，方法返回离栈顶最近的距离。  
2.    //栈中最顶部的项被认为距离为1。  
3.    public synchronized int search(Object o) {  
4. //lastIndexOf返回一个指定的字符串值最后出现的位置,  
5. //在一个字符串中的指定位置从后向前搜索  
6.        int i = lastIndexOf(o);  
7.   
8.        if (i >= 0) {  
9.     //所以离栈顶最近的距离需要相减  
10.            return size() - i;  
11.        }  
12.        return -1;  
13.    }  
14.   
15.    //Vector里的方法  
16.    public synchronized int lastIndexOf(Object o) {  
17.        return lastIndexOf(o, elementCount-1);  
18.    }  
19.   
20.    public synchronized int lastIndexOf(Object o, int index) {  
21.        if (index >= elementCount)  
22.            throw new IndexOutOfBoundsException(index + " >= "+ elementCount);  
23.   
24. //Vector、Stack里可以放null数据  
25.        if (o == null) {  
26.            for (int i = index; i >= 0; i--)  
27.                if (elementData[i]==null)  
28.                    return i;  
29.        } else {  
30.            for (int i = index; i >= 0; i--)  
31.                if (o.equals(elementData[i]))  
32.                    return i;  
33.        }  
34.        return -1;  
35.    }  

 

二、个人简单实现

栈单链表实现：没有长度限制，并且出栈和入栈速度都很快

 

[java]  

1. public class LinkedListStack {  
2. <pre name="code" class="java">    private LinkedList linkedList = new LinkedList();  
3.   
4.     //入栈  
5.     public void push(Object obj) {  
6.         linkedList.insertHead(obj);  
7.     }  
8. <pre name="code" class="java">    //向栈顶压入一个项  
9.     public E push(E item) {  
10.     //调用Vector类里的添加元素的方法  
11.         addElement(item);  
12.   
13.         return item;  
14.     }  
15.   
16.     public synchronized void addElement(E obj) {  
17.     //通过记录modCount参数来实现Fail-Fast机制  
18.         modCount++;  
19.     //确保栈的容量大小不会使新增的数据溢出  
20.         ensureCapacityHelper(elementCount + 1);  
21.         elementData[elementCount++] = obj;  
22.     }  
23.   
24.     private void ensureCapacityHelper(int minCapacity) {  
25.         //防止溢出。超出了数组可容纳的长度，需要进行动态扩展！！！    
26.         if (minCapacity - elementData.length > 0)  
27.             grow(minCapacity);  
28.     }  
29.   
30.     //数组动态增加的关键所在  
31.     private void grow(int minCapacity) {  
32.         // overflow-conscious code  
33.         int oldCapacity = elementData.length;  
34.     //如果是Stack的话，数组扩展为原来的两倍  
35.         int newCapacity = oldCapacity + ((capacityIncrement > 0) ?  
36.                                          capacityIncrement : oldCapacity);  
37.   
38.     //扩展数组后需要判断两次  
39.     //第1次是新数组的容量是否比elementCount + 1的小（minCapacity;）  
40.         if (newCapacity - minCapacity < 0)  
41.             newCapacity = minCapacity;  
42.   
43.     //第1次是新数组的容量是否比指定最大限制Integer.MAX_VALUE - 8 大  
44.     //如果大，则minCapacity过大，需要判断下  
45.         if (newCapacity - MAX_ARRAY_SIZE > 0)  
46.             newCapacity = hugeCapacity(minCapacity);  
47.         elementData = Arrays.copyOf(elementData, newCapacity);  
48.     }  
49.   
50.     //检查容量的int值是不是已经溢出   
51.     private static int hugeCapacity(int minCapacity) {  
52.         if (minCapacity < 0) // overflow  
53.             throw new OutOfMemoryError();  
54.         return (minCapacity > MAX_ARRAY_SIZE) ?  
55.             Integer.MAX_VALUE :  
56.             MAX_ARRAY_SIZE;  
57.     }  

[java]  

1.     //出栈   
2.     public Object pop() throws Exception {   
3.         return linkedList.deleteHead();   
4.     }   
5.     public void display() {   
6.         linkedList.display();   
7.     }   
8.     /** * 栈单链表实现：没有长度限制，并且出栈和入栈速度都很快 */   
9.     private class LinkedList {   
10.         private class Node {   
11.             Node next;  
12.             //下一个结点的引用   
13.             Object data;  
14.             //结点元素   
15.             public Node(Object data) {   
16.                 this.data = data;   
17.             }   
18.         }   
19.           
20.         private Node head;   
21.         public LinkedList() {  
22.             this.head = null;  
23.         }   
24.     }   
25.     public void insertHead(Object data) {   
26.         Node node = new Node(data);   
27.         node.next = head; head = node;   
28.     }   
29.     public Object deleteHead() throws Exception {   
30.         if (head == null)   
31.             throw new Exception("Stack is empty!");   
32.         Node temp = head;  
33.         //head = temp.next;也行   
34.         head = head.next;   
35.         return temp.data;   
36.     }   
37.     public void display() {   
38.         if (head == null)   
39.             System.out.println("empty");   
40.         System.out.print("top -> bottom : | ");   
41.         Node cur = head;   
42.         while (cur != null) {   
43.             System.out.print(cur.data.toString() + " | ");   
44.             cur = cur.next;   
45.         }   
46.         System.out.print("\n");   
47.     }  
48. }  
49. }  

测试：

 

[java]  

1.   
2. public void testLinkedListStack() {  
3.     LinkedListStack lls = new LinkedListStack();  
4.   
5.     lls.push(1);  
6.     lls.push(2);  
7.     lls.push(3);  
8.     lls.display();  
9.     try {  
10.         System.out.println(lls.pop());  
11.     } catch (Exception e) {  
12.         e.printStackTrace();  
13.     }  
14.     lls.display();  
15. }  

top -> bottom : | 3 | 2 | 1 | 

3 top -> bottom : | 2 | 1 |