栈的基本原理,实现自己的堆栈

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



1.栈的基本原理



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



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





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.如果由于新增的元素导致数组的长度不够，则把原来的数组尺寸翻倍，并拷贝老数组元素到新的数组

   *2.

   *

   *

   */

   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）当数组默认的容量发生改变时，push的性能会有较大降低


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