本文共 4868 字，大约阅读时间需要 16 分钟。

栈

栈（stack）是一种特殊的线性表，其插入和删除操作只允许在线性表的一端进行。

栈的抽象数据类型

package pers.zhang.stack;/** * @author zhang * @date 2020/1/16 - 14:05 * * 栈接口，描述栈的抽象数据类型，泛型参数T表示数据元素的数据类型 */public interface SStack
   
     {
       //判断栈是否为空    boolean isEmpty();        //元素x入栈    void push(T x);        //出栈，返回栈顶元素    T pop();        //取出栈顶元素，未出栈    T get();}
   

栈的实现

栈有两种基本的实现：

• 顺序栈：使用数组实现
• 链栈：使用栈节点实现

顺序栈

package pers.zhang.stack;/** * @author zhang * @date 2020/1/16 - 14:12 * * 顺序栈，实现栈接口 */public class SeqStack
   
     implements SStack
    
      {
       //存储栈数据元素的Object数组    private Object element[];    //栈顶元素下表    private int top;    //构造容量为size的栈    public SeqStack(int size){
           this.element = new Object[Math.abs(size)];        this.top = -1;    }    //默认构造，构造容量为64的空栈    public SeqStack(){
           this(64);    }    //判断栈是否为空，若为空返回true    @Override    public boolean isEmpty() {
           return this.top == -1;    }    //元素x入栈，空对象不操作    @Override    public void push(T x) {
           if(x == null)            return;        if(this.top == element.length - 1){
   //栈满，需要扩容            Object[] temp = this.element;            this.element = new Object[temp.length * 2];//重新申请一个2倍容量的数组            for(int i = 0; i < temp.length; i++)//复制元素                this.element[i] = temp[i];        }        this.top++;//移动栈顶指针        this.element[this.top] = x;//入栈    }    //出栈，返回栈顶元素，若栈空返回null    @Override    public T pop() {
           return this.top == -1 ? null : (T) this.element[this.top--];    }    //取出栈顶元素，未出栈，若栈空返回null    @Override    public T get() {
           return this.top == -1 ? null : (T) this.element[this.top];    }    //返回栈所有元素的描述字符串，形式为“(,)”，算法同顺序表    @Override    public String toString(){
                       String str = "(";        if (this.top != -1)            str += this.element[this.top].toString();        for (int i= this.top - 1; i >= 0; i--)            str += ", "+this.element[i].toString();        return str + ") ";    }}
    
   

链栈

节点类：

public class Node
   
     {
       //数据域，保存数据元素    public T data;    //地址域，引用后继节点    public Node
    
      next;    public Node(){
           this(null,null);    }    public Node(T data, Node
     
       next){
           this.data = data;        this.next = next;    }    public String toString(){
           return this.data.toString();    }    public boolean equals(Object obj){
           return obj == this || obj instanceof Node && this.data.equals(((Node
      
       )obj).data);    }}
      
     
    
   

链栈的实现：

package pers.zhang.stack;import pers.zhang.linearList.LinearList;import pers.zhang.linearList.Node;/** * @author zhang * @date 2020/1/16 - 14:28 * * 链栈，实现栈接口 */public class LinkedStack
   
     implements SStack
    
      {
       //栈顶节点，同单链表节点一致    private Node
     
       top;    //构造空栈    public LinkedStack(){
           this.top = null;    }    //判断栈是否为空，若空返回true    @Override    public boolean isEmpty() {
           return this.top == null;    }    //元素x入栈，空对象不操作    @Override    public void push(T x) {
           if(x == null)            return;        this.top = new Node<>(x, this.top);//头插入，x节点作为新的栈顶    }    //出栈，返回栈顶元素，栈空返回null    @Override    public T pop() {
           if(this.top == null)            return null;        T temp = this.top.data;//保存栈顶节点元素        this.top = this.top.next;//删除栈顶节点        return temp;    }    //取出栈顶元素，未出栈，空栈返回null    @Override    public T get() {
           return this.top == null ? null : this.top.data;    }    //返回栈所有元素的描述字符串，形式为“(,)”。算法同不带头结点的单链表    public String toString(){
           String str = "(";        for (Node
      
        p = this.top; p != null; p = p.next){
               str += p.data.toString();            if (p.next != null)                str += ", ";//不是最后一个结点时后加分隔符        }        return str + ")";//空表返回()    }}
      
     
    
   

测试

package pers.zhang.stack;/** * @author zhang * @date 2020/1/16 - 14:36 */public class Stack_ex {
       public static void main(String args[])    {
   /*	    SeqStack
   
     stack = new SeqStack
    
     (20);	    System.out.print("Push: ");	    char ch='a';	    for(int i=0;i<5;i++)	    {	        String str = (char)(ch+i)+"";	        stack.push(str);	        System.out.print(str+"  ");	    }*/        LinkedStack
     
       stack = new LinkedStack
      
       ();        System.out.print("Push: ");        for (int i=1; i<=5; i++)        {
               Integer intobj = new Integer(i);            stack.push(intobj);            System.out.print(intobj+"  ");        }        System.out.println("\nStack: "+stack.toString());        System.out.print("Pop : ");        while(!stack.isEmpty())                  //全部出栈            System.out.print(stack.pop().toString()+"  ");        System.out.println();    }}
      
     
    
   

输出如下：

Push: a  b  c  d  e  Stack: (e, d, c, b, a) Pop : e  d  c  b  a  Push: 1  2  3  4  5  Stack: (5, 4, 3, 2, 1) Pop : 5  4  3  2  1

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