栈 (Stack) 数据结构的概念与实现

1 栈的概念

栈(Stack)是计算机科学中的一种线性数据结构,它遵循后进先出 (LIFO, Last in first out) 原则。

我们可以将栈看作是一种受限的数据结构,因为它只允许在栈的一端进行插入和删除操作,这一端被称为栈顶,另一端被称为栈底,通常栈底元素不能直接访问或修改。

2 栈的性质与应用场景

栈作为一种数据结构,具有以下性质:

  • 后进先出 (LIFO) 原则:最后进入栈的元素将首先被移出。这意味着最近添加的元素在访问时会比之前添加的元素优先级更高。
  • 受限性:栈只允许在栈顶进行插入和删除操作,即只能对栈顶元素进行访问,其他元素必须通过一系列出栈操作才能访问到。
  • O(1) 时间复杂度:在栈顶进行插入、删除和访问操作的时间复杂度都是常数时间,即 O(1),这使得栈在很多场景下非常高效。

栈的应用场景包括但不限于以下几个方面:

  • 函数调用和递归:栈在计算机的函数调用和递归中扮演了重要角色。每当调用一个函数时,当前函数的状态(包括局部变量和返回地址等)都会被压入栈中。函数执行完毕后,状态会从栈中弹出,返回到调用该函数的上层函数,实现了函数的嵌套调用。
  • 表达式求值:在计算数学表达式时,可以使用栈来跟踪运算符和操作数的顺序,确保正确的运算顺序。
  • 浏览器的前进和后退:在浏览器中,通过使用栈来实现前进和后退功能,记录用户访问的页面历史。当用户点击后退按钮时,浏览器会从栈顶取出上一个页面的状态,使用户回到之前的页面。
  • 括号匹配:在编程中,栈常用于检查表达式中的括号是否正确匹配。通过将左括号入栈,遇到右括号时弹出栈顶元素并检查是否匹配,可以有效判断表达式中的括号是否配对。
  • 撤销操作:在许多编辑器和应用程序中,栈用于实现撤销功能。每次用户执行操作时,相关的状态信息被压入栈中。当用户希望撤销操作时,状态信息从栈中弹出,将应用程序恢复到之前的状态。

3 栈的实现

JDK 中提供了很多对栈数据结构的实现,其中包括了 ArrayDeque 类。尽管 ArrayDeque 的底层是一个双端队列 (Deque),但由于它遵循后进先出(LIFO)原则,因此也可以用作栈。接下来我们将以(JDK 20 中的) ArrayDeque 类为例讲解栈的实现。

3.1 ArrayDeque 数据类型

ArrayDeque 通过一个 Object[] 数组存储队列元素,并通过首尾索引分别指向队列中的第一个元素和最后一个元素:

1
2
3
transient Object[] elements;
transient int head;
transient int tail;

3.2 入栈 (push) 操作

ArrayDeque 的入栈方法 push() 的实现如下:

1
2
3
public void push(E e) {
    addFirst(e);
}

该方法的本质就是向队首添加元素,实现如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
// 像队首添加元素
public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    final Object[] es = elements;
    es[head = dec(head, es.length)] = e;
    // tail == 0, 如果 head 减到 0,触发扩容
    if (head == tail)
        grow(1);
}
// 将头索引前移
static final int dec(int i, int modulus) {
    if (--i < 0) i = modulus - 1;
    return i;
}

由于数组的特殊性,ArrayDeque 在向队首插入数据时,实际上是从数组的后部往前插入的。举例来说,如果数组的长度为 17,那么第一个元素会被插入到数组索引 16 的位置,第二个元素会插入到索引 15 的位置,依此类推。

当数组容量被占满时,会触发 grow 扩容方法,扩容后所有元素会被移动到新数组的末尾。

3.3 扩容 (grow) 操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 数组最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int needed) {
    // 缓存旧的数组容量
    final int oldCapacity = elements.length;
    int newCapacity;
    // Double capacity if small; else grow by 50%
    int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
    if (jump < needed
        || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
        newCapacity = newCapacity(needed, jump);
    final Object[] es = elements = Arrays.copyOf(elements, newCapacity);
    // Exceptionally, here tail == head needs to be disambiguated
    if (tail < head || (tail == head && es[head] != null)) {
        // wrap around; slide first leg forward to end of array
        int newSpace = newCapacity - oldCapacity;
        // 将数据复制到新数组末尾,次序不变
        System.arraycopy(es, head,
                            es, head + newSpace,
                            oldCapacity - head);
        // 最后清理复制前的数据
        for (int i = head, to = (head += newSpace); i < to; i++)
            es[i] = null;
    }
}

grow 方法的核心有两部分:

  • 首先是计算 newCapacity
    • 通过条件判断获取 jump,如果 jump 小于 needed 或者旧容量加上 jump 超过了 MAX_ARRAY_SIZE,则调用 newCapacity() 方法计算新容量,实现如下:
       1
       2
       3
       4
       5
       6
       7
       8
       9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      
      private int newCapacity(int needed, int jump) {
          final int oldCapacity = elements.length, minCapacity;
          // 最小新容量设置为 oldCapacity + needed,
          //  如果超过限制,则返回最大 Integer.MAX_VALUE
          //  如果超过 Integer 限制,则抛出异常
          if ((minCapacity = oldCapacity + needed) - MAX_ARRAY_SIZE > 0) {
              if (minCapacity < 0)
                  throw new IllegalStateException("Sorry, deque too big");
              return Integer.MAX_VALUE;
          }
          // minCapacity 在正常范围内,且 needed > jump,则返回 minCapacity
          if (needed > jump)
              return minCapacity;
          // 否则返回 oldCapacity + jump,如果超过限制则返回最大允许容量
          return (oldCapacity + jump - MAX_ARRAY_SIZE < 0)
              ? oldCapacity + jump
              : MAX_ARRAY_SIZE;
      }
    • 否则 newCapacity 直接等于 (oldCapacity + jump)
  • 然后根据新容量扩容数组,并完成数据拷贝:
    • 该过程首先调用 Arrays.copyOf() 方法将就数组中所有元素移动到新数组的开头:
       1
       2
       3
       4
       5
       6
       7
       8
       9
      10
      11
      12
      
      old:
      +---++---++---++---++---++---++---+
      |   ||   ||   ||   || 1 || 2 || 3 |
      +---++---++---++---++---++---++---+
      new:
      +---++---++---++---++---++---++---++---++---++---++---++---++---++---+
      |   ||   ||   ||   ||   ||   ||   ||   ||   ||   ||   ||   ||   ||   |
      +---++---++---++---++---++---++---++---++---++---++---++---++---++---+
      copy:
      +---++---++---++---++---++---++---++---++---++---++---++---++---++---+
      |   ||   ||   ||   || 1 || 2 || 3 ||   ||   ||   ||   ||   ||   ||   |
      +---++---++---++---++---++---++---++---++---++---++---++---++---++---+
    • 然后调用 System.arraycopy() 将数据移动到新数组末尾:
      1
      2
      3
      
      +---++---++---++---++---++---++---++---++---++---++---++---++---++---+
      |   ||   ||   ||   || 1 || 2 || 3 ||   ||   ||   ||   || 1 || 2 || 3 |
      +---++---++---++---++---++---++---++---++---++---++---++---++---++---+
    • 最后清理复制前的数据:
      1
      2
      3
      
      +---++---++---++---++---++---++---++---++---++---++---++---++---++---+
      |   ||   ||   ||   ||   ||   ||   ||   ||   ||   ||   || 1 || 2 || 3 |
      +---++---++---++---++---++---++---++---++---++---++---++---++---++---+

3.4 弹栈 (pop) 操作

ArrayDeque 的弹栈方法 pop() 的实现如下:

1
2
3
public E pop() {
    return removeFirst();
}

该方法的本质就是删除队首元素,实现如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
public E removeFirst() {
    E e = pollFirst();
    if (e == null)
        throw new NoSuchElementException();
    return e;
}
public E pollFirst() {
    final Object[] es;
    final int h;
    E e = elementAt(es = elements, h = head);
    if (e != null) {
        es[h] = null;
        head = inc(h, es.length);
    }
    return e;
}

该方法首先通过 elementAt() 方法定位栈顶元素,实现如下:

1
2
3
4
// 参数 i 为头索引 head
static final <E> E elementAt(Object[] es, int i) {
    return (E) es[i];
}

如果定位到栈顶元素不为 null,则将该元素清空,并调用 inc() 方法移动栈顶:

1
2
3
4
static final int inc(int i, int modulus) {
    if (++i >= modulus) i = 0;
    return i;
}

当所有元素都被弹出时,再次调用 pop() 会让 head 索引指向 0,此处并不存在元素,进而抛出异常。


欢迎关注我的公众号,第一时间获取文章更新:

微信公众号

相关内容