网站怎样改logo,电子商务网站建设组织流程图,青岛网站优化,建筑工程网库文章目录 前言本文源代码网址#xff1a;https://gitee.com/zfranklin/java/tree/master/dataStructure/src/com/njupt/queue队列的性质数组队列成员变量方法 链表栈成员变量方法 总结 前言
顺序表和链表两种存储方式实现数据结构–队列。 本文源代码网址#xff1a;https:/… 文章目录 前言本文源代码网址https://gitee.com/zfranklin/java/tree/master/dataStructure/src/com/njupt/queue队列的性质数组队列成员变量方法 链表栈成员变量方法 总结 前言
顺序表和链表两种存储方式实现数据结构–队列。 本文源代码网址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。
正常情况下只需要在tail1的位置存入新数据但是由于head方会出数据有多余的空间还能进数据所以tail (tail1)%this.values.length 。用取模使得数组循环起来剩余的空间也能循环利用。值得注意的是如果是进第一个数据head的值要变为tail。
this.tail (this.tail1)%this.values.length;
this.values[this.tail] num;
this.size;
if(this.size1) this.head this.tail;也有可能遇到整个数组都被用完的情况这个时候我们需要扩容。
在搬移数据时和栈不同栈搬数据只需要将短数组数据一个一个搬入长数组下标一样。但是队列进进出出下标不知道是多少。干脆从head开始一个一个搬进长数组长数组从下标为0开始。因为满了才会扩容所以循环次数为 this.values.length。短数组的下标仍然要1取模循环把数组前前后后的数组都读完。
public void capacityIncrease()
{T temp[] (T[])new Object[(this.values.length1)*2];int jthis.head;for(int i0;ithis.values.length;i){temp[i] this.values[j];j (j1)%this.size;}this.head 0;this.tail this.size-1;values temp;System.out.println(capacity increased,sizethis.size);
}最后头置0尾时this.size-1。还要记得把temp临时数组赋给this.values。 数据出队列out 先判断队列是否为空size是否为0。若为0返回false出数据失败。
然后head1仍然要取模循环起来。this.size–。和进数据对应的当this.size0时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语言专栏的密码专函小练习类似。
