Java函数实现基本的数据结构（如堆栈、队列和链表等）

Java语言是一种强大的面向对象编程语言，支持各种数据结构和算法的实现。在Java编程中，我们可以使用函数来实现各种基本的数据结构，如堆栈、队列和链表等。这些数据结构都是计算机科学中非常基本的概念，几乎在所有编程语言和计算机科学领域中都有广泛的应用。下面，我们将讨论这些数据结构以及如何在Java编程中使用函数来实现它们。

一、堆栈

堆栈是一种基于后进先出（LIFO）原则的数据结构。这意味着，最后被插入堆栈的元素最先被弹出。例如，浏览器的“后退”按钮就是一个堆栈结构。在Java中，我们可以使用数组或链表来实现堆栈。

使用数组来实现堆栈：

public class Stack {
    private int[] arr;
    private int top;

    public Stack(int size) {
        arr = new int[size];
        top = -1;
    }

    public void push(int element) {
        arr[++top] = element;
    }

    public int pop() {
        return arr[top--];
    }

    public int peek() {
        return arr[top];
    }

    public boolean isEmpty() {
        return (top == -1);
    }

    public boolean isFull() {
        return (top == arr.length - 1);
    }
}

使用链表来实现堆栈：

public class Stack {
    private Node top;

    private class Node {
        int data;
        Node next;
    }

    public Stack() {
        top = null;
    }

    public void push(int element) {
        Node newNode = new Node();
        newNode.data = element;
        newNode.next = top;
        top = newNode;
    }

    public int pop() {
        int element = top.data;
        top = top.next;
        return element;
    }

    public int peek() {
        return top.data;
    }

    public boolean isEmpty() {
        return (top == null);
    }
}

二、队列

队列是一种基于先进先出（FIFO）原则的数据结构。这意味着，先被插入队列的元素最先被弹出。队列可以用于模拟实际生活中的排队场景。在Java中，我们可以使用数组或链表来实现队列。

使用数组来实现队列：

public class Queue {
    private int[] arr;
    private int front;
    private int rear;

    public Queue(int size) {
        arr = new int[size];
        front = -1;
        rear = -1;
    }

    public void enqueue(int element) {
        if (isEmpty()) {
            front = 0;
        }
        arr[++rear] = element;
    }

    public int dequeue() {
        int element = arr[front++];
        if (isEmpty()) {
            front = -1;
            rear = -1;
        }
        return element;
    }

    public boolean isEmpty() {
        return (front == -1 && rear == -1);
    }

    public boolean isFull() {
        return (rear == arr.length - 1);
    }
}

使用链表来实现队列：

public class Queue {
    private Node front, rear;

    private class Node {
        int data;
        Node next;
    }

    public Queue() {
        front = null;
        rear = null;
    }

    public void enqueue(int element) {
        Node newNode = new Node();
        newNode.data = element;
        newNode.next = null;
        if (isEmpty()) {
            front = newNode;
            rear = newNode;
            return;
        }
        rear.next = newNode;
        rear = newNode;
    }

    public int dequeue() {
        int element = front.data;
        front = front.next;
        if (front == null) {
            rear = null;
        }
        return element;
    }

    public boolean isEmpty() {
        return (front == null && rear == null);
    }
}

三、链表

链表是一种由节点组成的数据结构，每个节点都包含一个数据元素和一个指向下一个节点的指针。链表有单向链表、双向链表和循环链表等不同的形式。在Java中，我们可以使用类来定义这些不同类型的链表。

单向链表：

public class LinkedList {
    private Node head;

    private class Node {
        int data;
        Node next;
    }

    public LinkedList() {
        head = null;
    }

    public void add(int element) {
        Node newNode = new Node();
        newNode.data = element;
        newNode.next = null;
        if (head == null) {
            head = newNode;
            return;
        }
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = newNode;
    }

    public void delete(int element) {
        if (head == null) {
            return;
        }
        if (head.data == element) {
            head = head.next;
            return;
        }
        Node previous = head, current = head.next;
        while (current != null && current.data != element) {
            previous = current;
            current = current.next;
        }
        if (current != null) {
            previous.next = current.next;
        }
    }

    public void print() {
        Node node = head;
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
        System.out.println();
    }
}

双向链表：

public class DoublyLinkedList {
    private Node head;

    private class Node {
        int data;
        Node previous;
        Node next;
    }

    public DoublyLinkedList() {
        head = null;
    }

    public void add(int element) {
        Node newNode = new Node();
        newNode.data = element;
        newNode.previous = null;
        newNode.next = null;
        if (head == null) {
            head = newNode;
            return;
        }
        Node last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = newNode;
        newNode.previous = last;
    }

    public void delete(int element) {
        if (head == null) {
            return;
        }
        if (head.data == element) {
            if (head.next != null) {
                head.next.previous = null;
            }
            head = head.next;
            return;
        }
        Node current = head.next;
        while (current != null && current.data != element) {
            current = current.next;
        }
        if (current != null) {
            current.previous.next = current.next;
            if (current.next != null) {
                current.next.previous = current.previous;
            }
        }
    }

    public void print() {
        Node node = head;
        while (node != null) {
            System.out.print(node.data + " ");
            node = node.next;
        }
        System.out.println();
    }
}

循环链表：

public class CircularLinkedList {
    private Node head;

    private class Node {
        int data;
        Node next;
    }

    public CircularLinkedList() {
        head = null;
    }

    public void add(int element) {
        Node newNode = new Node();
        newNode.data = element;
        newNode.next = null;
        if (head == null) {
            head = newNode;
            head.next = head;
            return;
        }
        Node last = head;
        while (last.next != head) {
            last = last.next;
        }
        last.next = newNode;
        newNode.next = head;
    }

    public void delete(int element) {
        if (head == null) {
            return;
        }
        if (head.data == element) {
            Node last = head;
            while (last.next != head) {
                last = last.next;
            }
            last.next = head.next;
            head = head.next;
            return;
        }
        Node previous = head, current = head.next;
        while (current != head && current.data != element) {
            previous = current;
            current = current.next;
        }
        if (current != head) {
            previous.next = current.next;
        }
    }

    public void print() {
        if (head == null) {
            return;
        }
        Node node = head;
        do {
            System.out.print(node.data + " ");
            node = node.next;
        } while (node != head);
        System.out.println();
    }
}

总结：

在Java编程中，使用函数实现基本的数据结构非常简单。我们可以使用数组或链表来实现堆栈、队列