JDK学习之Stack

今天我们学习一下JDK中栈的实现，栈也是一种基本的数据结构，遵循后进先出(LIFO)，废话少说，先看一下UML继承关系。

1，UML继承关系图：

 

 

这里我们看到其主要继承Vector，下边我们看下其主要方法的实现方式。

 

2，JDK中主要方法的实现方式

增加一条记录，push(E item)

 

    public E push(E item) {
	addElement(item);

	return item;
    }

内部调用addElement(item)方法，这个方法是继承自Vector，我们看下addElement方法的具体实现：

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

 

再看下ensureCapacityHelper方法：

  private void ensureCapacityHelper(int minCapacity) {
	int oldCapacity = elementData.length;
	if (minCapacity > oldCapacity) {
	    Object[] oldData = elementData;
	    int newCapacity = (capacityIncrement > 0) ?
		(oldCapacity + capacityIncrement) : (oldCapacity * 2);
    	    if (newCapacity < minCapacity) {
		newCapacity = minCapacity;
	    }
	    elementData = new Object[newCapacity];
	    System.arraycopy(oldData, 0, elementData, 0, elementCount);
	}
    }

 

可以看到其内部使用数组来实现，跟ArrayList是相同的，区别是addElement方法前加了synchronized修饰符，给调用这个方法的对象加了一把锁，防止同一时间多个对象访问这个方法，保证的线程安全，但是会带来很大的系统开销。

弹出一条数据，pop()：

    public synchronized E pop() {
	E	obj;
	int	len = size();

	obj = peek();
	removeElementAt(len - 1);

	return obj;
    }

 调用的peek方法

    public synchronized E peek() {
	int	len = size();

	if (len == 0)
	    throw new EmptyStackException();
	return elementAt(len - 1);
    }

 

 直接返回数组的最后一条记录，即最后压入的数据项，同样是同步方法；

查找一条记录，search(Object o) ：

 

    public synchronized int search(Object o) {
	int i = lastIndexOf(o);

	if (i >= 0) {
	    return size() - i;
	}
	return -1;
    }

  调用了父类的lastIndexOf()方法：

    public synchronized int lastIndexOf(Object elem, int index) {
        if (index >= elementCount)
            throw new IndexOutOfBoundsException(index + " >= "+ elementCount);

	if (elem == null) {
	    for (int i = index; i >= 0; i--)
		if (elementData[i]==null)
		    return i;
	} else {
	    for (int i = index; i >= 0; i--)
		if (elem.equals(elementData[i]))
		    return i;
	}
	return -1;
    }

 

实现方法同ArrayList(参考JDK学习之ArrayList http://masterzs.iteye.com/blog/635792)。

3 典型应用：

回文，输入一串字符串，反方向打印出来，

 

 

            Stack stack = new Stack();
                Scanner scanner=new Scanner(System.in);   
	System.out.print("Please input some character:");   
	 String inputString=scanner.next();  //获取字符串值   
	 System.out.println("The string you input is:  "+inputString+" ");   		
	        for(int index =0;index<= inputString.length()-1;index++){
		stack.push(inputString.charAt(index));
	 		
	                                        }
	System.out.print("The string you input Reverse is: ");
	while(stack.size()!=0)
	             System.out.print(stack.pop());
			
	}

 

 

 4，总结

在实际项目中从未使用过：（，Java的栈帧用于存储方法调用的状态，栈的特点是存取速度快，一般存储运行时程序的状态，调用方法的参数，返回值，状态信息之类的运行参数，

具体项目中很少用到。