Java函数实现数据结构：栈、队列、链表全解析

Java作为一门高级编程语言，不仅提供了丰富的语法和模块库，同时也允许开发者自己实现各种数据结构。本文将会全面解析Java实现栈、队列和链表的过程及其重要函数。

1. 栈（Stack）

栈是一种定义为“后进先出”（Last-In-First-Out，LIFO）的数据结构。它基于数组或链表实现，提供了一组简单的操作，例如push（压入）、pop（弹出）和peek（读取栈顶）等。下面是Java语言实现栈的基本代码：

public class Stack {
    private int top;
    private int maxSize;
    private Object[] stackArray;
 
    public Stack(int maxSize) {
        this.maxSize = maxSize;
        stackArray = new Object[maxSize];
        top = -1;
    }
 
    public void push(Object obj) {
        if (isFull())
            throw new RuntimeException("Stack is full!");
        stackArray[++top] = obj;
    }
 
    public Object pop() {
        if (isEmpty())
            throw new RuntimeException("Stack is empty!");
        return stackArray[top--];
    }
 
    public Object peek() {
        if (isEmpty())
            throw new RuntimeException("Stack is empty!");
        return stackArray[top];
    }
 
    public boolean isEmpty() {
        return (top == -1);
    }
 
    public boolean isFull() {
        return (top == maxSize - 1);
    }
}

这段代码定义了一个堆栈（Stack）类，其中包括了五个私有的实例变量，分别是栈顶指针（top）、栈的最大尺寸（maxSize）、存储元素的数组（stackArray）以及两个标志栈是否为空和是否已满的布尔类型的函数。

接下来，我们定义了一个构造方法来初始化栈的大小和顶部指针。此外，还包含一个包装对象（Object）作为参数的push()方法，以将一个单个对象添加到堆栈的顶部。pop()方法则删除并返回顶部对象，peek()方法则返回顶部对象而不删除它。isEmpty()和isFull()方法分别获取栈的状态并返回布尔值。

2. 队列（Queue）

队列是一种定义为“先进先出”（First-In-First-Out，FIFO）的数据结构。它同样可以基于数组或链表实现，提供了一组简单的操作。与栈相比，队列是更高级的模型，因为它提供了有序线性的元素集合，并且支持在任意位置插入和删除元素等更高级操作。下面是Java语言实现队列的基本代码：

public class Queue {
    private int front, rear, size;
    private int capacity;
    private Object[] arr;
 
    public Queue(int capacity) {
        this.capacity = capacity;
        front = this.size = 0;
        rear = capacity - 1;
        arr = new Object[this.capacity];
    }
 
    public boolean isFull(Queue queue) {
        return (queue.size == queue.capacity);
    }
 
    public boolean isEmpty(Queue queue) {
        return (queue.size == 0);
    }
 
    public void enqueue(Object item) {
        if (isFull(this))
            return;
        this.rear = (this.rear + 1) % this.capacity;
        this.arr[this.rear] = item;
        this.size = this.size + 1;
    }
 
    public Object dequeue() {
        if (isEmpty(this))
            return null;
 
        Object item = this.arr[this.front];
        this.front = (this.front + 1) % this.capacity;
        this.size = this.size - 1;
        return item;
    }
 
    public Object front() {
        if (isEmpty(this))
            return null;
 
        return this.arr[this.front];
    }
 
    public Object rear() {
        if (isEmpty(this))
            return null;
 
        return this.arr[this.rear];
    }
}

这段代码定义了一个队列（Queue）类，其中包括了四个私有的实例变量，分别是队列的头尾指针（front和rear）、队列的最大容量（capacity）以及存储元素的数组（arr）。我们定义了一个构造方法来初始化队列的大小和头尾指针。此外，还包含两个布尔型函数，分别判断当前队列是否已满和空。enqueue()方法用于在队列的尾部添加一个元素，dequeue()方法用于删除头部元素并返回其值，front()和rear()方法分别返回头部和尾部元素的值。

3. 链表（LinkedList）

链表是一种线性数据结构，其中每个节点都包含数据和一个指向下一个节点的指针，它们可以是单向链表也可以是双向链表。LinkedList是Java作为一种强类型语言提供的链表数据结构实现。

public class Node {
    int data;
    Node nextNode;

    public Node(int data) {
        this.data = data;
    }

    public void setNextNode(Node nextNode) {
        this.nextNode = nextNode;
    }

    public Node getNextNode() {
        return nextNode;
    }

    public int getData() {
        return data;
    }
}

public class LinkedList {
    Node head;

    public LinkedList() {
        head = null;
    }

    public void add(int data) {
        Node newNode = new Node(data);

        if (head == null) {
            head = newNode;
        } else {
            Node currentNode = head;
            while (currentNode.getNextNode() != null) {
                currentNode = currentNode.getNextNode();
            }
            currentNode.setNextNode(newNode);
        }
    }

    public void delete(int data) {
        if (head == null) {
            return;
        } else if (head.getData() == data) {
            head = head.getNextNode();
            return;
        } else {
            Node currentNode = head;
            while (currentNode.getNextNode() != null) {
                if (currentNode.getNextNode().getData() == data) {
                    currentNode.setNextNode(currentNode.getNextNode().getNextNode());
                    return;
                }
                currentNode = currentNode.getNextNode();
            }
            return;
        }
    }

这段代码中，我们定义了一个链表（LinkedList）类，这个类也是由节点（Node）组成的。Node类用于创建一个节点，包含一个实例变量data，它存储节点的值，以及一个实例变量nextNode，它存储下一个节点的指针。LinkedList类包含一个实例变量head，该变量指向链表的第一个节点。

我们定义了一个构造函数，它将head初始化为null。add()函数将添加一个节点到链表的末尾，并将该节点作为最后一个节点。delete()函数将从链表中移除指定值的节点。如果该节点是头节点，则头指针将指向下一个节点。否则，我们遍历链表，找到需要删除的节点，并将前一个节点的nextNode指向被删除节点的下一个节点，以达到删除节点的目的。

总结

本文介绍了使用Java语言实现栈、队列和链表的方法及其重要函数，这些数据结构都是我们日常编程中常用的基本数据结构。使用Java语言自己实现数据结构不仅有助于更好地理解其工作原理，而且可以通过重写其方法使它们更适合特定的应用场景。