数据结构之栈

栈

​ 栈是一种很常见的数据结构，其特点是先进后出（FILO，first in last out），只可以操作栈顶的元素。

​ 在jdk中，已经封装了Stack，可以拿来即用。api中Stack是通过Vector实现的。是一个线程安全的数组框架。

​ 仿照java api来实现一个栈。。

​

class Stack {
    //数组模拟栈
    int[] stack;
    int maxSize;
    int top = -1; //用来指向栈顶元素
    
    public Stack() {}
    
    public Stack(int maxSize) {
        this.maxSize = maxSize;
        stack = new int[maxSize];
    }
    
    /**
    * 栈结构主要有几个方法： 
    * 入栈（压栈）： 即向栈中添加数据
    * 出栈： 删除栈顶元素
    * 查看栈顶元素
    * 判断栈是否空
    * 判断栈是否满
    */
    
    //this stack is empty
    public boolean isEmpty() {
        return top == -1;
    }
    
    //this stack is full
    public boolean isFull() {
        return top == maxSize - 1;
    }
    
    //push data
    public void push(int data) {
        if ( isFull() ) return;
        stack[++top] = data;
    }
    
    //pop and return this data
    public int pop() {
        if(isEmpty()) return;
        return stack[top--];
    }
    
    //peek 
    public int peek() {
        return stack[top];
    }
    
    public void traverse() {
        if (isEmpty()) return;
        for (int i = top; i >= 0; i--) {
            System.out.println(stack[i]);
        }
    }
}

栈的应用比较广泛

​ 在程序函数的调用中，使用到了栈结构，当调用一个函数时，会开辟一块空间，用来存放函数中的变量等，而当函数执行完毕之后，就会销毁这个空间，即出栈。

​ 使用栈来对数学表达式求值等等