堆栈的链式存储

一些基本概念

栈的链式存储结构实际上就是一个单链表，叫做链栈。

插入和删除操作只能在链顶进行。

链顶指针Top在链表的头部。

堆栈的链式存储实现

堆栈应用

• 表达式求值
• 函数调用及递归实现
• 深度优先搜索
• 回溯算法

Java代码实现

Node类如下：

public class Node {
    private Object data;
    private Node next;

    public Node(){
        super();
    }

    public Node(Object data,Node next){
        super();
        this.data=data;
        this.next=next;
    }

    public Node(Object data){
        super();
        this.data=data;
    }

    public Object getData() {
        return data;
    }

    public void setData(Object data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

/**
 * 堆栈的链式存储
 *
 * @author lck100
 */
public class MyStack {
    private Node head;// 栈

    private MyStack() {
        // 构建头节点
        head = new Node();
        head.setNext(null);
    }

    /**
     * 判断堆栈是否为空
     *
     * @return 如果为空则返回true，否则返回false
     */
    public boolean isEmpty() {
        return head.getNext() == null;
    }

    /**
     * 入栈，将元素压入栈中
     *
     * @param item 要压入栈中的元素
     */
    public void push(Object item) {
        // 由于是链式存储，所以不存在满栈的情况
        // 创建一个新的结点
        Node node = new Node();
        // 为结点赋值
        node.setData(item);
        // 指向当前堆栈的栈顶结点
        node.setNext(head.getNext());
        // 将当前堆栈的下一个元素（栈顶）指向新结点
        head.setNext(node);
    }

    /**
     * 删除并返回堆栈的栈顶元素
     *
     * @return 返回堆栈的栈顶元素
     * @throws Exception 抛出异常
     */
    public Object pop() throws Exception {
        // 判断是否栈为空
        if (isEmpty()) {
            throw new Exception("栈为空，无元素可删除！");
        } else {
            // 获取当前栈顶结点
            Node topNode = head.getNext();
            // 将栈顶结点指向当前栈顶元素
            head.setNext(topNode.getNext());
            // 获取栈顶元素的数据
            return topNode.getData();
        }
    }

    public static void main(String[] args) throws Exception {
        MyStack stack = new MyStack();
        // 判断当前栈是否为空
        System.out.println(stack.isEmpty() + "\n");

        // 入栈
        stack.push("唐僧");
        stack.push("孙悟空");
        stack.push("猪八戒");
        stack.push("沙僧");
        stack.push("小白龙");

        // 出栈
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
        System.out.println(stack.pop());
    }
}

测试，控制台打印：