什么是栈？

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

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

　　分类：

　　　　（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);
　　}


 总结：

　　数据结构中包含了两部分信息：1、一个固定大小的数组，2、一个计数器elementCount

　　push 添加对象，在添加时需要校验数组大小是否越界，如果数组大小不够，则需要进行扩容。每次添加都是在当前数组elementCount的下一个节点进行添加。

　　　　因此数组大小并非当前栈的大小，栈的大小通过计数器elementCount进行标记。每次访问需要根据elementCount进行定位。

　　pop 弹出对象，在弹出时会调用remove方法将elementCount-1这个元素清空，同时elementCount– 。

　　peek 获取栈顶对象，在获取栈顶对象即获取 数组 len-1下标的对象，此时不对原数据进行任何操作 。

　　

　　

 

 

版权声明：本文为xiaolangabc原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/xiaolangabc/p/10821653.html