本章内容

栈定义

栈是一种运算受限的线性表，只允许在一端插入和删除数据。它遵循后进先出的原则。

栈主要包含两个操作：入栈和出栈，即：从栈顶插入一个数据或从栈顶删除一个数据。

栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈称为顺序栈，用链表实现的栈称为链式栈。

栈实现

基于数组实现栈

基于数组的顺序栈，代码实现：

/** * @author 南秋同学 * 基于数组实现栈 */public class StackByArray {    /**     * 数组     */    private final String[] items;    /**     * 栈中元素个数     */    private int count;    /**     * 栈容量     */    private final int length;    public StackByArray(int capacity) {        this.items = new String[capacity];        this.length = capacity;        this.count = 0;    }    /**     * 入栈     * @param item 元素     * @return 入栈是否成功     */    public boolean push(String item) {        // 数组空间已满，返回false，表示入栈失败        if (count == length) {            System.out.println("栈中元素已满！");            return false;        }        // 入栈成功，将数据添加到元素中，注意此处的下标为count，因为count表示栈中已经存在的元素个数        items[count] = item;        // 入栈成功，栈中元素个数加一        count++;        return true;    }    /**     * 出栈     * @return 栈顶元素     */    public String pop() {        // 栈为空，返回null        if (count == 0) {            return null;        }        // 返回下标为count-1的数组元素（即：栈顶元素）        String tmp = items[count-1];        items[count-1] = null;        // 出栈成功，栈中元素个数减一        count--;        return tmp;    }    public static void main(String[] args) {        StackByArray stackByArray = new StackByArray(5);        System.out.println("初始化栈中数组：" + Arrays.toString(stackByArray.items));        stackByArray.push("a");        stackByArray.push("b");        stackByArray.push("c");        stackByArray.push("d");        stackByArray.push("e");        stackByArray.push("f");        System.out.println("栈中元素：" + Arrays.toString(stackByArray.items));        System.out.println("栈顶元素["+stackByArray.pop()+"]出栈");        System.out.println("栈顶元素出栈后，栈中元素：" + Arrays.toString(stackByArray.items));        stackByArray.push("g");        System.out.println("栈顶元素入栈后，栈中元素：" + Arrays.toString(stackByArray.items));    }}

基于链表实现栈

基于链表的链式栈，代码实现：

/** * @author 南秋同学 * 基于链表实现栈 */public class StackByList<E> {    /**     * 定义链表节点     * @param <E>     */    @Data    @AllArgsConstructor    @NoArgsConstructor    static class Node<E>{        private E value;        private Node<E> next;    }    /**     * 链表头节点     */    private final Node<E> head;    /**     * 栈顶元素节点（即：链表中的第一个元素）     */    private Node<E> top;    /**     * 栈中元素个数     */    private int count;    /**     * 栈容量     */    private final int length;    public StackByList(int n){        // 设置链表头节点，注意：链表中头节点一般不存储数据，用于指向链表中的第一个节点        this.head = new Node<>();        this.head.setNext(null);        this.length = n;        this.count = 0;    }    /**     * 入栈     * @param element 元素     * @return 入栈是否成功     */    public boolean push(E element){        if(count == length){            System.out.println("栈中元素已满！");            return false;        }        // 将入栈元素封装成节点        Node<E> newNode = new Node<>();        newNode.setValue(element);        newNode.setNext(this.head.next);        // 将当前节点设置为链表的第一个节点（即：头节点的后继节点）        this.head.setNext(newNode);        // 将新加入的节点设置为栈顶节点        this.top = newNode;        // 将栈中的元素个数+1        count++;        return true;    }    /**     * 出栈     * @return 栈顶元素     */    public E pop(){        if(count == 0){            return null;        }        // 取出栈顶节点        Node<E> node = top;        // 设置head节点为被取出的栈顶节点的后继节点        this.head.setNext(node.next);        // 设置top节点为被取出的栈顶节点的后继节点        top = node.next;        // 设置被取出的栈顶节点的后继节点为null        node.setNext(null);        // 将栈中的元素个数-1        count--;        return node.getValue();    }    public static void main(String[] args) {        StackByList<String> stringStackByList = new StackByList<>(5);        stringStackByList.push("a");        stringStackByList.push("b");        stringStackByList.push("c");        stringStackByList.push("d");        stringStackByList.push("e");        stringStackByList.push("f");        StackByList.Node printNode = stringStackByList.top;        while (printNode != null){            System.out.println("栈中元素：" + printNode.getValue());            printNode = printNode.next;        }        System.out.println("栈顶元素["+stringStackByList.pop()+"]出栈");        printNode = stringStackByList.top;        while (printNode != null){            System.out.println("栈顶元素出栈后，栈中元素：" + printNode.getValue());            printNode = printNode.next;        }        System.out.println("------------------------------");        stringStackByList.push("g");        printNode = stringStackByList.top;        while (printNode != null){            System.out.println("栈顶元素入栈后，栈中元素：" + printNode.getValue());            printNode = printNode.next;        }    }}

复杂度

顺序栈和链式栈入栈、出栈都只涉及栈顶元素的操作，时间复杂度均为O(1)。

顺序栈和链式栈使用一个大小为n的数组存储数据，空间复杂度均为O(1)。

注意：空间复杂度一般是指除了本身的数据存储空间之外，算法运行时需要的额外存储空间。

栈应用场景

栈在函数调用中的应用

线程运行时，操作系统会为线程分配了一块独立的内存空间（栈结构），用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧压入栈中；函数执行完成并返回后，就会将该函数对应的栈帧从栈中移除（即：出栈）。

代码示例：

public static void main(String[] args) {    int z = 1;    int request = 0;    int response = 0;    request = add(2,3);    response = z * request;    System.out.println(response);}private static int add(int x, int y){    int sum = 0;    sum = x + y;    return sum;}

函数调用栈，如图所示：

栈在表达式求值中的应用

以1+2*3-4/2为例，编译器通过两个栈来实现的对该表达式的运算。其中一个栈用来保存操作数，另一个栈用来保存运算符，从左向右遍历表达式，当遇到数字时，就将数字压入操作数栈栈中；当遇到运算符时，就与运算符栈的栈顶元素进行比较：

• 如果运算符的优先级高于栈顶运算符，则将运算符压入栈中；
• 如果运算符的优先级低于或等于栈顶运算符，则从运算符栈中取栈顶运算符，并从操作数栈的栈顶取2个操作数，然后进行计算，计算完成后将计算结果压入操作数栈中，继续向右遍历表达式。

如图所示：

栈在括号匹配中的应用

假设表达式中包含三种括号：圆括号 ()、方括号[]和花括号{}，并且它们可以任意嵌套。比如：{[]()[{}]}或[{()}([])]等为合法格式，而{[}()]或[({)]等为不合法格式。

可以使用栈来保存未匹配的左括号，从左向右扫描字符串。当扫描到左括号时，则将其压入栈中；当扫描到右括号时，则从栈顶取出一个左括号：

• 如果能够匹配（如：(与)匹配、[与]匹配、{与}匹配），则为合法格式并继续向右遍历字符串；
• 如果不能匹配或者栈中没有数据，则为非法格式。

当扫描完所有括号后，如果栈为空，则说明字符串为合法格式；否则说明有未匹配的左括号，为非法格式。

【阅读推荐】

想了解常用数据结构与算法（如：数组、链表、快速排序、堆与堆排序、二分查找、动态规划、广度优先搜索算法（BFS）、深度优先搜索算法（DFS）等）的同学请移步->数据结构与算法系列合集（持续更新中）。

更多精彩内容请移步【南秋同学】个人主页进行查阅。

【作者简介】

一枚热爱技术和生活的老贝比，专注于Java领域，关注【南秋同学】带你一起学习成长～