数据结构与算法(Java)--栈(Linked_Stack)

admin

2024-12-07 5 0条评论

数据结构与算法(Java)--栈(Linked_Stack)

栈（Stack）是一种后进先出（LIFO, Last In First Out）的数据结构。栈的操作主要包括入栈（push）、出栈（pop）、查看栈顶元素（peek）和检查栈是否为空（isEmpty）。本文将详细介绍如何使用链表（Linked List）来实现栈结构，并给出相应的Java代码示例。

一、栈的基本概念

栈是一种受限的线性表，只允许在一端进行插入和删除操作。栈的特点是后进先出，即最后压入栈的元素最先弹出。

二、链表实现栈的原理

使用链表实现栈，每次入栈时在链表头部插入元素，每次出栈时从链表头部删除元素。这样可以保证所有操作的时间复杂度为O(1)。

三、链表实现栈的具体步骤

定义节点类：表示栈中的每个元素。
定义栈类：包含栈的基本操作。

1. 节点类

class Node<T> {
    T data;
    Node<T> next;

    public Node(T data) {
        this.data = data;
        this.next = null;
    }
}

2. 栈类

public class LinkedStack<T> {
    private Node<T> top; // 栈顶节点
    private int size; // 栈的大小

    public LinkedStack() {
        this.top = null;
        this.size = 0;
    }

    // 入栈
    public void push(T data) {
        Node<T> newNode = new Node<>(data);
        newNode.next = top;
        top = newNode;
        size++;
    }

    // 出栈
    public T pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈为空，无法出栈");
        }
        T data = top.data;
        top = top.next;
        size--;
        return data;
    }

    // 查看栈顶元素
    public T peek() {
        if (isEmpty()) {
            throw new RuntimeException("栈为空，无法查看栈顶元素");
        }
        return top.data;
    }

    // 检查栈是否为空
    public boolean isEmpty() {
        return top == null;
    }

    // 获取栈的大小
    public int size() {
        return size;
    }
}

四、链表实现栈的完整代码

// 节点类
class Node<T> {
    T data;
    Node<T> next;

    public Node(T data) {
        this.data = data;
        this.next = null;
    }
}

// 栈类
public class LinkedStack<T> {
    private Node<T> top; // 栈顶节点
    private int size; // 栈的大小

    public LinkedStack() {
        this.top = null;
        this.size = 0;
    }

    // 入栈
    public void push(T data) {
        Node<T> newNode = new Node<>(data);
        newNode.next = top;
        top = newNode;
        size++;
    }

    // 出栈
    public T pop() {
        if (isEmpty()) {
            throw new RuntimeException("栈为空，无法出栈");
        }
        T data = top.data;
        top = top.next;
        size--;
        return data;
    }

    // 查看栈顶元素
    public T peek() {
        if (isEmpty()) {
            throw new RuntimeException("栈为空，无法查看栈顶元素");
        }
        return top.data;
    }

    // 检查栈是否为空
    public boolean isEmpty() {
        return top == null;
    }

    // 获取栈的大小
    public int size() {
        return size;
    }

    public static void main(String[] args) {
        LinkedStack<Integer> stack = new LinkedStack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);

        System.out.println("栈顶元素: " + stack.peek()); // 输出: 栈顶元素: 3
        System.out.println("出栈元素: " + stack.pop()); // 输出: 出栈元素: 3
        System.out.println("栈顶元素: " + stack.peek()); // 输出: 栈顶元素: 2
        System.out.println("栈的大小: " + stack.size()); // 输出: 栈的大小: 2
    }
}

五、总结

使用链表实现栈是一种非常灵活的方法，它不需要预先分配固定大小的内存空间，能够根据需要动态增长。在链表实现的栈中，每次入栈和出栈操作的时间复杂度都是O(1)，保证了操作的高效性。

思维导图

链表实现栈 (Linked_Stack)
│
├── 基本概念
│   ├── 栈的定义
│   └── 后进先出 (LIFO)
│
├── 实现原理
│   ├── 链表头部插入 (push)
│   └── 链表头部删除 (pop)
│
├── 节点类
│   ├── 数据域 (data)
│   └── 指针域 (next)
│
├── 栈类
│   ├── 属性
│   │   ├── top (栈顶节点)
│   │   └── size (栈的大小)
│   ├── 方法
│   │   ├── push (入栈)
│   │   ├── pop (出栈)
│   │   ├── peek (查看栈顶元素)
│   │   ├── isEmpty (检查栈是否为空)
│   │   └── size (获取栈的大小)
│
├── 完整代码
│   └── 节点类与栈类实现
│
└── 主要操作
    ├── 入栈 (push)
    ├── 出栈 (pop)
    ├── 查看栈顶元素 (peek)
    └── 检查栈是否为空 (isEmpty)

通过本文的讲解，读者可以更深入地理解如何使用链表来实现栈结构，并掌握其基本操作和应用场景。在实际开发中，合理选择和使用数据结构，可以显著提升程序的性能和可维护性。希望本文对你有所帮助。

标签：节点