概念

栈（stack）是一种线性数据结构，栈中的元素只能先入后出（First In Last Out，简称FILO）。
最早进入的元素存放的位置叫作栈底（bottom），最后进入的元素存放的位置叫作栈顶 （top）。

存储原理

栈既可以用数组来实现，也可以用链表来实现

数组实现

栈的数组实现如下：

数组实现的栈也叫顺序栈或静态栈

链表实现

栈的链表实现如下：

链表实现的栈也叫做链式栈或动态栈

操作

入栈（压栈）

入栈操作（push）就是把新元素放入栈中，只允许从栈顶一侧放入元素，新元素的位置将会成为新的栈顶

出栈（弹栈）

出栈操作（pop）就是把元素从栈中弹出，只有栈顶元素才允许出栈，出栈元素的前一个元素将会成为新的栈顶。

应用

• 函数调用
  每进入一个函数，就会将临时变量作为一个栈入栈，当被调用函数执行完成，返回之后，将这个函
  数对应的栈帧出栈

案例

利用栈实现字符串逆序

public static void reversalStr() {
        ArrayStack stack = new ArrayStack(10);
        String str = "how are you";
        char[] cha = str.toCharArray();
        for (char c : cha) {
            stack.push(c);
        }
        while (!stack.isEmpty()) {
            System.out.print(stack.pop());
        }
    }

利用栈判断分隔符是否匹配

写过xml标签或者html标签的，我们都知道<必须和最近的>进行匹配，[ 也必须和最近的 ] 进行匹配。

public static void matchHtml() {
        ArrayStack stack = new ArrayStack(5);
        String str = "12<a[b{}c}]>";
        char[] cha = str.toCharArray();
        for (char c : cha) {
            switch (c) {
                case '{':
                case '[':
                case '<':
                    stack.push(c);
                    break;
                case '}':
                case ']':
                case '>':
                    if (!stack.isEmpty()) {
                        char ch = stack.pop().toString().toCharArray()[0];
                        if (c == '}' && ch != '{'
                                || c == ']' && ch != '['
                                || c == ')' && ch != '(') {
                            System.out.println("Error: 开分隔符=" + ch + " 闭分隔符=" + c);
                        }
                    }
                    break;
                default:
                    break;
            }
        }
    }

总结

根据栈后进先出的特性，我们实现了单词逆序以及分隔符匹配。所以其实栈是一个概念上的工具，具体能实现什么功能可以由我们去想象。栈通过提供限制性的访问方法push()和pop()，使得程序不容易出错。

对于栈的实现，我们稍微分析就知道，数据入栈和出栈的时间复杂度都为O(1)，也就是说栈操作所耗的时间不依赖栈中数据项的个数，因此操作时间很短。而且需要注意的是栈不需要比较和移动操作，我们不要画蛇添足。