java实现队列queue数据结构详解

109次阅读

没有评论

共计 1844 个字符，预计需要花费 5 分钟才能阅读完成。

在 Java 中，可以使用数组或者链表来实现队列数据结构。

使用数组实现队列

首先，创建一个固定大小的数组作为队列的容器。
声明两个指针，一个指向队列头部（front），一个指向队列尾部（rear）。
当插入一个元素时，将元素放入 rear 指针所指向的位置，并将 rear 指针向后移动一位。
当删除一个元素时，将 front 指针所指向的元素删除，并将 front 指针向后移动一位。
当队列为空时，front 和 rear 指针指向同一位置。

使用链表实现队列

首先，创建一个链表类，包含节点类和队列类。
节点类包含一个值和一个指向下一个节点的指针。
队列类包含一个指向头节点的指针和一个指向尾节点的指针。
当插入一个元素时，创建一个新节点，并将其放入尾节点的后面，并更新尾节点指针。
当删除一个元素时，将头节点删除，并更新头节点指针。
当队列为空时，头节点和尾节点指针为空。

以下是使用数组实现队列的示例代码：

public class Queue {
private int capacity; // 队列容量
private int[] data; // 存储队列元素的数组
private int front; // 队列头部指针
private int rear; // 队列尾部指针
public Queue(int capacity) {
this.capacity = capacity;
this.data = new int[capacity];
this.front = 0;
this.rear = -1;
}
public boolean isEmpty() {return (rear == -1);
}
public boolean isFull() {return (rear == capacity - 1);
}
public void enqueue(int item) {if (isFull()) {System.out.println("Queue is full, cannot enqueue item.");
return;
}
data[++rear] = item;
}
public int dequeue() {if (isEmpty()) {System.out.println("Queue is empty, cannot dequeue item.");
return -1;
}
int item = data[front++];
if (front > rear) {
front = 0;
rear = -1;
}
return item;
}
public int peek() {if (isEmpty()) {System.out.println("Queue is empty, cannot peek item.");
return -1;
}
return data[front];
}
}

使用示例：

public class Main {public static void main(String[] args) {Queue queue = new Queue(5);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
System.out.println(queue.dequeue()); // 输出 1
System.out.println(queue.peek()); // 输出 2
System.out.println(queue.isEmpty()); // 输出 false
System.out.println(queue.isFull()); // 输出 false
queue.enqueue(4);
queue.enqueue(5);
System.out.println(queue.isFull()); // 输出 true
queue.enqueue(6); // 输出 Queue is full, cannot enqueue item.
System.out.println(queue.dequeue()); // 输出 2
System.out.println(queue.dequeue()); // 输出 3
System.out.println(queue.dequeue()); // 输出 4
System.out.println(queue.dequeue()); // 输出 5
System.out.println(queue.isEmpty()); // 输出 true
System.out.println(queue.peek()); // 输出 Queue is empty, cannot peek item.
}
}

以上是使用数组实现队列的详细解释和示例代码。你也可以尝试使用链表来实现队列数据结构。

丸趣 TV 网 – 提供最优质的资源集合！

正文完