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

在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.
}
}

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

最新问答

相关标签