Stack

字数: 0 字 时长: 0 分钟

1. 栈概述

Stack 这个类在 Java 实际开发中并不算常用，但：

栈这种数据结构在整个计算机体系中非常重要。

栈（Stack）有些地方也叫：

堆栈

不过这个叫法容易和：

Heap
堆

混淆，所以这里统一称为：

栈

1.1 栈的数据结构

栈可以想象成一摞盘子。

第一个盘子放在最下面，第二个盘子放在第一个盘子上面，后面的盘子继续往上叠。

对于这一摞盘子，可以做两个最基本的操作：

在最上面放一个新的盘子

把最上面的盘子拿走

如果想直接从中间或者底部拿出一个盘子，就比较麻烦。

例如要拿最下面的盘子：

先拿走顶部盘子
    ↓
继续拿走上面的盘子
    ↓
最终才能拿到底部盘子

这种数据结构遵循：

LIFO
Last In First Out
后进先出

也就是：

最后进入栈的元素，最先离开栈。

1.2 push 和 pop

栈最常见的两个操作：

push
    ↓
压入


pop
    ↓
弹出

push 表示：

把一个元素放到栈顶。

pop 表示：

把栈顶元素取出并移除。

例如：

push 1

push 2

push 3

栈结构：

栈顶
 ↓
 3
 2
 1

此时：

3

最后进入栈，却会最先被：

pop

出去。

这就是：

LIFO

1.3 TOP 指针

为了让栈按照：

LIFO

工作，可以使用一个：

TOP

标记当前栈顶位置。

基本思路：

1. 初始化栈时：

TOP = -1

因此可以通过：

TOP == -1

判断栈是否为空。

2. 压入元素时：

TOP + 1
    ↓
新元素写入 TOP 对应的位置

3. 弹出元素时：

返回 TOP 位置的元素
    ↓
TOP - 1

4. 压入之前需要判断：

栈是否已经满了

也就是：

isFull()

5. 弹出之前需要判断：

栈是否为空

也就是：

isEmpty()

整个过程：

例如空栈：

TOP = -1

压入：

1

以后：

stack[0] = 1

TOP = 0

继续压入：

2

以后：

stack[1] = 2

TOP = 1

继续压入：

3

以后：

stack[2] = 3

TOP = 2

然后弹出：

3

返回：

stack[2]

同时：

TOP
    ↓
2 → 1

2. 自定义栈

假设栈中保存的是：

int

可以使用 Java 自己实现一个最简单的栈。

需要三个字段：

int[] arr
    ↓
保存栈中的数据


int top
    ↓
记录栈顶位置


int capacity
    ↓
记录栈容量

定义：

class StackDemo {

    private int[] arr;

    private int top;

    private int capacity;
}

2.1 初始化栈

StackDemo(
        int size) {

    arr =
            new int[size];

    capacity =
            size;

    top =
            -1;
}

初始化以后：

capacity = size

top = -1

表示：

当前栈为空

2.2 push()

向栈中压入元素：

public void push(
        int value) {

    if (isFull()) {

        System.out.println(
                "溢出\n程序终止\n"
        );

        System.exit(1);
    }

    System.out.println(
            "压入 " + value
    );

    arr[++top] =
            value;
}

核心：

arr[++top] = value;

执行过程：

top + 1
    ↓
移动栈顶位置
    ↓
写入新元素

2.3 pop()

从栈中弹出元素：

public int pop() {

    if (isEmpty()) {

        System.out.println(
                "栈是空的"
        );

        System.exit(1);
    }

    return arr[top--];
}

核心：

arr[top--]

执行过程：

返回当前栈顶元素
    ↓
top - 1

2.4 size()

返回当前栈的大小：

public int size() {

    return top + 1;
}

因为：

top 从 0 开始

所以元素数量：

top + 1

2.5 isEmpty()

判断栈是否为空：

public boolean isEmpty() {

    return top == -1;
}

当：

top = -1

说明：

栈中没有元素

2.6 isFull()

判断栈是否已经满：

public boolean isFull() {

    return top
            == capacity - 1;
}

例如容量：

5

数组下标范围：

0 ~ 4

所以：

top == 4

就说明栈已经满了。

2.7 printStack()

打印栈中的元素：

public void printStack() {

    for (
            int i = 0;
            i <= top;
            i++
    ) {

        System.out.println(
                arr[i]
        );
    }
}

2.8 测试

public static void main(
        String[] args) {

    StackDemo stack =
            new StackDemo(5);

    stack.push(1);
    stack.push(2);
    stack.push(3);
    stack.push(4);

    stack.pop();

    System.out.println(
            "\n弹出元素后"
    );

    stack.printStack();
}

输出：

压入 1
压入 2
压入 3
压入 4

弹出元素后
1
2
3

由于这个栈是通过数组实现的，所以：

push
    ↓
O(1)


pop
    ↓
O(1)

2.9 栈的使用场景

栈虽然结构简单，但用途很多。

2.9.1 反转字符

由于栈遵循：

LIFO

所以可以：

按照正常顺序压入字符
    ↓
再依次弹出
    ↓
得到反转后的顺序

2.9.2 浏览器后退

浏览器访问页面时，可以把访问过的 URL 按顺序压入栈中。

访问新页面
    ↓
URL 压入栈


点击后退
    ↓
弹出当前 URL
    ↓
回到之前的页面

3. Java Stack 类

Java 已经提供了一个：

java.util.Stack

它继承自：

Vector

继承关系：

Vector
    ↑
Stack

而 Vector 的很多核心方法都使用：

synchronized

进行同步。

所以 Stack 也带有这种早期线程安全集合的设计特点，有点类似：

StringBuffer

3.1 Stack 基本使用

例如：

Stack<String> stack =
        new Stack<>();

stack.push(
        "张无忌"
);

stack.push(
        "周芷若"
);

stack.push(
        "灭绝师太"
);

System.out.println(
        stack
);

Stack 中比较重要的方法：

push()

pop()

peek()

empty()

search()

3.2 push()

push() 用来：

压入元素

源码：

public E push(
        E item) {

    addElement(
            item
    );

    return item;
}

可以看到：

push()

本身没有：

synchronized

但内部调用了 Vector 的：

addElement()

源码：

public synchronized void addElement(
        E obj) {

    modCount++;

    ensureCapacityHelper(
            elementCount + 1
    );

    elementData[
            elementCount++
    ] = obj;
}

所以：

push()
    ↓
addElement()
    ↓
synchronized
    ↓
向数组中添加元素

3.3 pop()

pop() 用来：

返回并移除栈顶元素

源码：

public synchronized E pop() {

    E obj;

    int len =
            size();

    obj =
            peek();

    removeElementAt(
            len - 1
    );

    return obj;
}

执行过程：

size()
    ↓
获取栈大小
    ↓
peek()
    ↓
获取栈顶元素
    ↓
removeElementAt()
    ↓
删除栈顶元素
    ↓
返回元素

3.4 peek()

peek() 只获取：

栈顶元素

但不会删除。

源码：

public synchronized E peek() {

    int len =
            size();

    if (len == 0) {

        throw new EmptyStackException();
    }

    return elementAt(
            len - 1
    );
}

如果：

栈为空

则抛出：

EmptyStackException

否则：

len - 1

就是栈顶元素的位置。

3.5 Stack 的底层结构

Stack 继承自：

Vector

而 Vector 底层使用数组保存元素。

部分结构：

public class Vector<E>
        extends AbstractList<E>
        implements List<E>,
                   RandomAccess,
                   Cloneable,
                   Serializable {

    protected Object[] elementData;

    protected int elementCount;

    protected int capacityIncrement;
}

所以：

Stack
    ↓
继承 Vector
    ↓
Vector
    ↓
Object[] elementData

也就是说：

Stack 底层仍然是数组结构。

pop() 最终会调用：

removeElementAt(
        len - 1
);

删除栈顶元素。

Vector 的删除逻辑本身还具有：

System.arraycopy()

进行数组移动的能力。

4. 小结

栈最核心的特点：

LIFO
Last In First Out
后进先出

两个最重要的操作：

push
    ↓
压入元素


pop
    ↓
弹出元素

栈顶通常使用：

TOP

表示。

自定义数组栈：

arr
    ↓
保存元素


top
    ↓
记录栈顶


capacity
    ↓
记录容量

对于数组实现：

push
    ↓
O(1)


pop
    ↓
O(1)

Java 也提供了：

java.util.Stack

它继承：

Vector

所以：

Stack
    ↓
Vector
    ↓
动态数组

Stack 类本身现在并不算常用，但：

栈这种后进先出的数据结构非常重要。

在 Java 中，现代代码通常推荐使用：

ArrayDeque

来代替：

Stack

因为 ArrayDeque 不带 Vector 这套同步设计，通常更加轻量。