queue (用 java 简单实现)
queue
?
------
结构
?
线性存储，1个出口 & 1个入口，
first-in, first-out
?
------
操作
?
* insert (enqueue)
在入口处添加，
时间复杂度：O(1)
* delete (dequeue)
在出口处删除，
时间复杂度：O(1)
*?
?
------
实现方案：
?
用 Object[] 存贮数据，类采用泛型，
add() & remove() 方法，对数组进行操作，并用 synchronized 控制并发，
数组 小index 是 head,大index是tail,
插入在 tail 处,删除在 head 处,
?
用2个变量分别保存当前 下次 插入 & 删除 时的 index,
?
提供对数据长度的扩增方法，以保证数组长度够，
?
------
例子：
?
package eric.algrathem.struct.queue;import java.util.Arrays;import java.util.Collection;/** * <p> * structure for queue * </p> * <p> * 用1个数组存数据,数组 小index 是 head,大index是tail,<br /> * 插入在 tail 处,删除在 head 处, * </p> * * @author eric * @param <E> */public class QueueStruct<E> {/** 初始容量 */public static final int DEFAULT_SIZE = 10;/** 容量不足时翻倍数 */public static final float DEFAULT_INCREMENT = 1.5f;/** 数据 */private Object[] elementData;/** 元素个数 */private int elementCount;/** 数组的头部,即 下次删除数据的 index */private int head;/** 数组的尾部,即 下次插入数据的 index */private int tail;public QueueStruct() {this(DEFAULT_SIZE);}public QueueStruct(int size) {this.elementData = new Object[size];this.elementCount = 0;this.head = 0;this.tail = 0;}public QueueStruct(Object[] data) {this.elementData = data;this.elementCount = data.length;this.head = 0;this.tail = 0;}public QueueStruct(Collection<? extends E> c) {this(c.toArray());}/** * 添加数据 到尾部 * * @param ele * @return */public synchronized E add(E ele) {if (tail >= elementData.length) {adjustData();}elementData[tail] = ele;elementCount++;tail++;return ele;};/** * 删除数据 从头部 * * @return */@SuppressWarnings("unchecked")public synchronized E remove() {E e = (E) elementData[head];elementData[head] = null;elementCount--;head++;return e;};/** * 获得当前的数据 * * @return */public synchronized Object[] getData() {return Arrays.copyOfRange(this.elementData, this.head, this.tail);}public synchronized void adjustData() {if (tail >= elementData.length) { // tail 处空间不足时调用// head 的空位去掉int newSize = (elementData.length == elementCount) ? (int) Math.ceil(elementCount * DEFAULT_INCREMENT): elementData.length;elementData = Arrays.copyOfRange(elementData, head, elementData.length);// 调整空间elementData = Arrays.copyOf(elementData, newSize);tail = elementCount;head = 0;}}}?
package eric.algrathem.struct.queue;import junit.framework.Assert;import junit.framework.TestCase;import org.junit.Test;public class QueueStructTest extends TestCase {@Testpublic void test() {QueueStruct<Integer> queueOne = new QueueStruct<Integer>();// 第1次 加入个数int addCountOne = 30;// 第1次 删除个数int removeCountOne = 20;// 第2次 加入个数int addCountTwo = 10;for (int i = 0; i < addCountOne; i++) {queueOne.add(i);}Object[] data = queueOne.getData();for (int i = 0; i < data.length; i++) {Assert.assertTrue((Integer) data[i] == i);}for (int i = 0; i < removeCountOne; i++) {Assert.assertTrue(queueOne.remove() == i);}for (int i = 0; i < addCountTwo; i++) {queueOne.add(i * 10);}Object[] data2 = queueOne.getData();int baseCount = addCountOne - removeCountOne;for (int i = 0; i < addCountTwo; i++) {Assert.assertTrue((Integer) data2[baseCount + i] == i * 10);}}public static void main(String[] args) {new QueueStructTest().test();}}??
------