自定义栈II：链表实现
除了数组之外，我们可以还可使用链表来实现栈结构，它的实现稍微复杂一些，我们先来看链表本身的数据结构：
使用链表实现栈的流程如下：
也就是说，入栈时我们将数据存储在链表的头部，出栈时我们从头部进行移除，并将栈顶指针指向原头部元素的下一个元素，实现代码如下。
我们先来定义一个链表节点：
public class Node { Object value; // 每个节点的数据 Node next; // 下一个节点 public Node(Object value) { this(value, null); } /** * 创建新节点 * @param value 当前节点数据 * @param next 指向下一个节点（头插法） */ public Node(Object value, Node next) { this.value = value; this.next = next; } } 接下来我们使用链表来实现一个完整的栈： public class StackByLinked { private Node top = null; // 栈顶数据 private int maxSize = 0; // 栈最大容量 private int leng = 0; // 栈实际容量 public StackByLinked(int initSize) throws Exception { if (initSize <= 0) { throw new Exception("栈容量不能小于等于0"); } top = null; maxSize = initSize; leng = 0; } /** * 容量是否已满 * @return */ public boolean isFull() { return leng >= maxSize; } /** * 是否为空 * @return */ public boolean isEmpty() { return leng <= 0; } /** * 入栈 * @param val * @return * @throws Exception */ public boolean push(Object val) throws Exception { if (this.isFull()) { // 容量已满 throw new Exception("容量已满"); } top = new Node(val, top); // 存入信息，并将当前节点设置为头节点 leng++; return true; } /** * 出栈（移除） * @return * @throws Exception */ public Node pop() throws Exception { if (this.isEmpty()) { throw new Exception("栈为空，无法进行移除操作"); } Node item = top; // 返回当前元素 top = top.next; leng--; return item; } /** * 查询栈顶信息 * @return */ public Node peek() throws Exception { if (isEmpty()) { throw new Exception("你操作的是一个空栈"); } return top; } // 代码测试 public static void main(String[] args) throws Exception { StackByLinked stack = new StackByLinked(10); stack.push("Hello"); stack.push("Java"); System.out.println(stack.peek().value); stack.pop(); System.out.println(stack.pop().value); } }
以上程序的执行结果是：
Java
Hello
总结
本文我们使用了数组和链表等物理结构来实现了栈，当然我们也可以使用其他容器来实现，比如 Java 中的 List，我们只需要保证在操作栈时是后进先出的执行顺序，并且至少包含 3 个重要方法：入栈、出栈和查询栈顶元素就可以了。
最后
算法和数据结构的学习是 3 分学 7 分练，只看不练是没办法学好算法的，而且学习算法和数据结构是一个循序渐进的过程，短时间内不会有明显的收效。因为这些算法经过了几百年的发展和积累才得以流传下来的，所以想要“玩得转”还需要一点耐心。
这里给你讲一个学习算法的“秘诀”：看不懂的知识要反复看，如果反复看还是看不懂，那么别着急，休息一下再继续看！相信我，对于学习算法这件事，所有人的过程都是一样的。
