数据结构---堆栈以及Stack源码分析

冷不防 2024-04-18 21:01 152阅读 0赞

堆栈是限制在表的一端进行插入和删除的线性表，简称为栈，允许插入和删除的一端称为栈顶，另一端称为栈底，当表中没有元素的时候称为空栈。栈是先进后出。

栈丛实现层次上分为顺序栈和链栈，顺序栈即底层的存储地址是连续的即数组，链栈是是用链表。

顺序栈：

public class ListStack {
    	private final int MAXSIZE = 100;
    	private Object data[];
    	private int last=0;
    	//默认长度
    	int defaultLength = 20;
    	
    	public ListStack() {
    		data = new Object[defaultLength];
    	}
    	public ListStack(int len) {
    		data=new Object[len]; 
    	}
    	
    	public void push(Object obj) {
    		if(last>=data.length) {
    			data = Arrays.copyOf(data, data.length, Object[].class);
    		}
    		data[last++] = obj;
    	}
    	
    	public void pop() {
    		if(last==0) {
    			System.err.println("栈为空");
    			return;
    		}
    		data[last-1]=null;
    		last--;
    	}
    }

链栈：

public class LinkNode<V> {
    	//数据
    	V data;
    	//下一个节点
    	LinkNode<V> next =null;
    	public LinkNode(V data,LinkNode<V> next) {
    		this.data=data;
    		this.next=next;
    	}
    }
    public class LinkStack<V> {
    	private LinkNode<V>  header = new LinkNode<V>(null, null);
    	LinkNode<V> last = header;
    	
    	public void push(V v) {
    		LinkNode<V>  node = new LinkNode<V>(v, null);
    		//第一次插入
    		if(header.next==null) {
    			header.next=node;
    			last.next=node;
    		}else {
    			node.next=header.next;
    			header.next=node;
    		}
    	}
    	public void pop() {
    		if(header.next.next!=null) {
    			header.next=header.next.next;
    		}else {
    			System.err.println("栈已经空了");
    		}
    	}
    	
    }

看一下java封装的Stack类：

public class Stack<E> extends Vector<E> {
      
        public Stack() {
        }
    //入栈方法
        public E push(E item) {
            addElement(item);
    
            return item;
        }
    //出栈方法
        public synchronized E pop() {
            E       obj;
            int     len = size();
    
            obj = peek();
            removeElementAt(len - 1);
    
            return obj;
        }
    //查看栈顶元素
        public synchronized E peek() {
            int     len = size();
    
            if (len == 0)
                throw new EmptyStackException();
            return elementAt(len - 1);
        }
    //判断栈是否为空
        public boolean empty() {
            return size() == 0;
        }
    
        public synchronized int search(Object o) {
            int i = lastIndexOf(o);
    
            if (i >= 0) {
                return size() - i;
            }
            return -1;
        }
    
        /** use serialVersionUID from JDK 1.0.2 for interoperability */
        private static final long serialVersionUID = 1224463164541339165L;
    }
    //Stack类并不能找出他的数据结构以及出栈入栈的操作，所以看一下他的父类
    属性：
    //存储元素的数组（顺序栈）
     protected Object[] elementData;
     //数组元素长度
     protected int elementCount;
     //扩容因子
     protected int capacityIncrement; 
     构造方法：
       public Vector(int initialCapacity, int capacityIncrement) {
            super();
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            this.elementData = new Object[initialCapacity];
            this.capacityIncrement = capacityIncrement;
        }
        public Vector(int initialCapacity) {
            this(initialCapacity, 0);
        }
         public Vector() {
            this(10);
        } 
        //真正执行入栈饿方法
         public synchronized void addElement(E obj) {
            modCount++;
            //确保不会越界
            ensureCapacityHelper(elementCount + 1);
            elementData[elementCount++] = 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; /* to let gc do its work */
        }

通过看源码可以知道出栈以及入栈都是通过synchronized 修饰的，所以都是线程安全的。