Java 使用泛型实现栈数据结构

使用泛型，实现栈数据结构（本例为链式栈）。

栈是一种运算受限的线性表，是一种先进后出的数据结构，限定只能在一端进行插入和删除操作，允许操作的一端称为栈顶，不允许操作的称为栈底。

链式栈的内部是链式存储的，我们现在自己来实现链式存储机制。

直接看代码：

public class CustomStack<T> {
    private static class Node<U> { // 节点，由入栈元素和元素的地址组成
        U item; // 入栈的元素
        Node<U> next; // 下一个元素的地址

        Node() { item = null; next = null; }

        Node(U item, Node<U> next) {
            this.item = item;
            this.next = next;
        }

        boolean end() { // 末端表示，判断是否为空栈。
            return item == null && next == null;
        }
    }

    private Node<T> top = new Node<>();  // 栈顶

    public void push(T item) { // 压栈，向栈中添加元素
        top = new Node<>(item, top);
    }

    public T pop() { // 出栈，删除栈中的元素
        T result = top.item;
        if (!top.end()) {
            top = top.next;
        }
        return result;
    }

    public static void main(String[] args) {
        CustomStack<String> lss = new CustomStack<>();
        for (String s : "Phasers on stun!".split(" ")) {
            lss.push(s);
        }
        String str;
        while ((str = lss.pop()) != null) {
            System.out.println(str);
        }
    }

}

在CustomStack<String> lss = new CustomStack<>();创建完CustomStack对象，在内存中就存在了一个top节点，此时的栈只有一个top节点，并且是一个用来作为栈顶的空节点，foreach循环开始，将"Phasers on stun!"按空格拆分成String数组，调用push()方法进行压栈，每一次压栈，都将上一个Node的内存地址保存到自身的next属性中，循环结束，就形成了一个链式的栈结构。

压栈图示：

压栈

在while循环中调用pop()方法进行出栈，出栈时，先将节点中的item值取出，随后调用end()方法判断是否到达栈顶，若没有到达栈顶，就将当前节点的内存地址，修改为位于自己前面的节点的地址，到达栈顶时，栈中节点全部出栈，只会留下栈顶一个空的节点。

出栈图示：

出栈