在我们的日常生活中，有许多排队的情形，像在食堂排队打饭，在购票窗口排队购票等等，像这种满足成员元素先进先出特性的问题可以抽象成队列问题（不考虑队尾或者队伍中间的人由于种种因素中途离开的情形），那么什么是队列呢？
队列（Queue）队列也是线性表的一种，和栈一样是一种特殊的线性表，只不过队列满足的特点是先进先出（FIFO或者FCFS–>First Come First Service），而后者的特点是先进后出（FILO）。
ADT作为一个队列，它要实现的基本功能如下：置空，判空，获取队列长度，获取队首元素，入队，出队并返回队首元素，输出。其相应的接口定义如下
public interface IQueue {
public void clear();//置空
public boolean isEmpty();//判空
public int length();//获取队列长度
public Object peek();//获取队首元素
public void offer(Object x)throws Exception;//入队
public Object pop();//出队并返回队首元素
public void display();
}
实现
队列的实现同样有顺序存储结构和链式存储结构两种，顺序存储结构也同样是用数组实现，但是常规的队列使用顺序存储会存在一个很大的问题，首先，我们假设只定义常规的队列并使用顺序存储，而定义的入队和出队的方法如下：
入队：
//入队
public void offer(Object x) throws Exception {
if(rear==ElemQueue.length) {
throw new Exception("队列已满");
}else {
ElemQueue[rear]=x;
rear=rear+1;
}
}
//出队
public Object poll() {
if(!isEmpty()) {
Object x=ElemQueue[front];
front++;
return x;
}
return null;
}
伴随着不断的入队出队操作，front指针和rear指针都会向后移，而当到了rear与ElemQueue.length相等时，队列满，但事实上这个数组空间可能还有很多空间是没有使用的（front之前的），这就是“假溢出”，此时数组空间没满但是程序将队列判断为满，新的元素入队抛出溢出错误。所以为了解决这个问题我们引入了循环队列
循环队列
空出一个数组元素的空间，不存放元素，调整代码的逻辑结构，rear指向队尾元素的下一个元素，当队列满的条件修改为(rear+1)%ElemQueue.length等于0，并且在其他的函数中同样作出相应的修改（相较于常规的顺序表的函数），最终实现循环队列的代码如下：
package circleQueue;
import iQueue.IQueue;
public class CircleQueue implements IQueue{
public int front,rear;
public Object[] ElemQueue;
public CircleQueue(int maxSize) {
front=rear=0;
ElemQueue=new Object[maxSize];
}
@Override
public void clear() {
front=rear=0;
}
@Override
public boolean isEmpty() {
return front==rear;
}
@Override
public int length() {
return (rear-front+ElemQueue.length)%ElemQueue.length;
}
@Override
public Object peek() {
if(!isEmpty()) {
return ElemQueue[front];
}
return null;
}
@Override
public void offer(Object x) throws Exception {
if((rear+1)%ElemQueue.length==0) {
throw new Exception("队列已满");
}else {
ElemQueue[rear]=x;
rear=(rear+1)%ElemQueue.length;
}
}
@Override
public Object poll() {
if(!isEmpty()) {
Object x=ElemQueue[front];
front=(front+1)%ElemQueue.length;
return x;
}
return null;
}
public void display() {
if(!isEmpty()) {
for(int i=front;i!=rear;i=(i+1)%ElemQueue.length) {
System.out.print(ElemQueue[i].toString()+" ");
}
System.out.println();
}
else {
System.out.println("队列为空");
}
}
}
这样就避免了假溢出的问题，虽然浪费了一个数组元素的空间，但是我们在实现其他函数的时候方便了很多，当然最主要的还是解决了假溢出的问题
链队列
队列的链式实现，就和单链表差不多，只不过由于先进先出的特点，在入队函数和出队函数相比有点特殊而已，具体代码实现如下：
package linkQueue;
import iQueue.IQueue;
public class linkQueue implements IQueue{
Node front,rear;
public linkQueue() {
front=rear=null;
}
@Override
public void clear() {
front=rear=null;
}
@Override
public boolean isEmpty() {
return front==null;
}
@Override
public int length() {
if(!isEmpty()) {
Node p=front;
int len=0;
while(p!=null) {
++len;
p=p.next;
}
return len;
}
return 0;
}
@Override
public Object peek() {
return front.data;
}
@Override
public void offer(Object x) throws Exception {
Node s=new Node(x);
if(!isEmpty()) {
rear.next=s;
rear=s;
}else
front=rear=s;
}
@Override
public Object poll() {
if(!isEmpty()) {
if(front==rear) {
front=null;
}
Node p=front;
front=front.next;
return p.data;
}
return null;
}
@Override
public void display() {
if(!isEmpty()) {
Node p=front;
while(p!=null) {
System.out.print(p.data.toString()+" ");
p=p.next;
}
}else {
System.out.println("队列为空");
}
}
}
优先队列
但是在实际情况中，经常会出现并不完全按照先到先服务的情形（先进先出），比如程序的进程问题：正常情况下按照程序启动的先后顺序执行程序，但是在特殊情况下并不会按照先启动就先运行，比如现在有一个管理系统负荷超载的程序（此时程序的负荷超过了计算机系统的承受范围，需要执行该程序，防止系统崩溃），那么系统肯定会优先执行这个程序，因为它的优先级比其他的程序要高。由此我们引入了优先级队列，这是应用程度比其他队列要高的一种数据结构。通常使用链式存储实现，由于优先级的存在，笔者采用的是重新定义了结点Node类（定义后的结点为优先级结点PriNode）的方法
PriNode：
package linkQueue;
//带有优先级的结点
public class PriNode {
public Object data;
public int prior;
public PriNode next;
public PriNode() {
data=null;
prior=-1;
}
public PriNode(Object data,int prior) {
this.data=data;
this.prior=prior;
}
}
而优先队列的特殊也只在于入队操作，需要进行一个优先级的比较，并不是像其他队列那样简单的从队尾插入。具体实现代码如下：
package linkQueue;
import iQueue.IQueue;
//优先级队列
public class PriQueue implements IQueue{
PriNode front,rear;
public PriQueue() {
front=rear=null;
}
@Override
public void clear() {
front=rear=null;
}
@Override
public boolean isEmpty() {
return front==null;
}
@Override
public int length() {
if(!isEmpty()) {
PriNode p=front;
int len=0;
while(p!=null) {
++len;
p=p.next;
}
return len;
}
return 0;
}
@Override
public Object peek() {
if(!isEmpty()) {
return front.data;
}
return null;
}
@Override
public void offer(Object x) throws Exception {
//默认传入的实参为PriNode类型所以可以强转
PriNode s=(PriNode)x;
if(!isEmpty()) {
PriNode p=front,q=p;
while(p!=null && p.prior<=s.prior) {
q=p;
p=p.next;
}
if(p==null) {
rear.next=s;
rear=s;
}
else if(p==front){
s.next=front;
front=s;
}else {
s.next=q.next;
q.next=s;
}
}
else front=rear=s;
}
@Override
public Object pop() {
if(!isEmpty()) {
if(front==rear) {
front=null;
}
PriNode p=front;
front=front.next;
return p.data;
}
return null;
}
@Override
public void display() {
if(!isEmpty()) {
PriNode p=front;
while(p!=null) {
System.out.print(p.data.toString()+" ");
p=p.next;
}
}else {
System.out.println("队列为空");
}
}
}
总结
以上就是队列（主要是循环队列和链队列）和优先队列的一个实现，笔者在优先队列的入队函数可能不太完善，传的参数其实是Object类型，但是笔者考虑时默认传的是PriNode类型，将问题简单化了，如果有更好的处理方法欢迎各位大佬指出。
