[数据结构与算法]栈(数据结构)

栈（Stack)：

1.栈是一个先入后出的有序队列

2.栈是限制线性表中元素的插入和删除只能在线性的同一端的一种特殊线性表，允许插入和删除的一端为变化的一端，为栈顶，另一端为固定的一端为栈底

3.最先放入栈中的元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。

实现栈的思路分析

1.使用数组来模拟栈

2.定义一个top来表示栈顶，初始化为-1

3.入栈的操作，当有数据加入到栈时，top++；stack[top]=data;

4.出栈的操作，intvalue=stack[top];top–;return intvalue;

public class ArrayStackDemo {
    public static void main(String[] args) {
       ArrayStack stack = new ArrayStack(4);
       String key = "";
       boolean loop = true;
       Scanner sc=new Scanner(System.in);
       while (loop){
           System.out.println("show表示显示栈");
           System.out.println("exit退出程序");
           System.out.println("push入栈");
           System.out.println("pop出栈");
           System.out.println("请输入你的选择");
           key=sc.next();
           switch (key){
               case "show":
                   stack.list();
                   break;
               case "push":
                   System.out.println("请输入一个数");
                   int value =sc.nextInt();
                   stack.push(value);
                   break;
               case "pop":
                   try{
                       int res= stack.pop();
                       System.out.printf("出栈的数据是%d\n",res);
                   }catch (Exception e){
                       e.printStackTrace();
                   }
                   break;
               case "exit":
                   sc.close();
                   loop=false;
                   break;
               default:
                   break;
           }
           System.out.println("程序退出");
       }
    }
}
class ArrayStack{
    private int maxSize;//栈的大小
    private int[] stack;//数组，数组模拟栈
    private int top=-1;//表示栈顶初始化为-1
    public ArrayStack(int maxSize){
        this.maxSize=maxSize;
        this.stack=new int[this.maxSize];
    }

    public boolean isfull(){
        return top==maxSize-1;
    }
    public boolean isEmpty(){
        return top==-1;
    }
    public void push(int value){
        if(isfull()){
            System.out.println("栈已满");
            return;
        }
        top++;
        stack[top]=value;
    }
    public int pop(){
        if(isEmpty()){
            throw  new RuntimeException("栈已空");
        }
        int value=stack[top];
        top--;
        return value;
    }
    public void list(){
        if(isEmpty()){
            throw new RuntimeException("栈已空");
        }
        for(int i=top;i>=0;i--){
            System.out.printf("stack[%d]=%d\n",stack[i],i);
        }
    }

}