数据结构在Java中实现：链表、队列问题

原创阳光穿透心脏的1/2处 2024-12-06 16:09 6阅读 0赞

在Java中，我们可以使用类来实现各种数据结构，如链表和队列。

1. 链表（Linked List）：
   - 链表节点（Node）通常包含值、指向下一个节点的引用。
   ```java
   // Node class
   public class Node {
       int data; // Value of node
       Node next; // Pointer to next node

// Constructor for Node class
       Node(int item) {
           data = item;
           next = null;
       }
   }
   
   // LinkedList class with insert, delete and print methods
   public class LinkedList {
       Node head; // Pointer to first node of list

// Method to insert a new node at the beginning of the list
       void insert(int data) {
           Node newNode = new Node(data); // Create new node

if (head == null) { // If list is empty
               head = newNode;
               return;
           } else { // If list already has some nodes
               newNode.next = head; // Connect new node with head node
               head = newNode; // Update head pointer to the new head node
           }
       }

// Method to delete a node from the beginning of the list
       void delete(int data) {
           if (head == null) { // If list is empty
               System.out.println("List is empty, cannot delete.");
               return;
           } else { // If list already has some nodes
               Node current = head; // Initialize current node pointer to head

// Search for the node with given data
               while (current != null && current.data != data) {
                   current = current.next; // Move to next node
               }

if (current == null) { // If node with given data is not found in list
                   System.out.println("Node with given data is not found.");
                   return;
               } else { // If node with given data is found in list

// If the current node is the head of the list, update head pointer
                   if (current == head) {
                       head = current.next; // Update head to next node
                   }

// Delete the node from the list
                   current.next = current.next.next; // Point next node to node after deleted node

System.out.println("Node with data " + current.data + " is deleted.");
               }
           }
       }

// Method to print all nodes of the linked list
       void printList() {
           Node temp = head; // Initialize temporary pointer to head

while (temp != null) {
               System.out.print(temp.data + " -> "); // Print node data with arrow separator
               temp = temp.next;
           }

System.out.println("Tail of list -> NULL")); // Print tail node as NULL
       }
   }
```

2. 队列（Queue）：
队列在Java中可以使用`PriorityQueue`或自定义实现。这里以自定义实现一个基本的非循环队列为例：

```java
import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    private Queue<Integer> queue = new LinkedList<>();

// 添加元素到队尾
    public void enqueue(int data) {
        queue.add(data);
    }

// 从队头移除元素
    public int dequeue() {
        if (queue.isEmpty()) {
            System.out.println("Queue is empty, cannot dequeue.");
            return -1;
        }
        return queue.remove();
    }

// 检查队列是否为空
    public boolean isEmpty() {
        return queue.isEmpty();
    }

// 获取队列的大小（元素数量）
    public int size() {
        return queue.size();
    }
}
```

以上代码实现了一个基本的非循环队列，包括插入元素（enqueue）、移除并返回元素（dequeue）、检查队列是否为空（isEmpty）以及获取队列大小（size）等功能。