栈的抽象数据类型

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

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

1 /* 2 * 栈接口抽象数据类型 3 */ 4 public interface Stack
     
       { 5  6    /** 7     * 栈是否为空 8     * @return 9     */10    boolean isEmpty();11 12    /**13     * data元素入栈14     * @param data15     */16    void push(T data);17 18    /**19     * 返回栈顶元素,未出栈20     * @return21     */22    T peek();23 24    /**25     * 出栈,返回栈顶元素,同时从栈中移除该元素26     * @return27     */28    T pop();29 }

顺序栈的设计与实现

顺序栈，顾名思义就是采用顺序表实现的的栈，顺序栈的内部以顺序表为基础，实现对元素的存取操作，当然我们还可以采用内部数组实现顺序栈，在这里我们使用内部数据组来实现栈，至于以顺序表作为基础的栈实现，将以源码提供。这里先声明一个顺序栈其代码如下，实现Stack和Serializable接口：

1 /*  2 * 顺序栈的实现 3  */ 4 public class SeqStack
     
       implements Stack
      
       ,Serializable { 5  6     private static final long serialVersionUID = -5413303117698554397L; 7  8     /** 9      * 栈顶指针,-1代表空栈10      */11     private int top=-1;12 13     /**14      * 容量大小默认为1015      */16     private int capacity=10;17 18     /**19      * 存放元素的数组20      */21     private T[] array;22 23     private int size;24 25     public SeqStack(int capacity){26         array = (T[]) new Object[capacity];27     }28 29     public SeqStack(){30         array= (T[]) new Object[this.capacity];31     }32     //.......省略其他代码33 }

其获取栈顶元素值的peek操作过程如下图（未删除只获取值）：

以上是获取栈顶元素的操作，代码如下：

1 /** 2   * 获取栈顶元素的值,不删除 3   * @return 4   */ 5  @Override 6  public T peek() { 7      if(isEmpty()) 8          new EmptyStackException(); 9      return array[top];10  }

从栈添加元素的过程如下（更新栈顶top指向）：

以上是入栈操作，代码如下：

1 /** 2  * 添加元素,从栈顶(数组尾部)插入 3  * 容量不足时，需要扩容 4  * @param data 5  */ 6 @Override 7 public void push(T data) { 8     //判断容量是否充足 9     if(array.length==size)10         ensureCapacity(size*2+1);//扩容11 12     //从栈顶添加元素13     array[++top]=data;14     }

栈弹出栈顶元素的过程如下（删除并获取值）：

以上是出栈操作，代码如下：

1 /** 2   * 从栈顶(顺序表尾部)删除 3   * @return 4   */ 5  @Override 6  public T pop() { 7      if(isEmpty()) 8          new EmptyStackException(); 9      size--;10      return array[top--];11  }

到此，顺序栈的主要操作已实现完，是不是发现很简单，确实如此，栈的主要操作就这样，当然我们也可以通过前一篇介绍的MyArrayList作为基础来实现顺序栈，这个也比较简单，后面也会提供带代码，这里就不过多啰嗦了。下面给出顺序栈的整体实现代码：

1 import java.io.Serializable;  2 import java.util.EmptyStackException;  3   4 /*  5  * 顺序栈的实现  6  */  7 public class SeqStack
     
       implements Stack
      
       ,Serializable {  8   9     private static final long serialVersionUID = -5413303117698554397L; 10  11     /** 12      * 栈顶指针,-1代表空栈 13      */ 14     private int top=-1; 15  16     /** 17      * 容量大小默认为10 18      */ 19     private int capacity=10; 20  21     /** 22      * 存放元素的数组 23      */ 24     private T[] array; 25  26     private int size; 27  28     public SeqStack(int capacity){ 29         array = (T[]) new Object[capacity]; 30     } 31  32     public SeqStack(){ 33         array= (T[]) new Object[this.capacity]; 34     } 35  36     public  int size(){ 37         return size; 38     } 39  40  41     @Override 42     public boolean isEmpty() { 43         return this.top==-1; 44     } 45  46     /** 47      * 添加元素,从栈顶(数组尾部)插入 48      * @param data 49      */ 50     @Override 51     public void push(T data) { 52         //判断容量是否充足 53         if(array.length==size) 54             ensureCapacity(size*2+1);//扩容 55  56         //从栈顶添加元素 57         array[++top]=data; 58  59         size++; 60     } 61  62     /** 63      * 获取栈顶元素的值,不删除 64      * @return 65      */ 66     @Override 67     public T peek() { 68         if(isEmpty()) 69             new EmptyStackException(); 70         return array[top]; 71     } 72  73     /** 74      * 从栈顶(顺序表尾部)删除 75      * @return 76      */ 77     @Override 78     public T pop() { 79         if(isEmpty()) 80             new EmptyStackException(); 81         size--; 82         return array[top--]; 83     } 84  85     /** 86      * 扩容的方法 87      * @param capacity 88      */ 89     public void ensureCapacity(int capacity) { 90         //如果需要拓展的容量比现在数组的容量还小,则无需扩容 91         if (capacity
       
         s=new SeqStack<>();103         s.push("A");104         s.push("B");105         s.push("C");106         System.out.println("size->"+s.size());107         int l=s.size();//size 在减少,必须先记录108         for (int i=0;i
        
         "+s.pop());110         }111 112         System.out.println("s.peek->"+s.peek());113     }114 }

链式栈的设计与实现

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

从图可以看出，无论是插入还是删除直接操作的是链表头部也就是栈顶元素，因此我们只需要使用不带头结点的单链表即可。代码实现如下，比较简单，不过多分析了：

1 import com.zejian.structures.LinkedList.singleLinked.Node; 2  3 import java.io.Serializable; 4  5 /* 6  * 栈的链式实现 7  */ 8 public class LinkedStack
     
       implements Stack
      
        ,Serializable{ 9 10     private static final long serialVersionUID = 1911829302658328353L;11 12     private Node
       
         top;13 14     private int size;15 16     public LinkedStack(){17         this.top=new Node<>();18     }19 20     public int size(){21         return size;22     }23 24 25     @Override26     public boolean isEmpty() {27         return top==null || top.data==null;28     }29 30     @Override31     public void push(T data) {32         if (data==null){33             throw new StackException("data can\'t be null");34         }35         if(this.top==null){
   //调用pop()后top可能为null36             this.top=new Node<>(data);37         }else if(this.top.data==null){38             this.top.data=data;39         }else {40            Node
        
          p=new Node<>(data,this.top);41             top=p;//更新栈顶42         }43         size++;44     }45 46     @Override47     public T peek()  {48         if(isEmpty()){49             throw new EmptyStackException("Stack empty");50         }51 52         return top.data;53     }54 55     @Override56     public T pop() {57         if(isEmpty()){58             throw new EmptyStackException("Stack empty");59         }60 61         T data=top.data;62         top=top.next;63         size--;64         return data;65     }66     //测试67     public static void main(String[] args){68         LinkedStack
         
           sl=new LinkedStack<>();69         sl.push("A");70         sl.push("B");71         sl.push("C");72         int length=sl.size();73         for (int i = 0; i < length; i++) {74             System.out.println("sl.pop->"+sl.pop());75         }76     }77 }

转载地址：http://aangx.baihongyu.com/

你可能感兴趣的文章