数据结构与算法 | 栈的实现及应用

前面，我们实现了两种常见的线性表 —— 顺序表 和 链表 ，本篇我们来介绍另外一种常用的线性表 —— 栈。

声明：本篇为极客时间《 数据结构与算法之美 》专栏《 栈 》这一部分的学习笔记，部分内容摘抄自专栏文章。

栈

定义

线性表中的一种特殊数据结构，数据只能从固定的一端插入数据或删除数据，另一端是封死的。

特点

• FILO（First In Last Out）: 先进后出；

• 栈满还存会“上溢”，栈空再取会“下溢”；

  “上溢”：在栈已经存满数据元素的情况下，如果继续向栈内存入数据，栈存储就会出错。

  “下溢”：在栈内为空的状态下，如果对栈继续进行取数据的操作，就会出错。

分类

顺序栈

特点

• 采用数组实现，数据在物理结构上保持连续性。

代码实现

package one.wangwei.algorithms.datastructures.stack.impl;

import one.wangwei.algorithms.datastructures.stack.IStack;

import java.util.Arrays;

/**
 * 顺序栈
 *
 * @param <T>
 * @author wangwei
 * @date 2018/05/04
 */
public class ArrayStack<T> implements IStack<T> {

    /**
     * 默认大小
     */
    private static final int DEFAULT_SIZE = 10;
    /**
     * 数组
     */
    private T[] array = (T[]) new Object[DEFAULT_SIZE];
    /**
     * 大小
     */
    private int size;

    /**
     * 入栈
     *
     * @param value
     * @return
     */
    @Override
    public boolean push(T value) {
        if (size >= array.length) {
            grow();
        }
        array[size] = value;
        size++;
        return false;
    }

    /**
     * 扩容50%
     */
    private void grow() {
        int growSize = size + (size << 1);
        array = Arrays.copyOf(array, growSize);
    }

    /**
     * 压缩50%
     */
    private void shrink() {
        int shrinkSize = size >> 1;
        array = Arrays.copyOf(array, shrinkSize);
    }

    /**
     * 出栈
     *
     * @return
     */
    @Override
    public T pop() {
        if (size <= 0) {
            return null;
        }
        T element = array[--size];
        array[size] = null;

        int shrinkSize = array.length >> 1;
        if (shrinkSize >= DEFAULT_SIZE && shrinkSize > size) {
            shrink();
        }
        return element;
    }

    /**
     * 查看栈顶值
     *
     * @return
     */
    @Override
    public T peek() {
        if (size <= 0) {
            return null;
        }
        return array[size - 1];
    }

    /**
     * 删除元素
     *
     * @param value
     * @return
     */
    @Override
    public boolean remove(T value) {
        if (size <= 0) {
            return false;
        }
        for (int i = 0; i < size; i++) {
            T t = array[i];
            if (value == null && t == null) {
                return remove(i);
            }
            if (value != null && value.equals(t)) {
                return remove(i);
            }
        }
        return false;
    }

    /**
     * 移除 index 处的栈值
     *
     * @param index
     * @return
     */
    private boolean remove(int index) {
        if (index < 0 || index >= size) {
            throw new ArrayIndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        }
        if (index != --size) {
            System.arraycopy(array, index + 1, array, index, size - index);
        }
        array[size] = null;

        int shrinkSize = array.length >> 1;
        if (shrinkSize >= DEFAULT_SIZE && shrinkSize > size) {
            shrink();
        }
        return true;
    }

    /**
     * 清空栈
     */
    @Override
    public void clear() {
        if (size <= 0) {
            return;
        }
        for (int i = 0; i < size; i++) {
            array[i] = null;
        }
        size = 0;
        array = null;
    }

    /**
     * 是否包含元素
     *
     * @param value
     * @return
     */
    @Override
    public boolean contains(T value) {
        if (size <= 0) {
            return false;
        }
        for (int i = 0; i < size; i++) {
            T t = array[i];
            if (value == null && t == null) {
                return true;
            }
            if (value != null && value.equals(t)) {
                return true;
            }
        }
        return false;
    }

    /**
     * 栈大小
     *
     * @return
     */
    @Override
    public int size() {
        return size;
    }
    
}

源码

复杂度

空间复杂度

出栈和入栈的操作，只涉及一两个临时变量的存储空间，所以复杂度为O(1).

时间复杂度

顺序栈在出栈和入栈的操作时，最好情况时间复杂度为O(1)，当需要扩容或者缩减时，需要迁移数据，此时最坏情况时间复杂度为O(n). 根据摊还分析法则，它们的均摊时间复杂度还是为O(1).

链表栈

特点

• 用线性表的链式结构存储，数据在物理结构上非连续

代码实现

package one.wangwei.algorithms.datastructures.stack.impl;

import one.wangwei.algorithms.datastructures.stack.IStack;

/**
 * 链表栈
 *
 * @param <T>
 * @author wangwei
 * @date 2018/05/04
 */
public class LinkedStack<T> implements IStack<T> {

    private Node<T> top;
    private int size;

    public LinkedStack() {
        this.top = null;
        this.size = 0;
    }

    /**
     * 入栈
     *
     * @param value
     * @return
     */
    @Override
    public boolean push(T value) {
        Node<T> newTop = new Node<>(value);
        if (top == null) {
            top = newTop;
        } else {
            Node<T> oldTop = top;
            top = newTop;
            oldTop.above = top;
            top.below = oldTop;
        }
        size++;
        return true;
    }

    /**
     * 出栈
     *
     * @return
     */
    @Override
    public T pop() {
        if (top == null) {
            return null;
        }

        Node<T> needTop = top;
        top = needTop.below;
        if (top != null) {
            top.above = null;
        }

        T needValue = needTop.element;
        needTop = null;

        size--;
        return needValue;
    }

    /**
     * 查看栈顶值
     *
     * @return
     */
    @Override
    public T peek() {
        return top == null ? null : top.element;
    }

    /**
     * 删除元素
     *
     * @param value
     * @return
     */
    @Override
    public boolean remove(T value) {
        if (top == null) {
            return false;
        }
        Node<T> x = top;
        if (value == null) {
            while (x != null && x.element != null) {
                x = x.below;
            }
        } else {
            while (x != null && !value.equals(x.element)) {
                x = x.below;
            }
        }
        return remove(x);
    }

    /**
     * 删除一个节点
     *
     * @param node
     * @return
     */
    private boolean remove(Node<T> node) {
        if (node == null) {
            return false;
        }
        Node<T> above = node.above;
        Node<T> below = node.below;

        // 删除中间元素
        if (above != null && below != null) {
            above.below = below;
            below.above = above;
        }
        // 删除top元素
        else if (above == null && below != null) {
            top = below;
            top.above = null;
        } else if (above != null && below == null) {
            above.below = null;
            below = null;
        } else {
            top = null;
        }
        node = null;
        size--;
        return true;
    }

    /**
     * 清空栈
     */
    @Override
    public void clear() {
        if (top == null) {
            return;
        }
        for (Node<T> x = top; x != null; ) {
            Node<T> below = x.below;
            x.element = null;
            x.above = null;
            x.below = null;
            x = below;
        }
        top = null;
        size = 0;
    }

    /**
     * 是否包含元素
     *
     * @param value
     * @return
     */
    @Override
    public boolean contains(T value) {
        if (value == null) {
            for (Node<T> x = top; x != null; x = x.below) {
                if (x.element == null) {
                    return true;
                }
            }
        } else {
            for (Node<T> x = top; x != null; x = x.below) {
                if (x.element.equals(value)) {
                    return true;
                }
            }
        }
        return false;
    }

    /**
     * 栈大小
     *
     * @return
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * 节点
     *
     * @param <T>
     */
    private static class Node<T> {
        private T element;
        private Node<T> above;
        private Node<T> below;

        public Node(T element) {
            this.element = element;
        }
    }
}

源码

复杂度

空间复杂度

出栈和入栈的操作，只涉及一两个临时变量的存储空间，所以复杂度为O(1).

时间复杂度

出栈和入栈的操作，不涉及数据搬迁，只是顶部元素操作，时间复杂度均为O(1).

栈的应用

接下来，我们看看栈在软件工程中的实际应用。

函数调用

操作系统给每个线程分配了一块独立的内存空间，这块内存被组织成“栈”这种结构, 用来存储函数调用时的临时变量。每进入一个函数，就会将临时变量作为一个栈帧入栈，当被调用函数执行完成，返回之后，将这个函数对应的栈帧出栈。

示例：

int main() {
   int a = 1; 
   int ret = 0;
   int res = 0;
   ret = add(3, 5);
   res = a + ret;
   printf("%d", res);
   reuturn 0;
}

int add(int x, int y) {
   int sum = 0;
   sum = x + y;
   return sum;
}

main() 函数调用了 add() 函数，获取计算结果，并且与临时变量 a 相加，最后打印 res 的值。这个过程的中函数栈里的出栈、入栈操作，如下所示：

思考：为什么函数要用栈来保存临时变量呢？用其他数据结构不行吗？

函数调用的局部状态之所以用栈来记录是因为这些状态数据的存活时间满足“后入先出”（LIFO）顺序，而栈的基本操作正好就是支持这种顺序的访问。

栈是程序设计中的一种经典数据结构，每个程序都拥有自己的程序栈。栈帧也叫过程活动记录，是编译器用来实现函数调用过程的一种数据结构。C语言中，每个栈帧对应着一个未运行完的函数。从逻辑上讲，栈帧就是一个函数执行的环境：函数调用框架、函数参数、函数的局部变量、函数执行完后返回到哪里等等。栈是从高地址向低地址延伸的。每个函数的每次调用，都有它自己独立的一个栈帧，这个栈帧中维持着所需要的各种信息。

寄存器ebp(base pointer)指向当前的栈帧的底部（高地址），可称为“帧指针”或“基址指针”；寄存器esp(stack pointer)指向当前的栈帧的顶部（低地址），可称为“ 栈指针”。

在C和C++语言中，临时变量分配在栈中，临时变量拥有函数级的生命周期，即“在当前函数中有效，在函数外无效”。这种现象就是函数调用过程中的参数压栈，堆栈平衡所带来的。堆栈平衡是指函数调完成后，要返还所有使用过的栈空间。

函数调用其实可以看做4个过程：

1. 压栈: 函数参数压栈，返回地址压栈
2. 跳转: 跳转到函数所在代码处执行
3. 执行: 执行函数代码
4. 返回: 平衡堆栈，找出之前的返回地址，跳转回之前的调用点之后，完成函数调用

表达式求值

以 3 + 5 x 8 - 6 为这个表达式为例，编译器是如何利用栈来实现表达式求值的呢？

编译器会使用两个栈来实现，一个栈用来保存操作数，另一个栈用来保存运算符。从左向右遍历表达式，遇到数字直接压入操作数栈，遇到操作符，就与运算符栈顶元素进行比较。

如果比运算符栈顶元素的优先级高，就将当前运算符压入栈；如果比运算符栈顶元素的优先级低或者相同，从运算符栈中取栈顶运算符，从操作数栈的栈顶取 2 个操作数，然后进行计算，再把计算完的结果压入操作数栈，继续比较。

如图所示：

此前，我们在讲 比特币脚本语言 时，提到过 逆波兰表示法 ，也是运用了栈这种数据结构特征。

练习

Leetcode 224. Basic Calculator

题目具体的分析，我放在了单独的文章中，👉 戳此查看 。

括号匹配

栈还可以用来检测表达式中的括号是否匹配。

我们假设表达式中只包含三种括号，圆括号 ()、方括号 [] 和花括号{}，并且它们可以任意嵌套。比如，{[{}]}或 [{()}([])] 等都为合法格式，而{[}()] 或 [({)] 为不合法的格式。那我现在给你一个包含三种括号的表达式字符串，如何检查它是否合法呢？

我们用栈来保存未匹配的左括号，从左到右依次扫描字符串。当扫描到左括号时，则将其压入栈中；当扫描到右括号时，从栈顶取出一个左括号。如果能够匹配，比如“(”跟“)”匹配，“[”跟“]”匹配，“{”跟“}”匹配，则继续扫描剩下的字符串。如果扫描的过程中，遇到不能配对的右括号，或者栈中没有数据，则说明为非法格式。

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

练习

Leetcode 20. Valid Parentheses

我自己在做这道题时，虽说做对了，但是没有像下面的代码那样采用Map存储括号的对应关系，导致代码非常臃肿难堪。

class Solution {

  // Hash table that takes care of the mappings.
  private HashMap<Character, Character> mappings;

  // Initialize hash map with mappings. This simply makes the code easier to read.
  public Solution() {
    this.mappings = new HashMap<Character, Character>();
    this.mappings.put(')', '(');
    this.mappings.put('}', '{');
    this.mappings.put(']', '[');
  }

  public boolean isValid(String s) {

    // Initialize a stack to be used in the algorithm.
    Stack<Character> stack = new Stack<Character>();

    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);

      // If the current character is a closing bracket.
      if (this.mappings.containsKey(c)) {

        // Get the top element of the stack. If the stack is empty, set a dummy value of '#'
        char topElement = stack.empty() ? '#' : stack.pop();

        // If the mapping for this bracket doesn't match the stack's top element, return false.
        if (topElement != this.mappings.get(c)) {
          return false;
        }
      } else {
        // If it was an opening bracket, push to the stack.
        stack.push(c);
      }
    }

    // If the stack still contains elements, then it is an invalid expression.
    return stack.isEmpty();
  }
}

浏览器的前进、后退

使用两个栈，X 和 Y，把首次浏览的页面依次压入栈 X，当点击后退按钮时，再依次从栈 X 中出栈，并将出栈的数据依次放入栈 Y。当我们点击前进按钮时，我们依次从栈 Y 中取出数据，放入栈 X 中。当栈 X 中没有数据时，那就说明没有页面可以继续后退浏览了。当栈 Y 中没有数据，那就说明没有页面可以点击前进按钮浏览了。

比如你顺序查看了 a，b，c 三个页面，我们就依次把 a，b，c 压入栈，这个时候，两个栈的数据就是这个样子：

当你通过浏览器的后退按钮，从页面 c 后退到页面 a 之后，我们就依次把 c 和 b 从栈 X 中弹出，并且依次放入到栈 Y。这个时候，两个栈的数据就是这个样子：

这个时候你又想看页面 b，于是你又点击前进按钮回到 b 页面，我们就把 b 再从栈 Y 中出栈，放入栈 X 中。此时两个栈的数据是这个样子：

这个时候，你通过页面 b 又跳转到新的页面 d 了，页面 c 就无法再通过前进、后退按钮重复查看了，所以需要清空栈 Y。此时两个栈的数据这个样子：

当然，我们还可以使用双向链表来实现这个功能。

区别

我们都知道，JVM 内存管理中有个“堆栈”的概念。栈内存用来存储局部变量和方法调用，堆内存用来存储 Java 中的对象。那 JVM 里面的“栈”跟本篇说的“栈”是不是一回事呢？如果不是，那它为什么又叫作“栈”呢？

本篇介绍的栈是一种抽象的数据结构，而JVM中的”堆栈”是一种实际存在的物理结构，有关JVM堆栈的了解，可以看我之前的文章：https://wangwei.one/posts/java7-jvm-memory-model.html

参考资料

• 《数据结构与算法之美》
• https://time.geekbang.org/column/article/41222
• http://data.biancheng.net/view/9.html
• https://www.jianshu.com/p/594357dff57e
• https://www.cnblogs.com/33debug/p/6773059.html