文章目录
- 前言
- 本文源代码网址:https://gitee.com/zfranklin/java/tree/master/dataStructure/src/com/njupt/queue
- 队列的性质
- 数组队列
- 成员变量
- 方法
- 链表栈
- 成员变量
- 方法
- 总结
前言
顺序表和链表两种存储方式实现数据结构–队列。
javatreemasterdataStructuresrccomnjuptqueue_12">本文源代码网址: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。
java">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取模,循环把数组前前后后的数组都读完。
java">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置空,让垃圾回收器尽快把不用的空间回收了。
java">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语言专栏的密码专函小练习类似。