封装属于自己的数据结构

1. 引言

在编程中，数据结构是指按照一定的逻辑关系来组织和存储数据的方式。常见的数据结构有数组、链表、栈、队列、树、图等。标准的库和框架提供了很多常用的数据结构实现，但在某些情况下，程序员可能需要根据特定的需求设计和实现属于自己的数据结构。今天，我们将介绍如何在Java中封装属于自己的数据结构，并通过具体的代码示例来实现自定义的数据结构。

2. 数据结构封装的基本概念

2.1 封装的意义

封装是面向对象编程中的一个重要概念，指的是将数据和操作数据的方法组合到一起，对外界隐藏数据的具体实现细节，只暴露出必要的接口。在自定义数据结构时，封装允许我们将数据结构的实现细节隐藏起来，从而提供清晰的接口供外部使用。

封装自定义数据结构的目的是：

提高代码的可维护性：通过封装，程序员可以改变数据结构的实现，而不影响使用该数据结构的代码。
提升代码的复用性：封装后的数据结构可以在不同的项目和场景中被复用。
数据保护：通过封装，数据内部的变化对外部是透明的，防止外部直接修改数据。

2.2 如何封装数据结构

封装自定义数据结构的一般步骤包括：

定义数据结构的核心属性：首先要明确你需要存储什么样的数据，以及如何组织这些数据。
设计对外的操作接口：你需要设计一些公共方法（接口），供外部使用。例如：添加元素、删除元素、查询元素等。
实现数据结构的内部操作：根据需要实现数据结构的内部操作，如元素的插入、删除、查询等。
保持内部状态的有效性：确保数据结构内部的状态在外部操作中始终保持一致和有效。

3. 封装一个栈数据结构（Stack）

栈（Stack）是一种后进先出（LIFO，Last In First Out）的数据结构，即最后插入的元素最先被取出。栈常用于需要“回退”操作的场景，例如浏览器的前进和后退按钮。

3.1 栈的基本操作

栈的基本操作有：

push：将一个元素压入栈中。
pop：将栈顶的元素弹出。
peek：查看栈顶的元素，但不弹出它。
isEmpty：判断栈是否为空。

3.2 Java中的栈实现

我们将封装一个简单的栈类来实现这些基本操作。

示例代码：

// 自定义栈的实现
public class MyStack<T> {
    // 存储栈中元素的数组
    private Object[] elements;
    // 栈的大小
    private int size;
    // 栈的容量
    private static final int DEFAULT_CAPACITY = 10;

    // 构造方法，初始化栈的容量
    public MyStack() {
        elements = new Object[DEFAULT_CAPACITY];
        size = 0;
    }

    // 将元素压入栈中
    public void push(T element) {
        // 检查栈是否已满，若满则扩展栈容量
        if (size == elements.length) {
            expandCapacity();
        }
        elements[size++] = element;  // 将元素添加到栈顶
    }

    // 弹出栈顶元素
    @SuppressWarnings("unchecked")
    public T pop() {
        if (isEmpty()) {
            throw new IllegalStateException("栈为空，无法弹出元素");
        }
        T element = (T) elements[--size];  // 获取栈顶元素并将栈大小减1
        elements[size] = null;  // 清除栈顶元素的引用
        return element;
    }

    // 查看栈顶元素
    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("栈为空，无法查看栈顶元素");
        }
        return (T) elements[size - 1];
    }

    // 判断栈是否为空
    public boolean isEmpty() {
        return size == 0;
    }

    // 扩展栈容量
    private void expandCapacity() {
        int newCapacity = elements.length * 2;  // 扩展容量为原来的2倍
        Object[] newElements = new Object[newCapacity];
        System.arraycopy(elements, 0, newElements, 0, elements.length);  // 复制原数组的元素
        elements = newElements;  // 更新栈的元素数组
    }

    // 获取栈中元素的个数
    public int size() {
        return size;
    }
}

3.3 代码解读

栈的存储方式：我们使用了一个Object[]数组来存储栈中的元素，并通过size来跟踪当前栈中有多少元素。
扩容机制：当栈的容量不够时，我们会自动将栈的容量扩展为原来容量的两倍，确保栈能够容纳更多元素。
基本操作实现：
- push()方法将元素压入栈中，若栈满则扩展容量。
- pop()方法弹出栈顶元素，并更新栈的大小。
- peek()方法查看栈顶元素但不弹出。
- isEmpty()方法检查栈是否为空。

4. 封装一个队列数据结构（Queue）

队列（Queue）是一种先进先出（FIFO，First In First Out）的数据结构，即最先插入的元素最先被取出。队列常用于任务调度、打印队列等场景。

4.1 队列的基本操作

队列的基本操作有：

enqueue：将一个元素加入队列。
dequeue：从队列中移除并返回最早加入的元素。
peek：查看队列中最早加入的元素，但不移除它。
isEmpty：判断队列是否为空。

4.2 Java中的队列实现

我们将封装一个简单的队列类来实现这些基本操作。

示例代码：

// 自定义队列的实现
public class MyQueue<T> {
    // 存储队列元素的数组
    private Object[] elements;
    // 队列的头部
    private int front;
    // 队列的尾部
    private int rear;
    // 队列的容量
    private static final int DEFAULT_CAPACITY = 10;

    // 构造方法，初始化队列
    public MyQueue() {
        elements = new Object[DEFAULT_CAPACITY];
        front = 0;
        rear = 0;
    }

    // 将元素加入队列
    public void enqueue(T element) {
        if ((rear + 1) % elements.length == front) {
            throw new IllegalStateException("队列已满，无法加入元素");
        }
        elements[rear] = element;
        rear = (rear + 1) % elements.length;
    }

    // 从队列中移除元素
    @SuppressWarnings("unchecked")
    public T dequeue() {
        if (isEmpty()) {
            throw new IllegalStateException("队列为空，无法移除元素");
        }
        T element = (T) elements[front];
        front = (front + 1) % elements.length;
        return element;
    }

    // 查看队列中最早加入的元素
    @SuppressWarnings("unchecked")
    public T peek() {
        if (isEmpty()) {
            throw new IllegalStateException("队列为空，无法查看元素");
        }
        return (T) elements[front];
    }

    // 判断队列是否为空
    public boolean isEmpty() {
        return front == rear;
    }

    // 获取队列中元素的个数
    public int size() {
        return (rear - front + elements.length) % elements.length;
    }
}

4.3 代码解读

队列的存储方式：我们同样使用了一个数组来存储队列中的元素。不同的是，我们使用了front指针指向队列的头部，rear指针指向队列的尾部。
队列的循环结构：为了优化内存的使用，我们使用了循环队列的方式。rear和front指针在数组的末尾可以回绕到数组的开头，避免了数组空间的浪费。
基本操作实现：
- enqueue()方法将元素加入队列。
- dequeue()方法从队列中移除并返回最早加入的元素。
- peek()方法查看队列中最早加入的元素，但不移除

它。

isEmpty()方法判断队列是否为空。

5. 总结

今天我们通过具体的例子了解了如何在Java中封装自己的数据结构。通过封装，我们可以将数据结构的实现细节隐藏起来，仅提供必要的操作接口。我们通过栈和队列这两个常见的数据结构，展示了如何设计和实现自己的数据结构。封装数据结构不仅能够提高代码的可维护性和复用性，也能让我们更好地理解和运用数据结构的基本操作。希望大家在以后的开发中能够灵活运用这些技巧，封装出符合自己需求的数据结构。

去1:1私密咨询