队列也是一直特殊的线性表，它只允许在表尾插入数据，在表头删除数据，具有先进先出（First In First Out）的特性
队列的抽象数据类型（此处使用了泛型）：
public interface IQueue<T> {
public void clear();
public boolean isEmpty();
public int length();
public T peek();//查看表头数据元素
public void offer(T x) throws Exception;//表尾插入数据
public T poll();//表头删除数据
public void display();
}队列也分为顺序队列和链队列
顺序队列
顺序队列也是通过数组来存储数据元素的。
顺序队列需要两个变量front和rear，front指向队首元素，rear指向队尾元素的下一个存储位置
1、可以想象，若在一个存储5个元素的顺序队列中，存储5个元素，再删除表头的3个元素，此时不能再进行插入，但是队列还有存储空间，这就是所谓的“假溢出”。
解决假溢出的方法是，把顺序队列看成一个循环的顺序队列，当rear或front达到maxSize时，利用对整数的取余运算来解决。尾插入时（rear=（rear+1）%maxSize）。
2、采用上述方法还存在一个严重的问题，无法判别队列是空还是满，因为此时两种情况都是“rear==front”。这里采用一种方法，在存储空间的容量为maxSize时，只允许存储maxSize-1个数据元素。此时就能区分队列是空还是满了。空：rear==front，满：front==（rear+1）%maxSize
public class CircleSqQueue<T>implements IQueue<T> {
private Object[] queueElem;
private int front;//队首元素
private int rear;//队尾元素的下一个位置
public CircleSqQueue(int maxsize){
front=rear=0;
queueElem=new Object[maxsize];
}
public void clear(){
front=rear=0;
}
public boolean isEmpty(){
return front==rear;
}
public int length(){
return (rear-front+queueElem.length)%queueElem.length;
}
@SuppressWarnings("unchecked")
public T peek(){
if(front==rear)
return null;
return (T)queueElem[front];
}
public void offer(T x) throws Exception{
if(front==(rear+1)%queueElem.length)
throw new Exception("队列已满");
queueElem[rear]=x;
rear=(rear+1)%queueElem.length;
}
public T poll(){
if(this.isEmpty())
return null;
else{
@SuppressWarnings("unchecked")
T x=(T) queueElem[front];
front=(front+1)%queueElem.length;
return x;
}
}
public void display(){
for(int i=front;i<this.length();i++){
System.out.print(queueElem[(i+queueElem.length)%queueElem.length]+" ");
}
System.out.println();
}
}链队列
不需要头结点。
需要两个指针front和rear分别指向队首元素和队尾元素的结点
class Node<T>{
public T data;
public Node<T> next;
public Node(){
this.data=null;
this.next=null;
}
public Node(T data){
this.data=data;
this.next=null;
}
public Node(T data,Node<T> next){
this.data=data;
this.next=next;
}
}
public class LinkQueue<T> implements IQueue<T>{
private Node<T> front;
private Node<T> rear;
public LinkQueue(){
front=null;
rear=null;
}
public void clear(){
front=rear=null;
}
public boolean isEmpty(){
return front==null&&rear==null;
}
@Override
public int length() {
Node<T> p=front;
int length=0;
while(p!=null){
p=p.next;
length++;
}
return length;
}
public T peek(){
if(front==null)
return null;
return front.data;
}
/*
* 1、判断队首结点是否为空，若是，则队首结点==队尾结点==插入结点
* 2、若不为空，队尾结点尾插入元素，队尾指针向后移动
*/
public void offer(T data){
if(front!=null){
rear.next=new Node<T>(data);
rear=rear.next;
}
else
rear=front=new Node<T>(data);
}
/*
* 1、判断队首指针是否为空，为空，返回null
* 2、若不为空，判断此时队首结点是否等于队尾结点，若是，队尾==null
*/
public T poll(){
if(front!=null){
T x=front.data;
if(front==rear)
rear=null;
front=front.next;
return x;
}
else
return null;
}
public void display(){
Node<T>p=front;
while(p!=null){
System.out.print(p.data+" ");
p=p.next;
}
System.out.println();
}