数据结构实现难题：使用Java实现堆栈和队列？

原创淩亂°似流年 2024-11-22 04:57 32阅读 0赞

在Java中，我们可以使用数组或链表来实现堆栈和队列。这里我将分别解释这两种数据结构的Java实现。

1. 堆栈（Stack）：

- 数组实现：
```java
class Stack {
    int[] arr;
    int top;

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

// 入栈操作
    void push(int item) {
        if (top == arr.length - 1) {
            System.out.println("Stack overflow!");
            return;
        }
        arr[++top] = item;
    }

// 出栈操作（获取堆栈顶元素）
    int pop() {
        if (top == -1) {
            System.out.println("Stack underflow!");
            return -1;
        }
        int item = arr[top--];
        return item;
    }

// 检查栈是否为空
    boolean isEmpty() {
        return top == -1;
    }
}
```
- 链表实现（链表节点结构为：`Node(int data) { this.data = data; }`）：
```java
class Stack {
    Node stack;

Stack() {
        stack = new Node(0); // 创建一个空的堆栈
    }

// 入栈操作
    void push(int item) {
        stack.next = new Node(item);
        stack = stack.next;
    }

// 出栈操作（获取堆栈顶元素）
    int pop() {
        if (stack == null || stack.next == null) {
            System.out.println("Stack underflow!");
            return -1;
        }
        int item = stack.next.data;
        stack.next = stack.next.next; // 删除节点
        return item;
    }

// 检查栈是否为空
    boolean isEmpty() {
        return stack == null || stack.next == null;
    }
}
```
2. 队列（Queue）：

- 数组实现：
```java
class Queue {
    int[] arr;
    int front, rear;

Queue(int size) {
        arr = new int[size];
        front = 0;
        rear = -1; // 初始值设为-1，避免直接使用arr.length - 1
    }

// 入队操作
    void enqueue(int item) {
        if (rear == arr.length - 1) { // 队列已满
            System.out.println("Queue overflow!");
            return;
        }
        arr[++rear] = item; // 将元素添加到数组的末尾
    }

// 出队操作（获取队列首元素）
    int dequeue() {
        if (front == rear) { // 队列为空
            System.out.println("Queue underflow!");
            return -1;
        }
        int item = arr[front++];
        if (front >= rear + 1) { // 如果第一个出队的元素后不再有任何元素，则需要重新填充数组
            for (int i = rear + 2; i < arr.length; i++) {
                arr[i] = 0;
            }
            front = 0;
            rear = -1; // 初始值设为-1，避免直接使用arr.length - 1
        }
        return item;
    }

// 检查队列是否为空
    boolean isEmpty() {
        return front == rear;
    }

// 获取队列的长度
    int size() {
        return rear - front + 1;
    }
}
```
- 链表实现（链表节点结构为：`Node(int data) { this.data = data; }`）：
```java
class Queue {
    Node queue;

Queue() {
        queue = new Node(0); // 创建一个空的队列
    }

// 入队操作
    void enqueue(int item) {
        queue.next = new Node(item);
        queue = queue.next;
    }

// 出队操作（获取队列首元素）
    int dequeue() {
        if (queue == null || queue.next == null) { // 队列为空
            System.out.println("Queue underflow!");
            return -1;
        }
        int item = queue.next.data;
        queue.next = queue.next.next; // 删除节点
        queue = queue.next; // 更新队列头部
        return item;
    }

// 检查队列是否为空
    boolean isEmpty() {
        return queue == null || queue.next == null;
    }

// 获取队列的长度
    int size() {
        Node temp = queue;
        int count = 1; // 起始计数为1，因为数组起始位置是0

while (temp != null) { // 遍历链表
            temp = temp.next;
            if (count % 2 == 1) { // 如果当前节点是奇数位（从0开始的奇数）
                count++; // 计数加一
            }
        }

return count; // 返回队列长度
    }
}
```
以上代码实现了使用数组和链表两种数据结构实现的堆栈和队列。你可以根据需要选择使用哪种数据结构。