顺序与链式队列

前言

队列是一种特殊的线性表，其插入和删除操作分别在线性表的两端进行。特点是先进先出。

队列抽象数据类型

其中，像队列中插入元素的过程称为入队（enqueue），删除元素的过程称为出队（dequeue），允许入队的一端称为队尾（rear），允许出队的一头称为对头（front），没有元素的队列称为空队列

public interface QQueue<T> {

	boolean isEmpty();          //判断队列是否为空
	void enqueue(T x);          //元素x入队
	T dequeue();                //出队，返回对头元素
	
}

顺序队列

顺序队列使用数组存储数据元素
1.当队列空时，设置队头、队尾下标front=rear=-1，
2.当第一个元素入队时，front=rear=0，同时改变两个下标
3.进行入队、出队操作，front、rear随之变化
4.当入队的元素个数（包括已出队元素）超出数组容量时，rear下标越界，数据溢出，但是，由于之前已有若干元素出队，数组前部以空出许多存储单元，所以这种溢出并不是因为存储空间不够而产生的，称为假溢出

所以顺序队列有两个缺点：假溢出和存储单元没有重复使用机制

顺序循环队列

相比较顺序队列，有如下不同
1.队头、队尾元素按照如下循环规律变化，其中length表示数组长度
front=（front+1)%length;
rear=(rear+1)%length;
所以可以看出front和rear的取值范围为0~length-1；

2.约定rear是下一个入队元素位置，队列空条件是front==rear，即入队只改变rear，出队只改变front
3.约定队列满条件是队列中仍然有一个空位置，即front==（rear+1）%length，

public class SeqQueue<T> implements QQueue<T>{

	private Object element[];  //存储队列数据元素的数组
	private int front,rear;    //分别为对头和队尾元素
	
	public SeqQueue(int length){        //构造容量为length的空队列
		if(length<64)
			length=64;
		this.element=new Object[Math.abs(length)];
		this.front=this.rear=0;
	}
	
	public SeqQueue(){       //构造默认容量空队列
		this(64);
	}
	
	public boolean isEmpty() {     //判断队列是否为空
		return this.front==this.rear;
	}

	public void enqueue(T x) {   //元素x入队，空对象不能入队
	if(x==null)
		return;
	if(this.front==(this.rear+1)%this.element.length) //当队满时，扩充容量
	{
		Object[] temp=this.element;
		this.element=new Object[temp.length*2];
		int i=this.front,j=0;
		while(i!=this.rear){        //按照队列元素次序复制数组元素
			this.element[j]=temp[i];
			i=(i+1)%temp.length;
			j++;
		}
		this.front=0;
		this.rear=j;
	}
		this.element[this.rear]=x;
		this.rear=(this.rear+1)%this.element.length;
	}

	public T dequeue() {         //出队，返回队头元素，若队列空则返回null
   if(isEmpty())
		return null;
    T temp=(T)this.element[this.front];
      this.front=(this.front+1)%this.element.length;  //取得队头元素
     return temp;
	}

}

链式队列

以不带头结点的单链表实现链式队列，设指针front和rear分别指向队头和队尾结点，初始空队列的状态设置为front=rear=null；队列空条件是front==null&&rear==null

public class LinkedQueue<T> implements QQueue<T>{

	private Node<T> front,rear;        //分别指向队头和队尾
	
	public LinkedQueue(){             //构造空队列
		this.front=this.rear=null;
	}
	
	public boolean isEmpty() {        //判断队列是否为空
		return this.front==null&&this.rear==null;
	}

	public void enqueue(T x) {       //元素x入队，空对象入队
		if(x==null)  
			return;
		Node<T> q=new Node<T>(x,null);  
		 if(this.front==null)
			 this.front=q;   //空队入队
		 else
			 this.rear.next=q; //插入在队尾之后
		 this.rear=q;		
	}

	public T dequeue() {  //出队，返回对头元素，若队列元素为空，返回null
		if(isEmpty())
			return null;
		T temp=this.front.data;    //取得队头元素
		this.front=this.front.next;    //删除队头结点
		if(this.front==null)
			this.rear=null;
		return temp;
	}

}