首页 > > 程序设计 > Java技术 >

深入学习数据结构之栈（一）

2019-05-08 07:31:08来源：博客园阅读 ()

什么是栈？

　　定义：一种运算受限的线性表。其限制是仅允许在线性表的一端进行插入和删除运算。可操作的一端被称为栈顶，相对地，把另一端称为栈底，栈底不可进行操作。

所以栈中的数据遵循 “先进后出” 即只能操作栈顶的数据。

　　分类：

　　　　（1）静态栈：以数组作为数据的存储。

　　　　（2）动态栈：以链表作为数据的存储方式。

　　栈的操作：

　　　　（1）初始化栈：如果是数组结构，需要在初始化时确定栈的大小，此时栈无法动态扩充。如果是链表结构则不需要初始化的时候执行，

　　　　（2）入栈 push：

　　　　　　如图所示，将数据4压入栈中，此时4为栈顶元素

　　　　（3）出栈 pop ：取出栈顶元素

　　　　　　如图所示，将刚才压入栈的4弹出栈，

　　　　（4）栈顶peek：获取栈顶元素，此时不弹出栈顶元素，仅仅获取数据。

　　　　（5）判空 is_empty ：判断栈是否为空。注意如果是数组模式则不能直接通过数组大小进行判断。

　　　　（6）清空 clear：清空栈中所有内容。注意数组模式和链表模式区别

　　Java Stack栈实现原理：

　·　　Stack类层次结构图：

　　　 分析：从类结构图可以初步看出，Java中的stack是基于数组实现的。

　　　源码分析：

protected Object[] elementData; // 对象数组
　　protected int elementCount;  // 对象数量（无法通过数组大小获取实际大小，需要额外定义）　　　　
　
　  // push添加
　　public E push(E item) {
　　　　　　addElement(item);
　　　　　　return item;
　　　}
　　public synchronized void addElement(E obj) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
    }
　　
　　private void ensureCapacityHelper(int minCapacity) {
　　　　if (minCapacity - elementData.length > 0)
　　　　　　grow(minCapacity);
　　}

　　private void grow(int minCapacity) {
　　　　int oldCapacity = elementData.length;
　　　　int newCapacity = oldCapacity + ((capacityIncrement > 0) ?　capacityIncrement : oldCapacity);
　　　　if (newCapacity - minCapacity < 0)
　　　　　　newCapacity = minCapacity;
　　　　if (newCapacity - MAX_ARRAY_SIZE > 0)
　　　　　　newCapacity = hugeCapacity(minCapacity);
　　　　elementData = Arrays.copyOf(elementData, newCapacity);
　　}

　　// pop弹出
　　public synchronized E pop() {
        E obj;
        int len = size();
        obj = peek();
        removeElementAt(len - 1);
        return obj;
   }
 　public synchronized void removeElementAt(int index) {
        modCount++;
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
        }
        else if (index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        int j = elementCount - index - 1;
        if (j > 0) {
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        elementCount--;
        elementData[elementCount] = null; 
    }


　　// 查看栈顶元素
　　public synchronized E peek() {
        int     len = size();
        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);
　　}
　　public synchronized E elementAt(int index) {
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
        }
        return elementData(index);
　　}