五华区网站/google学术搜索
关于自定义循环队列的实现原理和要点可以参见之前的博文系列：循环队列及C语言实现。这里主要对JAVA下的具体实现方式与原理进行说明。
一、JAVA 中已经自带了 Queue、DQueue、ArrayList、LinkedList 等常用的数据结构，为什么还要单独实现循环队列？
之所以使用自定义循环队列，出发点还是基于我们在实际应用中对于数据处理各种各样的需求。使用自定义数据结构的好处就在于可以更加灵活的处理各种数据，增加自己需要的接口。然而弊端就是你的 code 可能会引入各种未知的 Bug。所以，在满足我们使用前提的场景下，使用上述已有数据结构等是比较推荐的，如果满足不了实际项目需求，再通过自定义的方式等实现是我们理想的一种选择。
二、什么场景需要使用自定义循环队列？
对于数据的处理要求比较灵活，比如：我们需要开发一个安卓服务器程序，需要不断处理每个客户端的请求以及完成与客户端的交互。发送来的数据需要及时处理，但同时数据以自定义格式进行传输：包头+长度+数据+包尾+校验。如上格式，服务器端需要不断将接收的数据进行缓存与解析，如果未满一帧那么需要缓存到下次数据接收过来再进行解析。这时，我们需要批量从队列读取数据以及如果一帧数据不完全，将读取的数据复原到队列中(更改队列当前读位置)的功能。此时，就可以考虑自己实现队列满足这些特殊的需求。
三、循环队列的特点与要素
1、先进先出(FIFO)；
2、队列首尾元素位置；
3、常用队列操作：初始化、销毁、遍历、读写等；
四、源码实现
为便于使用，这里将该循环队列以类的方式实现：
/*
* Copyright (c) 2017, SoldierJazz. All rights reserved.
* Use is subject to license terms.
*
*/
package com.exmple.java.text;
/**
* DataQueue 类实现为FIFO循环队列
*
*
使用前需要根据实际需求为队列分配合理的队列空间大小
*
* 创建一个4K空间的队列如下所示：
*
* DataQueue mdataqueue= new DataQueue(4096);
*
*
更多使用信息可以参考引用该类的例程，有关问题，可发送到
* SoldierJazz@163.com 寻求支持。
*
* @author SoldierJazz
* @version 1.0.0
*/
public class DataQueue {
Queue q = null;
public class Queue {
byte[] data = null;
int read;
int write;
int size;
int space;
}
Object mSemaphore = new Object();
DataQueue(int size) {
q = new Queue();
Queue_Init(q, size);
}
/**
* 返回当前队列可用数据量
*
* @param q 目标队列
*
*/
int Avail(Queue q) {
return q.size - q.space;
}
/**
* 初始化队列
*
* @param q 目标队列
*
* @param size 队列分配内存大小
*
*/
void Queue_Init(Queue q, int size) {
synchronized (mSemaphore) {
q.data = new byte[size];
q.read = 0;
q.write = 0;
q.size = size;
q.space = size;
}
}
/**
* 销毁队列
*
* @param q 目标队列
*
*/
void Queue_Destroy(Queue q) {
synchronized (mSemaphore) {
q.read = q.write = 0;
q.space = q.size;
}
}
/**
* 判断当前队列是否为空
*
* @param q 目标队列
*
* @return true表示队列为空
false表示队列不为空
*
*/
boolean Queue_Empty(Queue q) {
return (q.space == q.size);
}
/**
* 判断当前队列是否已满
*
* @param q 目标队列
*
* @return true表示队列已满
false表示队列未满
*
*/
boolean Queue_Full(Queue q) {
return (q.space == 0);
}
/**
* 写一个byte到目标队列
*
* @param q 目标队列
*
* @param val 写入的byte值
*
* @return true表示写入成功
false表示写入失败
*
*/
boolean AddQueue(Queue q, byte val) {
if (!Queue_Full(q)) {
q.data[q.write] = val;
q.write = (q.write + 1) % q.size;
q.space--;
return true;
}
return false;
}
/**
* 从队列中读取一个字节
*
* @param q 目标队列
*
* @param data 读取的字节
*
* @return true表示读取成功
false表示读取失败
*
*/
boolean DelQueue(Queue q, Byte data) {
if (!Queue_Empty(q)) {
data = q.data[q.read];
q.read = (q.read + 1) % q.size;
q.space++;
return true;
}
return false;
}
/**
* 批量写入长度为len的字节到队列
*
* @param q 目标队列
*
* @param data 写入的byte数组
*
* @param len 写入的数组长度
*
* @return 成功写入的字节数量
*
*/
int WriteQueue(Queue q, byte[] data, int len)
{
int ret = 0;
int rest = q.size - q.write;
synchronized (mSemaphore) {
if (!Queue_Full(q)) {
if (q.space >= len) {
ret = len;
if (rest >= len) {
System.arraycopy(data, 0, q.data, q.write, len);
q.write = (q.write + len) % q.size;
q.space -= len;
} else {
System.arraycopy(data, 0, q.data, q.write, rest);
q.write = 0;
System.arraycopy(data, rest, q.data, 0, len - rest);
q.write = len -rest;
q.space -= len;
}
} else {
ret = q.space;
if (rest >= q.space) {
System.arraycopy(data, 0, q.data, q.write, q.space);
q.write = (q.write + q.space) % q.size;
q.space = 0;
} else {
System.arraycopy(data, 0, q.data, q.write, rest);
q.write = 0;
System.arraycopy(data, rest, q.data, 0, q.space - rest);
q.write = q.space -rest;
q.space = 0;
}
}
}
return ret;
}
}
/**
* 从队列中恢复长度len个字节的数据
*
* @param q 目标队列
*
* @param len 要恢复的长度
*
* @return 成功恢复的字节数
*
*/
int RecoverReadQueue(Queue q, int len) {
int ret = 0;
int rest = q.read;
synchronized (mSemaphore) {
if (q.space >= len)
ret = len;
else
ret = q.space;
if (rest >= ret) {
q.read -= ret;
} else {
q.read = q.size - (ret - rest);
}
q.space -= ret;
return ret;
}
}
/**
* 从队列中读取len个字节数据到data数组中
*
* @param q 目标队列
*
* @param data 用于存放数据的目标数组
*
* @param start 拷贝至目标数组的起始位置
*
* @param len 读取的长度
*
* @return 成功读取的字节数
*
*/
int ReadQueue(Queue q, byte[] data, int start, int len) {
int rest = q.size - q.read;
int ret = 0;
synchronized (mSemaphore) {
if (!Queue_Empty(q)) {
if (Avail(q) >= len) {
ret = len;
if (rest >= len) {
System.arraycopy(q.data, q.read, data, start, len);
q.read = (q.read + len) % q.size;
q.space += len;
} else {
System.arraycopy(q.data, q.read, data, start, rest);
q.read = 0;
System.arraycopy(q.data, 0, data, start + rest, len - rest);
q.read = len -rest;
q.space += len;
}
return len;
} else {
ret = Avail(q);
if (rest >= Avail(q)) {
System.arraycopy(q.data, q.read, data, start, Avail(q));
q.read = (q.read + Avail(q)) % q.size;
q.space = q.size;
} else {
System.arraycopy(q.data, q.read, data, start, rest);
q.read = 0;
System.arraycopy(q.data, 0, data, start + rest, Avail(q) - rest);
q.read = Avail(q) -rest;
q.space = q.size;
}
}
}
return ret;
}
}
}以上内容为使用该类及相关方法的定义，比较简单，看注解即可。下面针对该类做一个使用与测试程序：
public void TestDataQueue() {
DataQueue dataq = new DataQueue(100);
byte[] a1 = {1, 2, 3, 4, 5, 6};
byte[] a2 = {7, 8, 9, 10};
byte[] b = new byte[10];
int nread = 0;
dataq.WriteQueue(dataq.q, a1, a1.length);
nread = dataq.ReadQueue(dataq.q, b, 0, 3);
System.out.println("length of queue: " + dataq.Avail(dataq.q));
for (int i = 0; i < nread; i++) {
System.out.printf("byte[%d]: %d\n", i, b[i]);
}
dataq.WriteQueue(dataq.q, a2, a2.length);
System.out.println("length of queue: " + dataq.Avail(dataq.q));
nread = dataq.ReadQueue(dataq.q, b, 0, dataq.Avail(dataq.q));
System.out.println("length of queue: " + dataq.Avail(dataq.q));
for (int i = 0; i < nread; i++) {
System.out.printf("byte[%d]: %d\n", i, b[i]);
}
}
public static void main(String args[]) {
test t = new test();
t.TestDataQueue();
}运行结果如下所示：
有疑问或者问题就给我邮件或者评论吧，觉得有用就点赞吧~:-D