一、队列基本操作
1、队列的基本认识
队列的基本特性就是先进先出（FIFO）。也就是第一个进去的元素，第一个出来。现在给出一个标准的定义：
队列就是一个只允许在一端进行插入，在另一端进行删除操作的线性表。
既然是线性表，按照存储方式那就有两种存储方式，基于数组的顺序存储方式和基于链表的链式存储方式。
队列按照实现方式也分为两种：
①、单向队列（Queue）：只能在一端插入数据，另一端删除数据。
②、双向队列（Deque）：每一端都可以进行插入数据和删除数据操作。
有了对概念分类有了了解，下面我们就是用java代码来实现这些队列
2、顺序队列的实现
顺序队列是基于数组实现的，针对于队列的操作主要有以下几个
（1）插入（2）删除（3）查找元素（4）队列长度（5）是否为空、
我们先给出最基本的操作图解
下面就根据这几个常用的操作使用java代码来实现队列
首先，我们定义一个操作队列的接口
public interface Queue<T> { //增加元素 void add(T t); //删除元素 T remove(); //队列长度 int size(); //返回对头元素，并未删掉 T front(); //是否为空 boolean isEmpty(); //是否已满 boolean isFull() }
然后我们就开始去实现。
插入操作，我们首先要先判断当前队列是否已满，如果满了直接返回。接下来得到当前元素的位置。最后插入元素，再移动位置。
删除操作与插入操作类似，首先要先判断当前队列是否为空，如不为空再移动指针（这里不是指针，指的是指向当前元素位置的标志），删除元素。
判断当前元素是否为空和是否已满类似，只需要判断当前队列的元素数量。
下面给出代码实现。
public class ArrayQueue<T> implements Queue<T>{ private T[] data; private int size;//元素个数 private int front;//队列中第一个对象的位置 private int rear;//队列中当前对象的位置 //初始化方法 public ArrayQueue() { data = (T[]) new Object[10]; size = 0; front =0; rear = 0; } //增加元素 @Override public void add(T t) { if(isFull()){ resize(); front = 0; } rear = (front+size)%data.length; System.out.println(rear); data[rear] = t; size++; } //删除元素 @Override public T remove() { if (isEmpty()) { throw new RuntimeException("队列为空!"); } T tempData = data[front]; data[front] = null; front = (front + 1) % (data.length); size--; return tempData; } //取得队列大小 @Override public int size() { return size; } @Override public boolean isEmpty() { return size == 0; } //判断当前队列是否已满 @Override public boolean isFull(){ return size == data.length; } //取得当前队头元素 @Override public T front() { if (isEmpty()) { throw new RuntimeException("队列为空!"); } return data[front]; } //扩容 public void resize(){ /*注意重新扩容的时候并不需要去设置size * 队列的大小并不能通过数组的大小直观的显示出来。 * 但是栈就可以直观的通过数组的大小显示出来*/ T[] tmp = (T[]) new Object[data.length*2]; System.arraycopy(data, 0, tmp, 0, data.length); data = tmp; tmp = null;//引用置为空，便于gc处理 } }
3、链式队列的实现
链式队列与顺序队列不同，每个节点不仅保存当前元素的值，还有指向下一个元素的指针。所以我们先看一下每个节点的图解形式
使用代码来表示就是
public class QueueNode<Item>{ Item item; QueueNode next; }
然后我们看链式队列入队和出队的操作
（a）空队列 （b）X入队 （c）y入队 （d）x出队
从上面的操作我们可以看到，实现上面的操作我们需要实现下面的代码
（1）一个指向FIFO头节点的指针
（2）一个指向FIFO尾节点的指针
（3）一个记录节点数的Int变量
private QueueNode first;//指向FIFO头节点的指针 private QueueNode last; //指向FIFO尾节点的指针 private int nodeNum; //记录节点数的Int变量
（4）判断当前队列是否为空
public boolean isEmpty(){ return first == null; }
（5）队列的大小
public int size(){ return nodeNum; }
（6）入队和出队操作
//入队 public void enqueue(Item item) { QueueNode oldLast = last; last = new QueueNode(); last.item = item; last.next = null; if (isEmpty()){ first = last; } else{ oldLast.next = last; } nodeNum++; } //出队 public Item dequeue(){ Item item = (Item) first.item; first = first.next; if (isEmpty()){ last = null; } nodeNum--; return item; }
（7）遍历
private class LinkListIterator implements Iterator<Item>{ QueueNode node = first; @Override public boolean hasNext(){ return node.next != null; } @Override public Item next(){ Item item = (Item) node.item; node = node.next; return item; } }
OK。有了上面的这些操作之后，下面给出一个完整的代码
public class Queue<Item> implements Iterable<Item>{ private QueueNode first; private QueueNode last; private int nodeNum; public boolean isEmpty(){ return first == null; } public int size(){ return nodeNum; } public void enqueue(Item item){ QueueNode oldLast = last; last = new QueueNode(); last.item = item; last.next = null; if (isEmpty()){ first = last; } else{ oldLast.next = last; } nodeNum++; } public Item dequeue(){ Item item = (Item) first.item; first = first.next; if (isEmpty()){ last = null; } nodeNum--; return item; } @Override public Iterator<Item> iterator(){ return new LinkListIterator(); } private class LinkListIterator implements Iterator<Item>{ QueueNode node = first; @Override public boolean hasNext(){ return node.next != null; } @Override public Item next(){ Item item = (Item) node.item; node = node.next; return item; } } }
OK，上面就是顺序队列和链式队列的基本实现。下面我们将介绍一种新的队列循环队列，为什么要有这个队列，我们先要考虑一个问题，也就是我们的队列弹出一个元素，那么这个空间将不能使用。这就是假溢出问题：
为了解决这个问题所以才出现了一个新的队列-循环队列
二、循环队列
我们先给出队列的图解形式
有了循环队列的基本实现，我们思考一个问题，在之前我们可以根据rear直接得到当前队列是否为空和是否已满。那么在循环队列里面还可以这样嘛？当然不可以，我们需要考虑font和rear的位置关系来判断。我们看下面两种情况：
一种是队列为空的时候，front和rear都指向同一个位置。一种是队列已满的时候，front和rear指向的元素紧邻。
我们可以使用下面的公式来判断
我们代码实现一下循环队列
public interface IQueue { public void clear(); public boolean isEmpty(); public int length(); public Object peek();// 取队首元素 public void offer(Object x) throws Exception;// 入队 public Object poll();// 出队 public void display(); }
然后是接口的实现
public class CircleSqQueue implements IQueue { private Object[] queueElem;//队列存储空间 private int front;//队首引用，若队列不为空，指向队首元素 private int rear;//队尾引用，若队列不为空，指向队尾的下一个元素 public CircleSqQueue(int maxsize) { front=rear=0; queueElem=new Object[maxsize];//分配maxsize个单元 } @Override public void clear() { front=rear=0; } @Override public boolean isEmpty() { return rear==front; } @Override public int length() { return (rear-front+queueElem.length)%queueElem.length; } @Override public Object peek() { if(front==rear){ return null; } else{ return queueElem[front]; } } @Override public void offer(Object x) throws Exception { if((rear+1)%queueElem.length==front){//队满 throw new Exception("队列已满"); } else{ queueElem[rear]=x; rear=(rear+1)%queueElem.length;//修改队尾指针 } } @Override public Object poll() { if(front==rear){ return null;//队列为空 } else{ Object t=queueElem[front]; front=(front+1)%queueElem.length; return t; } } @Override public void display() { if(!isEmpty()){ for(int i=front;i!=rear;i=(i+1)%queueElem.length){ System.out.println(queueElem[i].toString()+" "); } } else{ System.out.println("此队列为空"); } } }
三、总结
对于队列主要在于面试中常见的算法题，因为概念非常容易理解，我们只要根据当前实现的代码进行一些变化就好。谢谢大家的关注。
