一：概述
队列.jpg
关于队列的操作，我们这里主要实现入队，出队，判断空队列和清空队列等操作，声明队列接口Queue（队列抽象数据类型）如下：
public interface Queue<T> {
//队列长度
int size();
//队列是否为空
boolean isEmpty();
//入队
boolean enqueue(T data);
//返回队列头
T peek();
//出队
T dequeue();
}
二：顺序循环队列
double.009.jpeg
从上图的演示可以看出，队列的出队和入队，都会修改front和rear，对于顺序队列来说，因为rear一直增大，当增大到一定程度时，就会出现队列貌似满了的现象，这时候无法添加元素，就算队列里面有空间也不行，这种情况叫做假溢出，假溢出的缺点是很明显的。顺序循环队列就可以 解决假溢出的问题，如上图中，碰到80咋整？当然是让80回头是岸，放到队里前面去：
double.011.jpeg
所以，对于循环队列来说，front不一定小于rear，这样设计的好处很明显，能够循环利用存储单元。
上面的方法解决了空间浪费的问题，但是考虑的还不够全面；80入队后，这根"水管"的头和尾都被堵住了，那么如果还想入队怎么办？办法总是有的，这个时候就要考虑扩容了；那么什么时候扩容呢？真的要等到所有位置都填充了数据才开始扩容吗？并不是的，如上图所示，队列中还有个空位，但是明显无法入队了；这时候如果可能的话，就要扩容了；另外，如果真的还可以入队，那么front和rear就势必相等了；需要注意的是，空队列的front和rear也是相等的；当然，我们通过设置标记位来判断到底是空队列还是满队列，不过一个更好的方案是预留一个位置，当队列还剩一个位置没有数据填充时，就认为该队列是满的，例如上图的队列，虽然1号位置是空的，但是我们还是认为该队列已经满了，不宜再入队了。
综上可知，队列的front和rear的取值范围应该是0 - size-1；需要注意的是，队里中的元素，除了队头和队尾外，其他元素之间的位置是相连的，在上图中，不存在2和4号位有数据，而3号位却空出来的场景，所以有如下的约定：
1.front是队头元素的下标；rear指向下一个入队的元素存储的位置的下标
2.当front == rear时，此队列是空队列
3.入队改变rear的指向，出队改变front的指向，size是指队列的长度(不是容量)
4.约定满队列的条件是front == (rear + 1) % size；此时，队列中还有一个空的位置，主要是方便区分空队列和满队列；如上图中，rear == 1，front == 2，(1 + 1) % 5 == 2。
下面就通过数组来实现一个简单的队列：
public class SeqQueue<T> implements Queue<T> {
//默认容量，必要的时候可以扩容
private static final int DEFAULT_SIZE = 10;
//存储数据的数组
private T elementData[];
//队头和队尾指针
private int front,rear;
//队列长度
private int size;
@SuppressWarnings("unchecked")
public SeqQueue() {
elementData = (T[]) new Object[DEFAULT_SIZE];
front = rear = 0;
}
//队列长度，直接返回size好了
@Override
public int size() {
return size;
}
//按照上面的约定，front == rear时为空队列
@Override
public boolean isEmpty() {
return front == rear;
}
//入队
@Override
public boolean enqueue(T data) {
//如果队列满了，那么扩容，队列满的条件上面解释过
if(this.front == (this.rear + 1) % this.elementData.length) {
ensureCapacity(elementData.length*2+1);
}
//将数据存入rear指向的位置
elementData[this.rear] = data;
//更新rear指向下一个空元素的位置，当rear指向最后一个位置时，
//(this.rear + 1) % elementData.length就等于0，也就是
//说，此时rear指向了队头，只有这样做，才能做到存储单元的复用
this.rear = (this.rear + 1) % elementData.length;
//长度+1，没毛病
size ++;
return true;
}
//获取队头元素，直接返回数组指定的数据即可，简单
@Override
public T peek() {
return elementData[front];
}
//出队
@Override
public T dequeue() {
//获取头元素，最终返回的也是他
T tmp = this.elementData[front];
//将front指向下一个元素，需要注意的是，原来的头元素并没有置空
//因为front已经指向下一个元素，原来的头元素的位置虽然还有数据
//但是他已经没有意义了，下次入队的时候，就会把这个元素的数据
//更新，在这里置空操作是非必要的，这跟上图的操作是不太一样的
this.front = (this.front + 1) % this.elementData.length;
//长度-1，没毛病
size --;
return tmp;
}
//扩容，思路很简单，就是重新创建一个数组，
//然后将原来的数据按照秩序拷到新的数组
@SuppressWarnings("unchecked")
private void ensureCapacity(int capacity) {
//临时存储老的数据
T[] old = elementData;
//创建新的数组
elementData = (T[]) new Object[capacity];
int j = 0;
//这里的循环条件有点不一样，首先肯定是从队头开始拷贝，
//这个队头的索引不一定是0，只能取this.front；循环结
//束的条件是i != this.rear，也就是从队头开始拷，一
//到队尾结束；自增的条件是i = (i + 1) % old.length，
//这里千万不能用i++，因为有时候rear小于front，如果i++
//那么永远也到不了队尾，同时还会抛出数组越界的异常，而
//(i + 1) % old.length能够保证当rear小于front的时候，
//i能及时，正确的回到正确的位置，也就是上图中的"水管"的左边
//这样才能保证新队列的顺序能和老队列的顺序保持一致，很重要
for(int i = this.front ; i != this.rear ; i = (i + 1) % old.length) {
elementData[j++] = old[i];
}
this.front = 0 ;
this.rear = j;
}
//清空队列
public void clear(){
//循环的条件和上面扩容的条件一样
for(int i = this.front ; i != this.rear ; i = (i + 1) % elementData.length){
//把每个元素置空
elementData[i] = null;
}
this.front = this.rear = -1;
size = 0;
}
}
上面就是顺序队列的实现方式，稍稍有点绕，总体还是比较简单的。
三：链式队列
1532872643491.jpg
可以看到，跟顺序循环队列比起来，只是将底层的数组换成了单向链表，国际惯例，画图来表示出队和入队的过程：
队列.010.jpeg
从图中可以看出，链式队列的入队和出队，只需要改变尾节点和头结点的指向即可，而且还不存在顺序链表中的假溢出问题，下面代码实现他：
public class LinkQueue<T> implements Queue<T> {
//对于链式队列来说，头尾节点是必不可少的
private Node<T> front,rear;
//链表的长度
private int size;
//链式队列没有容量的限制，但是最好是给它设置一个上线
private static final int MAX_SIZE = 128;
public LinkQueue() {
this.front = this.rear = null;
}
//简单，不解释
@Override
public int size() {
return size;
}
//头尾节点均为空代表空队列
@Override
public boolean isEmpty() {
return this.front == null && this.rear == null;
}
@Override
public boolean add(T data) {
if(size >= MAX_SIZE) {
return false;
}
Node<T> node = new Node<T>(data);
//空队列插入
if(this.front == null) {
this.front = node;
//非空队列插入
}else {
this.rear.next = node;
}
//新插入的节点就是尾节点
this.rear = node;
size ++;
return true;
}
//返回头节点的数据，简单
@Override
public T peek() {
return this.front == null ? null : this.front.data;
}
@Override
public T poll() {
//空队列返回空
if(isEmpty()) {
return null;
//非空队列返回头节点，然后将头结点指向他的后继节点
}else {
T tmp = this.front.data;
this.front = this.front.next;
//如果队列只有一个节点，那么出队后就成了空队列，所以队尾也要置空
if(this.front == null) {
this.rear = null;
}
size --;
return tmp;
}
}
//清除队列
public void clear() {
//头尾节点都不存在了，链表也就不存在了，这样队列就没了
this.front = this.rear = null;
this.size = 0;
}
@SuppressWarnings("hiding")
class Node<T> {
public T data;
public Node<T> next;
public Node() {
}
public Node(T data) {
this.data = data;
}
public Node(T data, Node<T> next) {
this.data = data;
this.next = next;
}
}
}
以上就是两种队列的设计和实现，比较简单；相对来说，链式队列更简单，出队和入队比顺序循环队列简洁，而且没有假溢出的问题。
摘自：https://blog.csdn.net/javazejian/article/details/53375004#%E9%98%9F%E5%88%97%E7%9A%84%E6%8A%BD%E8%B1%A1%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B
网友评论