在某些时候，我们不能被要求像数组一样可以使用索引随机访问，而是需要被限制顺序处理业务，今天介绍一种先进先出（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.Iterator;
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();
E deQueueElement=entity.getListCollection().get(head);
entity.getDeListCollection().add(deQueueElement);
entity.getListCollection().set(head,null);
entity.setHead(head+1);
head=entity.getHead();
if (head>size-1)
{
entity.setHead(0);
}
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();
boolean isnull=true;
for (E obj:list) {
if (obj!=null)
return false;
}
return isnull;
} @Override
public CircleQueueEntity getQueueEntity()
{
return entity;
}
@Override
public int getQueueItemSize(){
return entity.getListCollection().size();
} @Override
public int getRequestElementIndex()
{
return this.requestElementIndex;
}
public int getQueueElementCount()
{
int count=0;
Iterator it =entity.getListCollection().iterator();
while (it.hasNext())
{
if (it.next()!=null)
count++;
}
return count;
}
}
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,
正在排队的元素:全部元素已入队列