栈（stack）原理

阳光穿透心脏的1/2处 2022-07-15 12:48 231阅读 0赞

######     一.原理 ######

栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

######  **    二.特点** ######

栈的基本特点：先入后出，后入先出。除头尾节点之外，每个元素有一个前驱，一个后继。

java中的Stack 　　Stack 类表示后进先出（LIFO）的对象堆栈。它通过五个操作对类 Vector 进行了扩展 ，允许将向量视为堆栈。它提供了通常的 push 和 pop 操作，以及取堆栈顶点的 peek 方法、测试堆栈是否为空的 empty 方法、在堆栈中查找项并确定到堆栈顶距离的 search 方法。首次创建堆栈时，它不包含项。 Deque 接口及其实现提供了 LIFO 堆栈操作的更完整和更一致的 set，应该优先使用此 set，而非此类。例如： Deque<Integer> stack = new ArrayDeque<Integer>();  　 成员方法：
     
      
      
       E push(E item)  把项压入堆栈顶部。 　
      
       E pop()  移除堆栈顶部的对象，并作为此函数的值返回该对象。 　
      
       E peek()  查看堆栈顶部的对象，但不从堆栈中移除它。 　
      
       boolean empty()  测试堆栈是否为空。 　
      
       int search(Object o)  返回对象在堆栈中的位置，以 1 为基数。　
     
      Stack继承于Vector，Vector本身是一个可增长的对象数组。 
    Stack并不要求其中保存数据的唯一性，当Stack中有多个相同的item时，调用search方法，只返回与查找对象equal并且离栈顶最近的item与栈顶间距离。 empty（） 　　判断stack是否为空，就需要有一个变量来计算当前栈的长度，如果该变量为0，则表示该栈为空。 源码： public boolean empty() {
        return size() == 0;
    }
     size()方法在父类Vector中实现了，在Vector里面有一个变量elementCount来表示容器里元素的个数。如果为0，则表示容器空。 public synchronized int size() {  
        return elementCount;  
    }  
     
     peek（） 　　返回栈顶端的元素，如果栈为空的话，则要抛出异常。 public synchronized E peek() {  
        int     len = size();  
    
        if (len == 0)  
            throw new EmptyStackException();  
        return elementAt(len - 1);  
    }  
     elementAt方法也是在Vector里面实现的，实际上是用一个elementData的Object数组来存储元素的。 public synchronized E elementAt(int index) {  
        if (index >= elementCount) {  
            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);  
        }  
    
        return elementData(index);  
    }  
    
    @SuppressWarnings("unchecked")  
    E elementData(int index) {  
        return (E) elementData[index];  
    } 
     peek（） 　　将栈顶的元素弹出来，如果栈里有元素，就取最顶端的那个，否则就要抛出异常。 public synchronized E pop() {  
    　    E   obj;  
      　  int  len = size();  
    
       　 obj = peek();  
       　 removeElementAt(len - 1);  
    
       　 return obj;  
    } 
     　　通过peek()取到顶端的元素之后，我们需要用removeElementAt()方法将最顶端的元素移除。 
    removeElementAt()方法定义在vector中。 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; /* to let gc do its work */  
    }  
     　　这里用待删除元素的后面元素依次覆盖前面一个元素。这样，就相当于将数组的实际元素长度给缩短了。 push（） 　　将数据入栈 public E push(E item) {  
        addElement(item);  
    
        return item;  
    }
     　　将要入栈的元素放到数组的末尾，再将数组长度加1就可以了。addElement（）方法也在vector中（好父亲啊）。 public synchronized void addElement(E obj) {  
        modCount++;  
        ensureCapacityHelper(elementCount + 1);  
        elementData[elementCount++] = obj;  
    }  
    
    private void ensureCapacityHelper(int minCapacity) {  
        // overflow-conscious code 
        if (minCapacity - elementData.length > 0)  
            grow(minCapacity);  
    }  
    
    private void grow(int minCapacity) {  
        // overflow-conscious code 
        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);  
    }  
    
    private static int hugeCapacity(int minCapacity) {  
        if (minCapacity < 0) // overflow 
            throw new OutOfMemoryError();  
        return (minCapacity > MAX_ARRAY_SIZE) ?  
            Integer.MAX_VALUE :  
            MAX_ARRAY_SIZE;  
    } 
     search（） 　　找到一个最靠近栈顶端的匹配元素，然后返回这个元素到栈顶的距离 public synchronized int search(Object o) {  
        int i = lastIndexOf(o);  
    
        if (i >= 0) {  
            return size() - i;  
        }  
        return -1;  
    } 
     对应在vector里面的实现也相对容易理解： public synchronized int lastIndexOf(Object o) {  
        return lastIndexOf(o, elementCount-1);  
    }  
    
    public synchronized int lastIndexOf(Object o, int index) {  
        if (index >= elementCount)  
            throw new IndexOutOfBoundsException(index + " >= "+ elementCount);  
    
        if (o == null) {  
            for (int i = index; i >= 0; i--)  
                if (elementData[i]==null)  
                    return i;  
        } else {  
            for (int i = index; i >= 0; i--)  
                if (o.equals(elementData[i]))  
                    return i;  
        }  
        return -1;  
    }  
     
     
     
      
     
      
      
       lastIndexOf是从数组的末端往前遍历，如果找到这个对象就返回。如果到头了，还未找到就返回个-1。 栈和队列的区别 队列是FIFO的（先进先出），堆栈是FILO的（现今后出） 栈是限定只能在表的一端进行插入和删除操作的线性表。 队列是限定只能在表的一端进行插入和在另一端进行删除操作的线性表 栈只能从头部取数据，也就最先放入的需要遍历整个栈最后才能取出来，而且在遍历数据的时候还得为数据开辟临时空间；  队列基于地址指针进行遍历，而且可以从头或尾部开始遍历，但不能同时遍历，无需开辟临时空间，因为在遍历的过程中不影像数据结构，速度要快的多。