数据结构在Java中的实现：链表、栈和队列

原创向右看齐 2024-10-16 11:36 68阅读 0赞

在Java中，我们可以使用类（Class）来实现各种数据结构。下面分别介绍链表、栈和队列的Java实现：

1. 链表（LinkedList）
- 创建一个Node类，包含值和下一个节点的引用。
```java
class Node {
    int data;
    Node next;

// Constructor
    Node(int item) {
        data = item;
        next = null;
    }
}
```
- 在LinkedList类中，维护链表头部（头节点）和尾部（尾节点）的信息。
```java
class LinkedList {
    Node head;  // Head of the list

// Constructor
    LinkedList() {
        head = null;
    }

// Insert at beginning
    void push(int new_data) {
        Node newNode = new Node(new_data);

if (head == null) {  // If list is empty
            head = newNode;
        } else {
            newNode.next = head;  // Connect new node with the first one
            head = newNode;  // Update head pointer
        }
    }

// Display linked list
    void display() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
    }
}
```
2. 栈（Stack）
- 在Java中，我们可以使用`java.util.Stack`类来实现栈。
```java
import java.util.Stack;

class StackExample {
    // Push an item onto the stack
    void push(int value) {
        Stack<Integer> stack = new Stack<>();  // Create a stack
        stack.push(value);  // Add value to stack
    }

// Pop an item off the top of the stack
    int pop() {
        Stack<Integer> stack = new Stack<>();  // Get reference to stack
        if (stack.isEmpty()) {  // If stack is empty
            return -1;  // Return error code
        } else {
            return stack.pop();  // Pop the top element and return it
        }
    }

// Display the contents of the stack
    void displayStack() {
        Stack<Integer> stack = new Stack<>();  // Get reference to stack
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
    }
}
```
3. 队列（Queue）
- Java中提供了一个`java.util.Queue`接口，它继承了`java.util.List`接口。常见的实现有`ArrayDeque`和`LinkedList`。
```java
import java.util.Deque;
import java.util.LinkedList;

class QueueExample {
    // Create a queue using LinkedList implementation
    Deque<Integer> createQueue() {
        Deque<Integer> queue = new LinkedList<>();  // Create a deque as a queue
        return queue;
    }

// enqueue an item into the queue
    void enqueue(int value) {
        Deque<Integer> queue = createQueue();  // Get reference to queue
        queue.addLast(value);  // Enqueue value at the rear of the queue
    }

// dequeue an item from the front of the queue
    int dequeue() {
        Deque<Integer> queue = createQueue();  // Get reference to queue
        if (queue.isEmpty()) {  // If queue is empty
            return -1;  // Return error code
        } else {
            int poppedValue = queue.removeFirst();  // Dequeue and remove the front element from the queue
            return poppedValue;
        }
    }

// Display the contents of the queue
    void displayQueue() {
        Deque<Integer> queue = createQueue();  // Get reference to queue
        while (!queue.isEmpty()) {
            System.out.println(queue.removeFirst());
        }
    }
}
```
以上就是链表、栈和队列在Java中的实现。