Java Collections Framework之Stack源码分析缺陷,栈改进版(通过LinkedList实现)(基于JDK1.6)

时间:2021-01-03 17:53:54

栈是重要的数据结构,从数据结构角度看,栈也是线性表,其特殊性在栈的基本操作是线性表的子集。Stack作为最基本的数据结构,在JDK代码中,也有它的实现,java.util.Stack类是继承了Vector类,来实现了栈的基本功能。

1.栈的基本原理

栈(Stack)是限定仅在表尾进行插入或者删除操作的线性表。因此,对于栈来说,表尾端有特殊含义,成为栈顶,表头称之为栈底。

由下图可以看出,栈的最基本的特征是LIFO(Last In First Out),因此栈又被称为后进先出的线性表。

Java Collections Framework之Stack源码分析缺陷,栈改进版(通过LinkedList实现)(基于JDK1.6)
 


2.栈的基本操作

InitStack(&S)--------------构造一个空栈

IsEmpty:判断栈是否为空

ClearStack:清空栈

StackLength:栈S的元素个数,即栈的长度

GetTop:获取栈顶元素

Push:插入新的元素

Pop:删除栈顶元素

 

3.java.util.Stack源码解析

1)数据结构:利用Vector(动态数组)完成后进先出的操作

2)基本方法:

     //初始化一个长度为10 的数组

     构造器      public Stack():

    //放入新元素到栈顶

     public E push(E item){

           //按序更新数组元素(计数器判断最后更新数组元素的索引)

           addElement(item);
           return item;

    }

  /**

   *1.如果由于新增的元素导致数组的长度不够,则把原来的数组尺寸翻倍,并拷贝老数组元素到新的数组

   */

   public synchronized void addElement(E obj) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = obj;
    }

//pop栈顶元素

 public synchronized E pop() {
    E    obj;
    int    len = size();
    obj = peek();
    removeElementAt(len - 1);
    return obj;
    }

4.java.util.stack的缺点

上述源码分析我们知道,Stack利用Vector动态数组实现了后进先出的栈的基本功能,但是数组有下列缺陷:

(1)当数组默认的容量发生改变时,原有的元素需要经过copy到新的数组中,因此pop、push的性能会有较大降低;

(2)这个类是java.util.Vector的子类,由于是继承stack就会将父类的方法继承过来
      如:add(int index,E element)等(具体见Vector的API说明)。这个破坏了stack约定的规则(只能从栈顶进,栈顶出)。

      所以SUN公司自己也给出的解释就是不要轻易用这个类。

(3)这个大概就是为了保持兼容性,积重难返,只能将错就错了,不能修改了


5.实现自己的Stack类

数组的缺点是,当数组长度发生变化时,原有的元素需要经过copy到新的数组中,这样性能有较大的损耗,

而链表最大的优点是插入和删除的性能非常好,Java提供了现成的双向链表类java.util.LinkedList,通过它可以快速编写自己的Stack程序,源码如下:

public class Stack<E>{
    LinkedList<E> list;
    public Stack(){
        list = new LinkedList();
    }
   
    public E pop(){
        return list.removeLast();
    }
   
    public void push(E o){
        list.add(o);
    }
   
    public E getTop(){
        return list.getLast();
    }
   
    public boolean isEmpty(){
        return list.size()==0;
    }
   
    public int size(){
        return list.size();
    }
   
    public static void main(String[] args) {
        Stack stack = new Stack();
        stack.push("bottom");
        stack.push("middle");
        stack.push("top");
        System.out.println(stack.isEmpty());
        System.out.println(stack.getTop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.isEmpty());
    }
}


并发栈ConcurrentStack<E>

并发栈代码:

package study.tune.system.concurrent;
/**
 *  
 */  
import java.util.concurrent.atomic.AtomicReference;  
/**
 * 使用Treiber算法实现Stack:基于CAS以及AtomicReference。
 *  
 * @author yangwm Aug 25, 2010 10:50:17 AM
 * @author ajian005@gmail.com
 */  
public class ConcurrentStack<E> {  
      
    AtomicReference<Node<E>> head = new AtomicReference<Node<E>>();  
    public void push(E item) {  
        Node<E> newHead = new Node<E>(item);  
        Node<E> oldHead;  
        do {  
            oldHead = head.get();  
            newHead.next = oldHead;  
        } while (!head.compareAndSet(oldHead, newHead));  
    }  
      
    public E pop() {  
        Node<E> oldHead;  
        Node<E> newHead;  
        do {  
            oldHead = head.get();  
            if (oldHead == null) {  
                return null;  
            }  
            newHead = oldHead.next;  
        } while (!head.compareAndSet(oldHead, newHead));  
        return oldHead.item;  
    }  
      
    static class Node<E> {  
        final E item;  
        Node<E> next;  
        public Node(E item) {  
            this.item = item;  
        }  
    }  
}  

并发栈测试用例:

package study.tune.system.concurrent;

/**
 *  
 */  
import java.util.Stack;  
import java.util.concurrent.CountDownLatch;  
import java.util.concurrent.CyclicBarrier;  
/**
 * 基准测试:Treiber算法实现Stack、同步实现的Stack  
 *  
 * @author yangwm Aug 25, 2010 11:36:14 AM
 * @author ajian005@gmail.com
 */  
public class StackBenchmark {  
    public static void main(String[] args) throws Exception {  
        StackBenchmark stackBenchmark = new StackBenchmark();  
        stackBenchmark.run();  
    }  
      
      
    private Stack<String> stack = new Stack<String>();  
    private ConcurrentStack<String> concurrentStack = new ConcurrentStack<String>();  
    private static final int THREAD_COUNT = 300;  
    private CountDownLatch latch = new CountDownLatch(THREAD_COUNT);  
    private CyclicBarrier barrier = new CyclicBarrier(THREAD_COUNT);  
      
    public void run() throws Exception {  
        StackTask stackTask = new StackTask();  
        long beginTime = System.currentTimeMillis();  
        for (int i = 0; i < THREAD_COUNT; i++) {  
            new Thread(stackTask).start();  
        }  
        latch.await();  
        long endTime = System.currentTimeMillis();  
        System.out.println("Stack consume Time:  " + (endTime - beginTime) + " ms");  
          
        latch = new CountDownLatch(THREAD_COUNT);  
        barrier = new CyclicBarrier(THREAD_COUNT);  
        ConcurrentStackTask concurrentStackTask = new ConcurrentStackTask();  
        beginTime = System.currentTimeMillis();  
        for (int i = 0; i < THREAD_COUNT; i++) {  
            new Thread(concurrentStackTask).start();  
        }  
        latch.await();  
        endTime = System.currentTimeMillis();  
        System.out.println("ConcurrentStack consume Time:  " + (endTime - beginTime) + " ms");  
    }  
      
    class StackTask implements Runnable {  
          
        @Override  
        public void run() {  
            try {  
                barrier.await();  
            } catch (Exception e) {  
                e.printStackTrace();  
            }  
            for (int i = 0; i < 10; i++) {  
                stack.push(Thread.currentThread().getName());  
                stack.pop();  
            }  
            latch.countDown();  
        }  
          
    }  
    class ConcurrentStackTask implements Runnable {  
          
        @Override  
        public void run() {  
            try {  
                barrier.await();  
            } catch (Exception e) {  
                e.printStackTrace();  
            }  
            for (int i = 0; i < 10; i++) {  
                concurrentStack.push(Thread.currentThread().getName());  
                concurrentStack.pop();  
            }  
            latch.countDown();  
        }  
          
    }  
      
}  
/*
Stack consume Time:  94 ms
ConcurrentStack consume Time:  63 ms
Stack consume Time:  78 ms
ConcurrentStack consume Time:  62 ms
*/ 


参考:http://www.ibm.com/developerworks/java/library/j-jtp04186/index.html