java队列--数据结构

---

前言

顺序表和链表两种存储方式实现数据结构–队列。

---

本文源代码网址：https://gitee.com/zfranklin/java/tree/master/dataStructure/src/com/njupt/queue

https://gitee.com/zfranklin/java/tree/master/dataStructure/src/com/njupt/queue

---

队列的性质

先进先出。如果一个单向行驶的隧道，先进隧道的先出去，后面一个接着一个排队，顺序不可打乱。

数组队列

成员变量

1.一个数组，存储数据
2.一个size，表示队列长度
3.head和tail，队列不像栈只在一端进出数据，所以要定义head和tail两个标志一进一出，我们以头出尾进为例。

方法

用数组实现队列，和数组实现栈一样，两种构造方法。

---

数据进入队列：
不能用栈的push，约定俗成push和pop时栈的方法，队列用in和out。

正常情况下：只需要在tail+1的位置存入新数据，但是由于head方会出数据，有多余的空间，还能进数据，所以tail = (tail+1)%this.values.length 。用取模使得数组循环起来，剩余的空间也能循环利用。值得注意的是，如果是进第一个数据，head的值要变为tail。

this.tail = (this.tail+1)%this.values.length;
this.values[this.tail] = num;
this.size++;
if(this.size==1) this.head = this.tail;

也有可能遇到整个数组都被用完的情况，这个时候我们需要扩容。

在搬移数据时和栈不同，栈搬数据只需要将短数组数据一个一个搬入长数组，下标一样。但是队列进进出出，下标不知道是多少。干脆从head开始一个一个搬进长数组，长数组从下标为0开始。因为满了才会扩容，所以循环次数为 this.values.length。短数组的下标仍然要+1取模，循环把数组前前后后的数组都读完。

public void capacityIncrease()
{T temp[] = (T[])new Object[(this.values.length+1)*2];int j=this.head;for(int i=0;i<this.values.length;i++){temp[i] = this.values[j];j = (j+1)%this.size;}this.head = 0;this.tail = this.size-1;values = temp;System.out.println("capacity increased,size="+this.size);
}

最后头置0，尾时this.size-1。还要记得把temp临时数组赋给this.values。

---

数据出队列out
先判断队列是否为空，size是否为0。若为0，返回false，出数据失败。

然后head+1，仍然要取模，循环起来。this.size–。和进数据对应的，当this.size==0时，this.tail也要变为this.tail一样的值。因为最后一个数据tail和head肯定是一样的，out之后，head往前走，但是tail不动，tail在head的前面去了。如果再进数据，倒也没问题，但是如果其他地方要用 tail 和 head ，可能会出现奇怪的问题。所以能避免尽量避免。

链表栈

成员变量

仅需头结点，尾结点，size可有可无，如果有，有需要直接返回size；没有，有需要从头到尾遍历一遍，有多少个结点，就有多大的size。

头进尾出，还是头出尾进？

头插头删都是比较好处理的，关键是尾部。尾插也很容易，尾删就难了。先要遍历一遍找到尾的前一个结点，再把前一个结点的next变为null。所以尾进头出比较简便。

方法

无需自写构造函数。

in 进数据：尾插
注意第一个数据进入时，头节点也要指向第一个数据。

out 出数据：头删
删完最后一个数据时，head会变成空，但是tail仍然指向最后一个数据。再重新in新数据，使用起来没有问题。但是最好在删完数据时把tail置空，让垃圾回收器尽快把不用的空间回收了。

public boolean out()
{if(this.head == null) {System.out.println("Out failed");return false;}	this.head = this.head.next;this.size--;if(this.head == null) this.tail = null;return true;
}

总结

顺序存储和链式存储在实现队列时优劣明显，链式比数组方便很多。不过数组实现队列运用的循环数组的思想比较有趣，和C语言专栏的密码专函小练习类似。