java代码如何用链表实现链式栈 java代码链式栈结构的基础编写技巧​

class Node<T> {
    T data;         // 存储的数据
    Node<T> next;   // 指向下一个节点的引用

    public Node(T data) {
        this.data = data;
        this.next = null; // 新节点默认不指向任何地方
    }
}

top

size

public class LinkedStack<T> {
    private Node<T> top; // 栈顶元素，所有操作都围绕它进行
    private int size;    // 栈中元素的数量

    public LinkedStack() {
        this.top = null; // 初始时栈是空的
        this.size = 0;
    }

    /**
     * 入栈操作：将元素添加到栈顶。
     * 这是一个O(1)操作，非常高效。
     */
    public void push(T item) {
        Node<T> newNode = new Node<>(item);
        newNode.next = top; // 新节点指向当前的栈顶
        top = newNode;      // 新节点成为新的栈顶
        size++;
        // 思考一下，这种操作方式，新元素总是在最前面，这正是栈的LIFO特性所需要的。
    }

    /**
     * 出栈操作：移除并返回栈顶元素。
     * 同样是O(1)操作。
     */
    public T pop() {
        if (isEmpty()) {
            // 必须处理栈空的情况，否则会遇到NullPointerException。
            // 抛出异常是比较标准的做法，告知调用者栈无法执行此操作。
            throw new IllegalStateException("Stack is empty, cannot pop.");
        }
        T data = top.data; // 获取栈顶数据
        top = top.next;    // 栈顶下移，指向下一个节点
        size--;
        return data;
    }

    /**
     * 查看栈顶元素：返回栈顶元素但不移除它。
     * O(1)操作。
     */
    public T peek() {
        if (isEmpty()) {
            // 同样需要检查栈是否为空。
            throw new IllegalStateException("Stack is empty, cannot peek.");
        }
        return top.data; // 直接返回栈顶数据
    }

    /**
     * 判断栈是否为空。
     */
    public boolean isEmpty() {
        return top == null; // 或者 return size == 0; 效果一样，但top == null更直观地反映结构状态。
    }

    /**
     * 返回栈中元素的数量。
     */
    public int size() {
        return size;
    }

    // 可以在这里添加一个简单的main方法进行测试
    public static void main(String[] args) {
        LinkedStack<String> myStack = new LinkedStack<>();
        System.out.println("Is stack empty? " + myStack.isEmpty()); // true

        myStack.push("Apple");
        myStack.push("Banana");
        myStack.push("Cherry");

        System.out.println("Stack size: " + myStack.size()); // 3
        System.out.println("Top element: " + myStack.peek()); // Cherry

        System.out.println("Popped: " + myStack.pop()); // Cherry
        System.out.println("Stack size after pop: " + myStack.size()); // 2
        System.out.println("New top element: " + myStack.peek()); // Banana

        myStack.push("Date");
        System.out.println("Top element after push: " + myStack.peek()); // Date

        while (!myStack.isEmpty()) {
            System.out.println("Popping: " + myStack.pop());
        }
        System.out.println("Is stack empty now? " + myStack.isEmpty()); // true

        try {
            myStack.pop(); // This should throw an exception
        } catch (IllegalStateException e) {
            System.out.println("Caught expected error: " + e.getMessage());
        }
    }
}

ArrayDeque

Stack

top

pop()

peek()

top

null

top.data

top.next

NullPointerException

if (isEmpty())

null

IllegalStateException

IllegalStateException

top

push

pop

top

size

size

push

size++

pop

size--

size()

size

LinkedStack<T>

Node

LinkedStack

ClassCastException

top

top

next