在前面的几章博客中,我与同学们一起熟悉了线性表这个基础的数据结构,今天我们要学习的这个数据结构和线性表有着紧密的联系,它就是——

    栈的定义很简单:

    栈(Stack)是限定仅在表尾进行插入和删除操作的线性表。

    我们一起来解读一下栈的定义,首先栈是一个线性表,因此它也是一个具有零个或多个数据元素的有限序列;其次栈只允许在表的尾部进行插入和删除元素,而不像是普通的线性表能够在任意位置添加删除元素。

    我们把栈中允许插入和删除的一端称为栈顶(top),另一端称为栈底(bottom),不含任何数据元素的栈称为空栈。栈又被称为后进先出(Last In First Out)的线性表,简称LIFO结构。栈的插入操作,叫作进栈,也叫做压栈,入栈;栈的删除操作,叫做出栈,有的也叫做弹栈。

    进栈,出栈的操作如下图所示:

    e60944f45c4949d6a3368821c4395ef5.png

    那么现在我们就一起来定义一下栈的抽象数据类型:

    	ADT 栈(Stack){
    		Data: 
    		同线性表。元素具有相同的类型,相邻元素具有前驱和后继关系。
    		
    		Operation:
    		E push(E item)                     //将新的元素压入栈顶
    		E pop()                            //弹出栈顶的元素
    		E peek()                           //返回栈顶的元素,但不从栈中删除
    		boolean empty()                    //检查栈是否为空
    		int search(Object o)               //返回某个元素在栈中基于1的位置,也就是该元素到栈顶的距离,比如栈顶元素的值应该为1
    		void clear();                      //清空整个栈
    	}
    

    首先我们先根据ADT抽象出一个MyStack的接口

    	public interface MyStack<E> {
    	public E push(E item);                    //将新的元素压入栈顶
    	public E pop();                           //弹出栈顶的元素
    	public E peek();                          //返回栈顶的元素,但不从栈中删除
    	public boolean empty();                   //检查栈是否为空
    	public int search(Object o);              //返回某个元素在栈中基于1的位置,也就是该元素到栈顶的距离,比如栈顶元素的值应该为1
    	public void clear();                      //清空整个栈
    }
    

    接下来我们就一起来完成一个在内存中顺序存储的栈MyArrayStack。首先我们来写这个数据结构的私有成员,一个能装泛型E的数组,size表示列表中元素的数目,以及一个默认的初识数组大小。

    	private E[] contents;
    	//在声明MyArrayStack时,如不指明大小,则初始大小为10
    	private static final int DEFAULT_CAPACITY = 10;
    	private int size;
    	
    	//两种构造函数,允许用户创建指定大小或者默认大小的栈
    	public MyArrayStack() {
    		// TODO Auto-generated constructor stub
    		this(DEFAULT_CAPACITY);
    	}
    	
    	@SuppressWarnings("unchecked")
    	public MyArrayStack(int capacity) {
    		//注意不能建立泛型数组,因此我们强行转换一个Object数组
    		contents = (E[]) new Object[capacity];
    		this.size = 0;
    	}
    

    然后是进栈和出栈的操作:

    	@Override
    	public E push(E item) {
    		// TODO Auto-generated method stub
    		//在插入元素之前,检查数组是否有足够的空间放置新的元素,若没有,则对数组进行扩容
    		ensureCapacity();
    		contents[size++] = item;
    		return item;
    	}
    	
    
    	@SuppressWarnings("unchecked")
    	private void ensureCapacity() {
    		// TODO Auto-generated method stub
    		if(size>=contents.length) {
    			//此处新数组的容量是旧数组的2倍加1,你可以自己选择扩容的多少
    			E[] newContents = (E[]) new Object[2*size+1];
    			//将就数组中的值全部拷于新数组中
    			System.arraycopy(contents, 0, newContents, 0, size);
    			//再让contents指向新的数组
    			contents = newContents;
    		}
    	}
    
    	@Override
    	public E pop() {
    		// TODO Auto-generated method stub
    		if(empty())
    			throw new EmptyStackException();
    		E data = contents[size-1];
    		contents[--size] = null;
    		return data;
    	}
    

    接下来是,返回栈中顶部元素以及返回栈中某个元素的位置的实现:

    	@Override
    	public E peek() {
    		// TODO Auto-generated method stub
    		if(empty())
    			throw new EmptyStackException();
    		return contents[size-1];
    	}
    	@Override
    	public int search(Object o) {
    		// TODO Auto-generated method stub
    		if(empty()) {
    			return -1;
    		}else {
    			int distance;
    			if(o == null) {
    				for(int i=size-1; i>=0; i--) {
    					if(contents[i] == null) {
    						distance = this.size-i;
    						return distance;
    					}
    				}
    				return -1;
    			}else {
    				for(int i=size-1; i>=0; i--) {
    					if(o.equals(contents[i])) {
    						distance = this.size-i;
    						return distance;
    					}
    				}
    				return -1;
    			}
    			
    		}
    		
    	}
    

    最后,是检查栈是否为空以及清空整个栈的操作:

    	@Override
    	public boolean empty() {
    		// TODO Auto-generated method stub
    		return this.size==0;
    	}
    	@Override
    	public void clear() {
    		// TODO Auto-generated method stub
    		for(int i=this.size-1;i>=0;i--) {
    			contents[size--] = null;
    		}
    	}
    

    我们可以看到,进栈,出栈以及获取栈顶元素的操作时间复杂度都是O(1),再加上后进先出的特性,使得栈这种数据结构在多个方面都有重要的作用。我们会在之后的博客中介绍一些使用栈的场景。