在某些时候，我们不能被要求像数组一样可以使用索引随机访问，而是需要被限制顺序处理业务，今天介绍一种先进先出（FIFO）的线性数据结构：队列，
当然，还有后进先出（LIFO）的处理方式，即为栈(后续有时间再另说)。
先进先出的数据结构：(以下图片非原创，来自网络)
在 FIFO 数据结构中，将首先处理添加到队列中的第一个元素。
如上图所示，队列是典型的 FIFO 数据结构。插入（insert）操作也称作入队（enqueue），新元素始终被添加在队列的末尾。 删除（delete）操作也被称为出队（dequeue)。 你只能移除第一个元素。
低效的队列实现：(此小段内容非原创，来自网络)
为了实现队列，我们可以使用动态数组和指向队列头部的索引。
如上所述，队列应支持两种操作：入队和出队。入队会向队列追加一个新元素，而出队会删除第一个元素。 所以我们需要一个索引来指出起点。
这是一个供你参考的实现：
// "static void main" must be defined in a public class.
class MyQueue {
// store elements
private List<Integer> data;
// a pointer to indicate the start position
private int p_start;
public MyQueue() {
data = new ArrayList<Integer>();
p_start = 0;
}
/** Insert an element into the queue. Return true if the operation is successful. */
public boolean enQueue(int x) {
data.add(x);
return true;
};
/** Delete an element from the queue. Return true if the operation is successful. */
public boolean deQueue() {
if (isEmpty() == true) {
return false;
}
p_start++;
return true;
}
/** Get the front item from the queue. */
public int Front() {
return data.get(p_start);
}
/** Checks whether the queue is empty or not. */
public boolean isEmpty() {
return p_start >= data.size();
}
};
public class Main {
public static void main(String[] args) {
MyQueue q = new MyQueue();
q.enQueue(5);
q.enQueue(3);
if (q.isEmpty() == false) {
System.out.println(q.Front());
}
q.deQueue();
if (q.isEmpty() == false) {
System.out.println(q.Front());
}
q.deQueue();
if (q.isEmpty() == false) {
System.out.println(q.Front());
}
}
}
缺点
上面的实现很简单，但在某些情况下效率很低。 随着起始指针的移动，浪费了越来越多的空间。 当我们有空间限制时，这将是难以接受的。
让我们考虑一种情况，即我们只能分配一个最大长度为 5 的数组。当我们只添加少于 5 个元素时，我们的解决方案很有效。 例如，如果我们只调用入队函数四次后还想要将元素 10 入队，那么我们可以成功。
但是我们不能接受更多的入队请求，这是合理的，因为现在队列已经满了。但是如果我们将一个元素出队呢？
实际上，在这种情况下，我们应该能够再接受一个元素。
循环队列的实现（原创）
上面我们提供了一种简单但低效的队列实现。
更有效的方法是使用循环队列。 具体来说，我们可以使用固定大小的数组和两个指针来指示起始位置（head）和结束位置(tail)。 目的是重用我们之前提到的被浪费的存储。
循环队列的实现最为关键是要用检测队列空（empty）与满(full)的策略，以下附上原码和输出结果。
1、抽象了一个队列的简单接口（ICircleQueue）
package com.chengcai.util;
/**
* Created by chengcai on 2019/3/7.
*/
public interface ICircleQueue<E> {
boolean enQueue(E e); E deQueue(); boolean isFull(); boolean isEmpty(); CircleQueueEntity getQueueEntity(); int getQueueItemSize(); int getRequestElementIndex(); }
2.抽像类（AbstractComDataSet），暂作了定义队列长度，留个扩展
public abstract class AbstractComDataSet {
static int QueueBufferSize=10;
}
3.队列属性类（CircleQueueEntity）
package com.chengcai.util; import java.util.ArrayList; import java.util.List;
/**
* Created by chengcai on 2019/3/7.
*/
public class CircleQueueEntity<T> { private int head; private int tail; private int index; private int size; private List<T> list = null; private List<T> deList=null;
public CircleQueueEntity() { head = 0; tail = 0; index = 0; size = AbstractComDataSet.QueueBufferSize; ConstructList(); }
void ConstructList()
{ list=new ArrayList<T>(); deList=new ArrayList<T>(); for (int i=0;i< size;i++) { list.add(null); } } public void setHead(int pointer) { this.head=pointer; } public int getHead() { return this.head; } public void setTail(int pointer) { this.tail=pointer; }
public int getTail() { return this.tail; }
public void setIndex(int pointer) { this.index= pointer; }
public int getIndex() { return this.index; }
public int getSizeOnly() { return size; } public List<T> getListCollection() { return this.list; } public List<T> getDeListCollection(){ return this.deList;}
}
4.循环队列类(CircleQueue)
package com.chengcai.util;
import java.util.List;
/**
* Created by chengcai on 2019/3/7.
*/
public class CircleQueue<E> implements ICircleQueue<E>{
private CircleQueueEntity<E> entity=null; private int requestElementIndex=0;
public CircleQueue()
{ entity=new CircleQueueEntity<E>(); }
@Override public boolean enQueue(E e)
{
if (isFull())
return false;
int index=entity.getIndex();
int tail=entity.getTail();
int size=entity.getSizeOnly();
if (tail>=size) {
entity.setTail(0);
tail=entity.getTail();
entity.setIndex(0);
index=entity.getIndex();
}
entity.getListCollection().set(entity.getTail(),e);
entity.setIndex(index + 1);
entity.setTail(tail + 1);
this.requestElementIndex++;
return true;
}
@Override public E deQueue()
{ if (isEmpty())
return null;
int head =entity.getHead();
int size=entity.getSizeOnly();
if (head>=size)
{
entity.setHead(0);
head =entity.getHead();
}
E deQueueElement=entity.getListCollection().get(head);
entity.getDeListCollection().add(deQueueElement);
entity.getListCollection().set(head,null);
entity.setHead(head+1);
return deQueueElement;
}
@Override public boolean isFull()
{
List<E> list=entity.getListCollection();
for(E obj:list)
{
if (obj==null)
return false;
} return true;
}
@Override
public boolean isEmpty()
{ List<E> list=entity.getListCollection();
return list.isEmpty();
}
@Override public CircleQueueEntity getQueueEntity()
{
return entity;
}
@Override
public int getQueueItemSize(){
return entity.getListCollection().size();
}
@Override public int getRequestElementIndex()
{
return this.requestElementIndex;
}
}
5.Main
package com.chengcai; import com.chengcai.util.*; public class Main {
private static String enQueue(ICircleQueue q, int[] data)
{
StringBuilder sb =new StringBuilder(); String strTemp=""; boolean isSuccess =false; int requestElementIndex=q.getRequestElementIndex();
sb.append("已成功入队:");
for (int i=requestElementIndex;i<data.length;i++)
{
isSuccess=q.enQueue(data[i]);
if (isSuccess) {
strTemp += Integer.toString(data[i]) + ",";
}
}
sb.append(strTemp);
return sb.toString();
}
private static String waitQueue(ICircleQueue q, int[] data)
{
StringBuilder sb =new StringBuilder(); String strTemp=""; int requestElementIndex=q.getRequestElementIndex();
strTemp="正在排队的元素:";
for (int i=requestElementIndex;i<data.length;i++)
{
strTemp += Integer.toString(data[i]) + ",";
}
sb.append(strTemp); return sb.toString();
}
private static String deQueue(ICircleQueue q,int deQueueFlag)
{
StringBuilder sb =new StringBuilder(); String strTemp="";
sb.append("已成功出队(FIFO):");
for (int i=0;i<deQueueFlag;i++)
{
strTemp= strTemp + q.deQueue().toString();
strTemp += ",";
}
sb.append(strTemp);
return sb.toString(); }
public static void main(String[] args) {
int[] data={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,20,21,22,23,24,25}; ICircleQueue q=new CircleQueue(); String strPrint;
strPrint="当前队列长度为:"+q.getQueueItemSize();
System.out.println(strPrint);
strPrint=enQueue(q,data); System.out.println(strPrint);
strPrint=waitQueue(q,data); System.out.println(strPrint);
strPrint=deQueue(q,3); System.out.println(strPrint);
strPrint=enQueue(q,data); System.out.println(strPrint);
strPrint=waitQueue(q,data); System.out.println(strPrint);
strPrint=deQueue(q,8); System.out.println(strPrint);
strPrint=enQueue(q,data); System.out.println(strPrint);
strPrint=waitQueue(q,data)+"全部元素已入队列"; System.out.println(strPrint); }
}
6.运行结果:
当前队列长度为:10
已成功入队:1,2,3,4,5,6,7,8,9,10,
正在排队的元素:11,12,13,14,15,20,21,22,23,24,25,
已成功出队(FIFO):1,2,3,
已成功入队:11,12,13,
正在排队的元素:14,15,20,21,22,23,24,25,
已成功出队(FIFO):4,5,6,7,8,9,10,11,
已成功入队:14,15,20,21,22,23,24,25,
正在排队的元素:全部元素已入队列