数据结构---[栈（stack)](代码片段)

栈（stack）

栈也是一种线性数据结构,只能从栈顶一段添加/取出元素;

类似于单口试管;后进先出

Last In First Out(LIFO)

栈（stack）又名堆栈，它是一种运算受限的线性表.限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

---

• 栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。

• 栈是允许在同一端进行插入和删除操作的特殊线性表。允许进行插入和删除操作的一端称为栈顶(top)，另一端为栈底(bottom)；栈底固定，而栈顶浮动；栈中元素个数为零时称为空栈。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称为先进后出表。

• 栈可以用来在函数调用的时候存储断点，做递归时要用到栈！

案例:
例如有三个方法: A, B, C;在A执行中,调用B方法,在B执行时,调用C方法.

对于栈来说, 先把main方法入栈; main方法中调用了A; 把A入栈, 此时A调用到B; 把B入栈; B调用到C了;
把C入栈, 执行完C; C弹出栈;再继续执行B; B弹出栈;再继续执行A; A弹出栈; 最后再将main方法弹出栈.

public class Demo 
    public static void main(String[] args) 
        A();
    
    public static void A()
        System.out.println("A执行一步.");
        B();
        System.out.println("A执行2步.");
    
    public static  void B()
        System.out.println("B执行一步");
        C();
        System.out.println("B执行2步.");
    
    public static void C()
        System.out.println("C执行一步.");
    

//执行过程
/*
A执行一步.
B执行一步
C执行一步.
B执行2步.
A执行2步.
* */

栈的具体实现

类似于数组,但是由于仅有栈顶控制进出的特殊性,所以具体实现方法比较简单

Class Stack

构造方法 Stack( ) 创建一个空堆栈。

方法:

自定义栈的基本操作实现

首先自定义栈的基本操作接口;

/**
 * 自定义栈的基本操作接口;
 * @param <E> 泛型;数据类型;
 * @author 小智
 * @create 2021-07-22 17:08
 */
public interface MyStack<E> 
    /**
     * 获取栈中的实际元素个数;
     */
    int getSize();

    /**
     * 判断栈是否为空栈;
     */
    boolean isEmpty();

    /**
     * 入栈;
     * @param element 需要添加的元素;
     */
    void push(E element);

    /**
     * 出栈;
     */
    E pop();

    /**
     * 查看栈顶元素;
     */
    E peek();

自定义栈的基本操作实现类:

/**
 * 自定义栈的基本操作实现类;
 * @author 小智
 * @create 2021-07-22 17:19
 */
public class MyStackImpl<E> implements MyStack<E> 

    /**
     * 数据容器(使用自定义数组中的data);
     */
    private MyselfArray<E> data;

    /**
     * 栈的实际元素个数;
     */
    private int size;

    /**
     * 无参构造;
     */
    public MyStackImpl() 
        data = new MyselfArray<>();
        size = 0;
    
    
    /**
     * 有参构造;
     * @param capacity 栈的容量;
     */
    public MyStackImpl(int capacity)
        data=new MyselfArray<>(capacity);
    

    /**
     * 获取栈中的实际元素个数;
     * @return int类型; 实际元素个数
     */
    @Override
    public int getSize() 
        return this.size;
    

    /**
     * 判断栈是否为空栈;
     * @return boolean类型; (true:空栈| false:不是空栈)
     */
    @Override
    public boolean isEmpty() 
        return this.size == 0;
    

    /**
     * 入栈;
     * @param element 需要添加的元素;
     */
    @Override
    public void push(E element) 
        try 
            //调用自定义数组的数组尾部添加元素方法;
            data.addTail(element);
            //元素数量加 1 ;
            size++;
         catch (IllegalAccessException e) 
            e.printStackTrace();
        
    

    /**
     * 出栈;
     * @return E类型; 栈顶元素;
     */
    @Override
    public E pop() 
        E result = null;
        try 
            //调用自定义数组的数组删除尾部元素方法;
            result = data.removeTail();
            //元素数量减 1 ;
            size--;
         catch (IllegalAccessException e) 
            e.printStackTrace();
        
        return result;
    

    /**
     * 查看栈顶元素;
     * @return E类型; 栈顶元素;
     */
    @Override
    public E peek() 
        try 
            //调用自定义数组的数组查找尾部元素方法;
            return data.getTail();
         catch (IllegalAccessException e) 
            e.printStackTrace();
            return null;
        
    
    /**
     * 输出栈;
     */
    @Override
    public String toString() 
        StringBuilder sbl = new StringBuilder();
        //追加输出格式;
        sbl.append("栈的容量大小为:"+data.getCapacity()+" 栈中的实际元素个数:"+size).append("  栈底 <");
        try 
            //循环遍历栈中的元素;注意栈中的元素存在自定义的数组中;
            for (int i = 0; i < this.size; i++) 
                sbl.append(data.getEleByIndex(i));
                //追加分隔符;
                if (i != size - 1) 
                    sbl.append(",");
                
            
            sbl.append("> 栈顶");
            //调用返回StringBuilder的toString方法;
            return sbl.toString();
         catch (IllegalAccessException e) 
            e.printStackTrace();
            return null;
        
    
    
    /**
     * 输出栈方式 2; 输出时将栈中的元素全部弹出;
     */
    public String toString2() 
        StringBuilder sbl = new StringBuilder();
        //追加输出格式;
        sbl.append("栈的容量大小为:" + data.getCapacity() + " 栈中的实际元素个数:" + size).append("  栈顶位置<<<");
        //只要栈不为空;就出栈,存入字符串sbl;
        while (!this.isEmpty()) 
            sbl.append(this.pop() + "<<<");
        
        return sbl.substring(0, sbl.lastIndexOf("<") - 2).toString();
    

• 自定义栈的时间复杂度

push(E element)入栈 ; pop 出栈 ; peek 查看栈顶元素 ; getSize 查看栈的实际元素个数 ;isEmpty 判断栈是否为空栈
时间复杂度均为O(1)

栈是线性表的特例;那么栈的顺序存储也是线性表顺序存储的简化,(顺序栈);而线性表是用数组实现,下标为0的一端作为栈底;首元素存到栈底,变化量小.

定义一个变量top:(栈顶元素在数组中的位置),定义StackSize作为栈的长度;top要小于StackSize;
当栈仅存在一个元素时,top为0,则空栈为top= -1