一、什么是栈

栈是程序的一种数据存储结构，是对数组或链表等其他结构的一个抽象，也就是说使用数据或链表可以实现栈这种数据结构，栈有自己的独特机制，就是同一时刻只允许访问一个数据项，最先插入的数据项最后一个被访问，是一种先进后出的特性，访问和操作数据项以栈顶为入口，进栈、出栈和查看等操作都是操作栈顶的位置，也就是说进出栈后栈顶的位置就变了。利用这种特性，可以让我们更好处理一下复杂的场景：单词逆序、分隔符匹配等等。

二、如何实现栈这种数据结构

实现栈这种先进后出的特性，比较常用的可以利用数组或链表去实现，下面以链表为例说一下如何实现栈。(Java中已经实现了栈这种数据结构Stack类)

实现之前先说一下对于栈数据结构需要具备的基本几个操作

• push()方法：将数据项压入栈中
• pop()方法：将栈顶的数据项弹出
• peek()方法：查看栈顶的数据项，但不做移除操作
• isEmpty()方法：判断是否为空栈
• isFull()方法：判断栈是否已满

public class StackHua {

    private int maxSize;//栈大小

    private int[] stackArray; // 通过数组实现栈

    private int top;//栈顶位置

 

    public StackHua(int maxSize) {

        this.maxSize = maxSize;

        this.stackArray = new int[maxSize];

        top = -1;

    }

    public void push(int item){

        stackArray[++top] = item;

    }

    public int pop(){

        return stackArray[--top];

    }

    public int peek(){

        return stackArray[top];

    }

    public boolean isEmpty(){

        return top == -1;

    }

    public boolean isFull() {

        return top == maxSize-1;

    }

}

三、Java中的栈

java中的栈Stack类,是通过动态数组实现了栈这种数据结构，Stack类继承了一个Vector类，该类是一个同步的ArrayList，跟ArrayList类似，主要原因是Vector类也实现了一个动态数组并且操作方法都是同步的，即在相关操作方法上使用synchronized关键字，保证原子性；但是在动态数组扩容时就显得很脆弱了。

Stack类中就几个方法：所要保存的数据项类型为泛型，根据创建Stack实例的时候可以确定具体类型。默认数组大小为10。

•     push(E  item)：将一个数据项压入栈中

•     pop()：将栈顶的数据项弹出

•     peek()：查询栈顶的数据项
•     empty()：判断栈是否为空
•     search(Object o)：搜索指定数据项在栈中的位置

栈使用实例：单词逆序

public class Main {
    public static void main(String[] args)  {
        String works = "Anything is possible";
        System.out.println("单词正序："+works);
        Stack stack =new Stack();
        for (int i = 0; i < works.length(); i++) {
            char work = works.charAt(i);
            stack.push(work);
        }
        StringBuilder result = new StringBuilder();
        while (!stack.empty()) {
            result.append(stack.pop());
        }
        System.out.println("单词逆序："+result.toString());
    }
}

输出：

单词正序：Anything is possible
单词逆序：elbissop si gnihtynA

四、Java中栈stack的缺点

由于java中的Stack类是继承与Vector类，而Vector类已经被官方推荐不使用了，应为所有操作方法都为同步Synchronized方法，在高并发的场景下，效率很低，而且还是用动态数组实现，在大数据场景下，动态数据扩容效率也是很低，因此不推荐。后面推荐使用链表实现的栈更为高效，即使用队列来实现（使用双端链表实现）

五、栈的效率

栈的出栈和入栈的时间复杂度都为O(1)，也就是说对栈的操作所耗时间不依赖栈的数据项的个数，操作效率极高。栈是我们写程序的一个很好的辅助工具；利用好它可以达到事倍功半的效果。