栈

栈是存放对象的一种特殊容器，在插入与删除对象时，这种结构遵循后进先出（Last-in-first-out，LIFO）的原则--也就是说，对象可以任意插入栈中，但每次取出的都是此前插入的最后一个对象。比如一摞椅子，只能将最顶端的椅子移出，也只能将新椅子放到最顶端--这两种操作分别称作入栈（Push）和退栈（Pop）。

栈是最基本的数据结构之一，在实际应用中几乎无所不在。例如，网络浏览器会将用户最近访问过的地址组织为一个栈：用户每访问一个新页面，其地址就会被存放至栈顶；而用户每次按下“Back”按钮，最后一个被记录下的地址就会被清除掉。再如，当今主流的文本编辑器大都支持编辑操作的历史记录功能：用户的编辑操作会被依次记录在一个栈中；一旦出现误操作，用户只需按下“Undo”按钮，即可撤销最近一次操作并回到此前的编辑状态。

由于栈的重要性，在Java 的java.util 包中已经专门为栈结构内建了一个类--java.util.Stack

栈ADT(AbstractDataType)

作为一种抽象数据类型，栈必须支持以下方法：

操作方法	功能描述
push(x)	将对象x 压至栈顶输入：一个对象输出：无
pop()	若栈非空，则将栈顶对象移除，并将其返回否则，报错输入：无输出：对象
getSize()	返回栈内当前对象的数目输入：无输出：非负整数
isEmpty()	检查栈是否为空输入：无输出：布尔标志
top()	若栈非空，则返回栈顶对象（但并不移除）否则，报错输入：无输出：栈顶对象

基于数组的简单实现

package datastructure.stack;

public class FireStack {
    private int size;
    private Integer[] data;

    public FireStack(){
        data = new Integer[10];
    }

    public int getSize(){
        return size;
    }

    public boolean isEmpty(){
        return this.size == 0;
    }

    public void push(Integer element){
        //考虑扩容
        data[size++] = element;
    }

    public Integer pop(){
        if (isEmpty()){
            throw new IndexOutOfBoundsException("-1");
        }
        int result = data[--size];
        data[size] = null;
        return result;
    }

    public Integer top(){
        if (isEmpty()){
            throw new IndexOutOfBoundsException("-1");
        }
        return data[size-1];
    }


    public static void main(String[] args) {
        FireStack fireStack = new FireStack();
        fireStack.push(0);
        fireStack.push(1);
        fireStack.push(2);
        fireStack.push(3);
        int length = fireStack.size;
        for (int i = 0; i < length; i++) {
            System.out.println(fireStack.pop());
        }
    }
}

测试结果

面试中关于栈的常见问题

使用栈计算后缀表达式
对栈的元素进行排序
判断表达式是否括号平衡
括号匹配算法
Tip借助栈进行数组倒置