万字长文带你漫游数据结构世界（四）栈

腾讯云产品技术支持、企业上云、迁移服务、上云部署方案免费提供，您身边的企业云计算产品服务专家

栈

栈是一种数据结构，在Java里面体现是Stack类。它的本质是先进后出，就像是一个桶，只能不断的放在上面，取出来的时候，也只能不断的取出最上面的数据。要想取出底层的数据，只有等到上面的数据都取出来，才能做到。当然，如果有这种需求，我们一般会使用双向队列。

以下是栈的特性演示：

栈的底层用什么实现的？其实可以用链表，也可以用数组，但是JDK底层的栈，是用数组实现的，封装之后，通过API操作的永远都只能是最后一个元素，栈经常用来实现递归的功能。如果想要了解Java里面的栈或者其他集合实现分析，可以看看这系列文章：http://aphysia.cn/categories/collection

元素加入称之为入栈（压栈），取出元素，称之为出栈，栈顶元素则是最后一次放进去的元素。

使用数组实现简单的栈(注意仅供参考测试，实际会有线程安全等问题)：

import java.util.Arrays;

public class MyStack<T> {
    private T[] data;
    private int length = 2;
    private int maxIndex;

    public MyStack() {
        data = (T[]) new Object[length];
        maxIndex = -1;
    }

    public void push(T element) {
        if (isFull()) {
            length = 2 * length;
            data = Arrays.copyOf(data, length);
        }
        data[maxIndex + 1] = element;
        maxIndex++;
    }

    public T pop() {
        if (isEmpty()) {
            throw new IndexOutOfBoundsException("栈内没有数据");
        } else {
            T[] newdata = (T[]) new Object[data.length - 1];
            for (int i = 0; i < data.length - 1; i++) {
                newdata[i] = data[i];
            }
            T element = data[maxIndex];
            maxIndex--;
            data = newdata;
            return element;
        }
    }

    private boolean isFull() {
        return data.length - 1 == maxIndex;
    }

    public boolean isEmpty() {
        return maxIndex == -1;
    }

    public void display() {
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i]+" ");
        }
        System.out.println("");
    }
}

测试代码：

public class MyStackTest { public static void main(String[] args) { MyStack<Integer> myStack = new MyStack<>(); myStack.push(1); myStack.push(2); myStack.push(3); myStack.push(4); myStack.display(); System.out.println(myStack.pop()); myStack.display(); } }

输出结果如下，符合预期：

1 2 3 4 4 1 2 3

栈的特点就是先进先出，但是如果需要随机取出前面的数据，效率会比较低，需要倒腾出来，但是如果底层使用数组，理论上是可以通过索引下标取出的，Java里面正是这样实现。