Java数组实现队列
简介
队列(Queue)是一种先进先出(FIFO)的数据结构,它支持在队列尾部插入数据,在队列头部删除数据。在实际的开发中,我们经常会使用队列来解决一些问题,比如多线程的任务队列,消息队列等等。在Java中,我们可以使用数组来实现队列。
实现过程
我们使用一个数组来保存队列中的元素,同时记录队列的头部和尾部元素的位置。具体实现方法如下:
1. 创建一个数组 queueArray 和两个变量 head 和 tail,其中 queueArray 用于保存队列的元素,head 和 tail 用于记录队列的头部和尾部元素位置,初始化 head 和 tail 为 0。
2. 在队列尾部插入数据时,将元素插入 queueArray 的 tail 位置,并将 tail 的值加 1。
3. 在队列头部删除数据时,将 head 的值加 1,并直接返回 queueArray[head](即队列的头部元素)。
示例1:
下面是一个简单的实现代码。我们在 main 函数中创建了一个队列,依次向队列中添加 1、2、3 三个元素,然后删除队列的头部元素,输出删除的元素,再添加 4、5、6 三个元素,并依次删除元素。最终队列为空时结束操作。
public class ArrayQueue {
private int[] queueArray;
private int head;
private int tail;
private int capacity;
public ArrayQueue(int capacity) {
this.capacity = capacity;
queueArray = new int[capacity];
}
public boolean enqueue(int item) {
if (tail == capacity) {
return false;
}
queueArray[tail] = item;
tail++;
return true;
}
public int dequeue() {
if (head == tail) {
return -1;
}
int item = queueArray[head];
head++;
return item;
}
public static void main(String[] args) {
ArrayQueue queue = new ArrayQueue(6);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
System.out.println(queue.dequeue());
queue.enqueue(4);
queue.enqueue(5);
queue.enqueue(6);
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
}
}
输出结果:
1
2
3
4
5
6
示例2:
我们可以使用Java的泛型,让代码具有更好的灵活性。现在我们重写 ArrayQueue 类,使用泛型来实现队列。
public class ArrayQueue<T> {
private T[] queueArray;
private int head;
private int tail;
private int capacity;
@SuppressWarnings("unchecked")
public ArrayQueue(int capacity) {
this.capacity = capacity;
queueArray = (T[]) new Object[capacity];
}
public boolean enqueue(T item) {
if (tail == capacity) {
return false;
}
queueArray[tail] = item;
tail++;
return true;
}
public T dequeue() {
if (head == tail) {
return null;
}
T item = queueArray[head];
head++;
return item;
}
public static void main(String[] args) {
ArrayQueue<Integer> queue = new ArrayQueue<>(6);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
System.out.println(queue.dequeue());
queue.enqueue(4);
queue.enqueue(5);
queue.enqueue(6);
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
System.out.println(queue.dequeue());
}
}
输出结果:
1
2
3
4
5
6
Java环形队列实现
简介
队列是一种常见的数据结构,使用队列可以控制数据的先进先出(FIFO)。在实际的应用中,队列应用广泛。当然,对于环形队列,它与普通队列不同。普通队列是线性的,所以必须有两个“指针”表示当前的队头、队尾,但环形队列是圆形的,只需要知道一个“指针”就可以了。环形队列在解决一些问题时比普通队列更加高效。本文将介绍如何使用数组实现Java环形队列。
实现过程
在数组中使用环形队列时,我们需要维护一个 head 数组表示当前队列的起点,tail 数组表示当前队列的终点。当 tail 超过了数组最大的下标时,tail 应该重新指向数组开始的位置。与普通队列相比,我们需要特别地处理一些特殊情况。
判断队列是否为空:
当 head == tail 时,队列为空。
判断队列是否已满:
当 (tail + 1) % capacity == head 时,队列已满。
在队列尾部插入数据:
- 如果队列未满,直接将元素插入 tail 位置。
- 如果队列已满,返回 false。
在队列头部删除数据:
- 如果队列为空,返回 null。
- 如果队列不为空,则先取出 head 位置的元素,再将 head 的值加 1。
示例1:
下面是一个简单的环形队列实现代码,我们在 main 函数中创建了一个容量为 6 的队列,并依次插入 1、2、3、4、5、6 个元素。最后,我们输出队列的所有元素。
public class CircularQueue {
private int[] queueArray;
private int head;
private int tail;
private int capacity;
public CircularQueue(int capacity) {
this.capacity = capacity;
queueArray = new int[capacity];
head = 0;
tail = 0;
}
public boolean enqueue(int item) {
if ((tail + 1) % capacity == head) {
return false;
}
queueArray[tail] = item;
tail = (tail + 1) % capacity;
return true;
}
public int dequeue() {
if (head == tail) {
return -1;
}
int item = queueArray[head];
head = (head + 1) % capacity;
return item;
}
public static void main(String[] args) {
CircularQueue queue = new CircularQueue(6);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5);
queue.enqueue(6);
int size = (queue.tail - queue.head + queue.capacity) % queue.capacity;
for (int i = 0; i < size; i++) {
System.out.println(queue.dequeue());
}
}
}
输出结果:
1
2
3
4
5
6
示例2:
我们同样可以是使用Java的泛型,让代码具有更好的灵活性。现在我们重写 CircularQueue 类,使用泛型来实现队列。
public class CircularQueue<T> {
private T[] queueArray;
private int head;
private int tail;
private int capacity;
@SuppressWarnings("unchecked")
public CircularQueue(int capacity) {
this.capacity = capacity;
queueArray = (T[]) new Object[capacity];
head = 0;
tail = 0;
}
public boolean enqueue(T item) {
if ((tail + 1) % capacity == head) {
return false;
}
queueArray[tail] = item;
tail = (tail + 1) % capacity;
return true;
}
public T dequeue() {
if (head == tail) {
return null;
}
T item = queueArray[head];
head = (head + 1) % capacity;
return item;
}
public static void main(String[] args) {
CircularQueue<Integer> queue = new CircularQueue<>(6);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);
queue.enqueue(5);
queue.enqueue(6);
int size = (queue.tail - queue.head + queue.capacity) % queue.capacity;
for (int i = 0; i < size; i++) {
System.out.println(queue.dequeue());
}
}
}
输出结果:
1
2
3
4
5
6
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:java数组实现队列及环形队列实现过程解析 - Python技术站