数据结构:队列的java实现以及优化
程序员文章站
2022-03-31 10:08:13
...
队列
队列是一种先进先出,后进后出的数据结构。
如果用数组的基本数据结构实现的话,普通的队列只能入列的元素数量为数组的大小,不管是否已经出列。
/**
* 队列:先入先出,后入后出
* 最多只能入列maxSize个元素,不管是否已经出列
*/
public class Queue {
private int maxSize; // 队列的最大容量
private int first = -1; // 第一个成员的index
private int last = 0; // 最后一个成员的index +1
private String[] arr;
public Queue(int maxSize){
this.maxSize = maxSize;
arr = new String[maxSize];
}
public String take(){
if (first+1 == last){
System.out.println("队列为空,无法出列");
return null;
}
first ++;
String e = arr[first];
return e;
}
public void add(String e){
if (last == maxSize){
System.out.println("队列已满,无法添加");
return;
}
arr[last] = e;
last ++;
}
}
环形队列
基于上面说到的普通队列的缺点,我们可以进行优化——环形队列,让队列可以同时存在数组大小的元素数量,不管之前是否已经出列。
/**
* 环形队列:在队列可以同时存在maxSize个元素,不管之前已经出列了多少元素
*/
public class CycleQueue {
private int maxSize; // 队列的最大容量
private int first = -1; // 第一个成员的index
private int last = 0; // 最后一个成员的index +1
private String[] arr;
public CycleQueue(int maxSize){
this.maxSize = maxSize;
arr = new String[maxSize];
}
public void add(String e){
if (last-first == maxSize+1){
System.out.println("队列已满,无法添加");
return;
}
arr[last%maxSize] = e;
last ++;
}
public String take(){
if (first == last-1){
System.out.println("队列为空,无法出列");
return null;
}
first ++;
String e = arr[first%maxSize];
return e;
}
}
测试
测试代码如下:
public class Test {
public static void main(String[] args) {
System.out.println("====普通队列测试");
queueTest();
System.out.println("====环形队列测试");
cycleQueueTest();
}
public static void queueTest(){
Queue queue = new Queue(10);
queue.add("a");
queue.add("b");
queue.add("c");
System.out.println(queue.take());
System.out.println(queue.take());
queue.add("d");
System.out.println(queue.take());
System.out.println(queue.take());
}
public static void cycleQueueTest(){
CycleQueue cycleQueue = new CycleQueue(2);
cycleQueue.add("a");
cycleQueue.add("b");
System.out.println(cycleQueue.take());
System.out.println(cycleQueue.take());
cycleQueue.add("c");
cycleQueue.add("d");
cycleQueue.add("e");
System.out.println(cycleQueue.take());
System.out.println(cycleQueue.take());
}
}
完整代码的已上传至GitHub