【栈】栈的设计与实现

一、栈的抽象数据类型

栈是一种用于存储数据的简单数据结构，有点类似链表或者顺序表（统称线性表），栈与线性表的最大区别是数据的存取的操作，我们可以这样认为栈(Stack)是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行，一般而言，把允许操作的一端称为栈顶(Top)，不可操作的一端称为栈底(Bottom)，同时把插入元素的操作称为入栈(Push),删除元素的操作称为出栈(Pop)。若栈中没有任何元素，则称为空栈，栈的结构如下图：

由图我们可看成栈只能从栈顶存取元素，同时先进入的元素反而是后出，而栈顶永远指向栈内最顶部的元素。到此可以给出栈的正式定义：栈(Stack)是一种有序特殊的线性表，只能在表的一端(称为栈顶，top，总是指向栈顶元素)执行插入和删除操作，最后插入的元素将第一个被删除，因此栈也称为后进先出(Last In First Out,LIFO)或先进后出(First In Last Out FILO)的线性表。栈的基本操作：创建栈，判空，入栈，出栈，获取栈顶元素等，注意栈不支持对指定位置进行删除，插入，其接口Stack声明如下：

public interface IStack<T> {
	//栈是否为空
	boolean isEmpty();
	//data元素入栈
	void push(T data);
	//返回栈顶元素,未出栈
	T peek();
	//出栈,返回栈顶元素,同时从栈中移除该元素
	T pop();
}

二、顺序栈的设计与实现

顺序栈，顾名思义就是采用顺序表实现的的栈，顺序栈的内部以顺序表为基础，实现对元素的存取操作。当然我们还可以采用内部数组实现顺序栈，在这里我们使用内部数组来实现栈。

public class SeqStack<T> implements IStack<T>,Serializable {
	private static final long serialVersionUID = 2835698994283027419L;
	//栈顶指针,-1代表空栈
    private int top=-1;
    //容量大小默认为10
    private int capacity=10;
    //存放元素的数组
    private T[] array;

    private int size;

    public SeqStack(int capacity){
        array = (T[]) new Object[capacity];
    }

    public SeqStack(){
        array= (T[]) new Object[this.capacity];
    }

    @Override
    public boolean isEmpty() {
        return this.top==-1;
    }
    //添加元素,从栈顶(数组尾部)插入，容量不足时，需要扩容
    @Override
    public void push(T data) {
        //判断容量是否充足
        if(array.length==size)
            ensureCapacity(size*2+1);//扩容

        //从栈顶添加元素
        array[++top]=data;
    }
    //获取栈顶元素的值,不删除
    @Override
    public T peek() {
        if(isEmpty())
            new EmptyStackException();
        return array[top];
    }

    @Override
    public T pop() {
        if(isEmpty())
            new EmptyStackException();
        size--;
        return array[top--];
    }
    //扩容的方法
    public void ensureCapacity(int capacity) {
        //如果需要拓展的容量比现在数组的容量还小,则无需扩容
        if (capacity<size)
            return;

        T[] old = array;
        array = (T[]) new Object[capacity];
        //复制元素
        for (int i=0; i<size ; i++)
            array[i]=old[i];
    }
}

三、链式栈的设计与实现

所谓的链式栈（Linked Stack），就是采用链式存储结构的栈，由于我们操作的是栈顶一端，因此这里采用单链表（不带头结点）作为基础，直接实现栈的添加，获取，删除等主要操作即可。其操作过程如下图：

public class LinkedStack<T> implements IStack<T>,Serializable {
	private static final long serialVersionUID = -7003963989918008372L;	
	private Node<T> top;
    private int size;

    public LinkedStack(){
        this.top=new Node<>();
    }
    public int size(){
        return size;
    }

    @Override
    public boolean isEmpty() {
        return top==null || top.data==null;
    }

    @Override
    public void push(T data) {
        if (data==null){
            throw new StackException("data can not be null");
        }
        if(this.top==null){//调用pop()后，如果栈为空，则top等于null
            this.top=new Node<>(data);
        }else if(this.top.data==null){
            this.top.data=data;
        }else {
           Node<T> p=new Node<>(data,this.top);
           top=p;//更新栈顶
        }
        size++;
    }

    @Override
    public T peek() throws EmptyStackException  {
        if(isEmpty()){
            throw new EmptyStackException("Stack empty");
        }
        return top.data;
    }

    @Override
    public T pop() {
        if(isEmpty()){
            throw new EmptyStackException("Stack empty");
        }
        T data=top.data;
        top=top.next;
        size--;
        return data;
    }
}
/**
 * Created by zejian on 2016/10/21.
 * 单向链表节点
 */
class Node<T> {
    public T data;//数据域
    public Node<T> next;//地址域
    
    public Node(){
    	
    }
    public Node(T data){
        this.data=data;
    }
    public Node(T data,Node<T> next){
        this.data=data;
        this.next=next;
    }
}