使用Java函数模拟常见数据结构

数据结构是计算机科学中一个重要的概念，其涉及的领域非常广泛，包括排序、搜索、图形处理等多个方面。而在Java语言中，通过函数模拟常见数据结构可以帮助我们更好地理解和应用各种算法。

在Java中函数模拟数据结构通常使用类来实现，下面将分别介绍常见的几种数据结构，以及相应的Java函数实现。

1. 数组

数组是一种线性结构，其元素类型相同，通过整数作为下标可以访问到其中的元素。在Java中，数组通过指定数据类型和数组长度来定义，并且可以使用循环语句来进行遍历操作。

例如，以下是一个长度为5的整数数组，其中包含了多个随机数。

int[] arr = new int[5];
for (int i = 0; i < arr.length; i++) {
  arr[i] = (int) (Math.random() * 100);
}

2. 栈

栈是一种基于后进先出（LIFO）原则的数据结构，因此常用于计算机行业中的操作系统、编译器等领域。在Java中，栈通常通过数组或链表来实现。

以下是基于数组实现的栈实例，主要包含了如下几个方法：

- push：将元素压入栈顶

- pop：将栈顶元素弹出

- peek：获取栈顶元素但不将其弹出

- isEmpty：判断栈是否为空

- isFull：判断栈是否已满

class Stack {
  int size;
  int top;
  int[] arr;

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

  void push(int data) {
    if (isFull()) {
      System.out.println("Stack is full.");
      return;
    }
    top++;
    arr[top] = data;
  }

  int pop() {
    if (isEmpty()) {
      System.out.println("Stack is empty.");
      return -1;
    }
    int data = arr[top];
    top--;
    return data;
  }

  int peek() {
    if (isEmpty()) {
      System.out.println("Stack is empty.");
      return -1;
    }
    return arr[top];
  }

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

  boolean isFull() {
    return top == size - 1;
  }
}

3. 队列

队列是一种基于先进先出（FIFO）原则的数据结构，其通常包含了入队、出队、队首元素和队列长度等方法。在Java中，队列通常通过数组或链表来实现。

以下是基于链表实现的队列实例，主要包含了如下几个方法：

- enqueue：将元素加入队列尾部

- dequeue：将队首元素出队

- peek：获取队首元素但不将其出队

- isEmpty：判断队列是否为空

- size：获取队列长度

class Queue {
  static class Node {
    int data;
    Node next;

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

  Node front, rear;

  Queue() {
    this.front = this.rear = null;
  }

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

  int dequeue() {
    if (isEmpty()) {
      System.out.println("Queue is empty.");
      return -1;
    }
    int data = front.data;
    front = front.next;
    if (front == null) {
      rear = null;
    }
    return data;
  }

  int peek() {
    if (isEmpty()) {
      System.out.println("Queue is empty.");
      return -1;
    }
    return front.data;
  }

  boolean isEmpty() {
    return front == null;
  }

  int size() {
    int count = 0;
    Node curr = front;
    while (curr != null) {
      count++;
      curr = curr.next;
    }
    return count;
  }
}

4. 链表

链表是一种基于节点连接构成的数据结构，内部可以存储各种类型的数据。在Java中，链表通常使用Node或者自定义类来实现，并且有单向链表和双向链表两种形式。

以下是基于Node类实现的单向链表实例，主要包含了如下几个方法：

- add：将元素添加到链表末尾

- insertAt：在指定位置插入元素

- delete：删除指定元素

- search：查找指定元素

- printList：打印链表元素

class LinkedList {
  static class Node {
    int data;
    Node next;

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

  Node head;

  LinkedList() {
    this.head = null;
  }

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

  void insertAt(int pos, int data) {
    Node newNode = new Node(data);
    if (pos == 0) {
      newNode.next = head;
      head = newNode;
      return;
    }
    Node curr = head;
    for (int i = 0; i < pos - 1 && curr != null; i++) {
      curr = curr.next;
    }
    if (curr == null) {
      System.out.println("Invalid position");
      return;
    }
    newNode.next = curr.next;
    curr.next = newNode;
  }

  void delete(int data) {
    Node curr = head;
    Node prev = null;
    if (curr != null && curr.data == data) {
      head = curr.next;
      return;
    }
    while (curr != null && curr.data != data) {
      prev = curr;
      curr = curr.next;
    }
    if (curr == null) {
      System.out.println("Element not found.");
      return;
    }
    prev.next = curr.next;
  }

  Node search(int data) {
    Node curr = head;
    while (curr != null && curr.data != data) {
      curr = curr.next;
    }
    if (curr == null) {
      System.out.println("Element not found.");
      return null;
    }
    return curr;
  }

  void printList() {
    Node curr = head;
    System.out.print("LinkedList: ");
    while (curr != null) {
      System.out.print(curr.data + " ");
      curr = curr.next;
    }
  }
}

总之，采用Java函数模拟常见数据结构可以帮助我们更好地理解和应用算法，提高编程效率和代码可读性。