Java - 可循环队列
2020-12-13 01:55
标签：length spl 后端 through else queue ext first 调用 队列是一种特殊的线性表，是一种先进先出的数据结构。只允许在表的前端进行删除操作，在表的后端进行插入操作。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。 简单的循环队列实现比较容易，队头获取数据、队头弹出获取数据，队尾插入数据。下面来研究一下可以无限循环使用的队列。思路如下： 1、数据结构 int[] elements：底层采用数组实现，用来存储队列的所有元素； maxSize：数组最大容量； first：队头索引属性； size：队列有效元素的个数； 1，2，3，4，5 2、算法 这里采用最大容量为5的队列来说明，即maxSize设为5。 (1) 第一次使用队列时，依次添加5个元素：1，2，3，4，5，first指向1，size 大小为5，maxSize为5。 1，2，3，4，5 算法很简单：添加1时，各种为空、队列已满的判断条件暂时省掉； add(int value) { if (size == 0) { first = 0； } elements[size++] = value; } (2) 调用2次pop()方法弹出获取队列元素，此时队列数据结构如下： 1，2，3，4，5 size为3，first指向3，maxSize始终为5。 pop() { size--; return elements[first++]; } (3) 此时我们再向队列添加元素6、7，此时队列数据结构如下： 1，2，3，4，5 6，7，3，4，5 访问的顺序应该为：3, 4, 5, 6, 7，其中size为5，first指向3。此时步骤1、2的算法明显不支持数组的循环使用，我们需要利用取模来循环添加数据到数组，具体算法如下： Java - 可循环队列 标签：length spl 后端 through else queue ext first 调用 原文地址：https://www.cnblogs.com/Latiny/p/10759909.htmlpublic class MyQueue {
/**
* 底层数组
*/
private int[] elements;
/**
* 队列最大容量
*/
private int maxSize;
/**
* 队列头索引
*/
private int first;
/**
* 队列有效元素的个数
*/
private int size;
public MyQueue(int maxSize) {
this.maxSize = maxSize;
elements = new int[maxSize];
first = -1;
size = 0;
}
/**
* 添加元素
*
* @param value
*/
public void add(int value) {
if (isFull()) {
throw new RuntimeException("队列已满。");
}
if (isEmpty()) {
first = 0;
}
// 队列未满但是(first + size >= maxSize)时，说明数组elements的first索引之后所有位置已填满，
// first索引之前有空位置可以插入元素， 新增元素插入位置算法为：(first + size) % maxSize。
if (first + size >= maxSize) {
elements[(first + size) % maxSize] = value;
} else {
elements[first + size] = value;
}
size++;
}
/**
* 获取队列元素，只能取队列头，弹出式获取。
*
* @return
*/
public int pop() {
if (isEmpty()) {
throw new RuntimeException("队列为空。");
}
size--;
// first 索引指向maxSize - 1时，即first已到达数组最后的位置，则弹出之后需将first指向第1个元素，
// 实现数组循环使用
if (first == maxSize -1) {
int tmp = elements[first];
first = 0;
return tmp;
} else {
return elements[first++];
}
}
/**
* 获取元素，不弹出
*
* @return
*/
public int peek() {
if (isEmpty()) {
throw new RuntimeException("队列为空。");
}
return elements[first];
}
public boolean isFull() {
return size == maxSize;
}
public boolean isEmpty() {
return size ;
}
public void display() {
if (isEmpty()) {
System.out.println("Queue is empty.");
return;
}
StringBuilder str = new StringBuilder();
for (int i = first; i ) {
if (i >= maxSize) {
str.append(elements[i % maxSize] + ", ");
} else {
str.append(elements[i] + ", ");
}
}
System.out.println(str.substring(0, str.length() - 2));
}
public int size() {
return size;
}
}