数据结构之-队列
队列 一种特殊的 线性表 ，也是常见的一种数据类型。特殊之处在于它只能在表的前端(front)进行删除，而在表的后端(rear)进行插入操作。进行插入操作的端称为 队尾 ，进行删除操作的端称为 队头 。
队列 又称为先进先出（FIFO—first in first out）线性表。
线性表 分为 顺序存储 和 链式存储 ，栈是线性表，所以也有这两种存储方式。同样，队列作为一种特殊的线性表，也同样存在这两种存储方式。
顾名思义，顺序存储采用数组的方式，而链式存储采用链表的方式。
顺序存储的队列 又分为 顺序队列 和 循环队列 。
首选说一下顺序队列的坏话，顺序队列在 入队列 的时候可以保持O(1)的时间复杂度，而在 出队列 的时候队头后边的元素需要依次往前移动，以保证队头不为空,时间复杂度就变成了O(n);
为什么出队列时一定要全部移动呢，那么我们是否可以解决 出队列 所带来的问题呢，当然可以。
如果不去限制队列的元素必须存储在数组的前n个单元这一条件，出队的性能就会大大增加。这也就意味着队头不一定位于index=0的位置了。
假设是长度为5的数组，初始状态，空队列如所示，front与 rear指针均指向下标为0的位置。然后入队a1、a2、a3、a4, front指针依然指向下标为0位置，而rear指针指向下标为4的位置。
出队a1、a2，则front指针指向下标为2的位置，rear不变，如下图所示，再入队a5，此时front指针不变，rear指针移动到数组之外。嗯？数组之外，那将是哪里？
如上图所示，添加a5元素之后，rear已经无家可归了，于此同时0和1位置的空间却被拜拜浪费了，这个中情况被称之为 假溢出 。
为了解决 假溢出 的情况也就引出了我们接下来要讲的 循环队列 。
接着上图的来讲，为了把无家可归的rear有个好的落脚点，我们就把它放置在index=0的位置。
但是如果继续进行入队操作的话，比如继续插入a6、a7，则rear指针就与front指针重合，同时指向下标为2的位置。
此时问题又出来了，我们刚才说，空队列时，等于rear，现在当队列满时，也是from等于rear，那么如何判断此时的队列究竟是空还是满呢？
办法一 是设置一个标志变量flag，当front == rear,且flag = 0时为队列空，当front == rear,且flag= 1时为队列满。
办法二 是当队列空时，条件就是from = rear,当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。 如下图所示，我们就认为此队列已经满了，也就是说，我们不允许上图情况出现。
在第二种情况下，由于rear可能比front大，也可能比front小，所以尽管它们只相差一个位置时就是满的情况，但也可能是相差整整一圈。所以若队列的最大尺寸为QueueSize，那么队列满的条件是(rear+1) %QueueSize == front (取模“%的目的就是为了整合rear与front大小为一个问题)。
比如上面这个例子， QueueSize = 5，当 front=0，而 rear=4, (4+1) %5 = 0，所以此时队列满。再比如，front = 2而rear =1。(1 + 1) %5 = 2，所以此时 队列也是满的。而对于下图, front = 2而rear= 0, (0+1) %5 = 1，1!=2,所以此时队列并没有满。
另外，当rear > front时，此时队列的长度为rear—front。但当rear < front时，队列长度分为两段，一段是QueueSize-front，另一段是0 + rear，加在一起，队列长度为rear-front + QueueSize，因此通用的计算队列长度公式为：
(rear—front + QueueSize) % QueueSize
从上面的图我们不难看出顺序存储存在着数组可能会溢出的问题，所以也就引出了链式存储结构。
在链队列中，队头指针指向头结点，队尾指针指向终端结点，一个普通的链队列如下图所示：
当队列为空时，front和rear都指向头结点。
绛旓細闃熷垪鏄竴绉嶇壒娈婄殑绾挎鏁版嵁缁撴瀯銆傞槦鍒楁槸涓绉嶅厛杩涘厛鍑虹殑鏁版嵁缁撴瀯锛屽畠閬靛惊鐗瑰畾鐨勬搷浣滆鍒欍傚湪杩欑鏁版嵁缁撴瀯涓紝鏂板厓绱犵殑娣诲姞鎬绘槸鍦ㄩ槦鍒楃殑鏈熬杩涜锛岃屽垹闄ゆ搷浣滄绘槸鍦ㄩ槦鍒楃殑寮濮嬨傝繖涓繃绋嬩笌鏃ュ父鐢熸椿涓殑鎺掗槦鍦烘櫙闈炲父鐩镐技銆傚厛鏉ョ殑浜哄厛鏈嶅姟锛屽悗鏉ョ殑浜哄悗鏈嶅姟锛屼繚璇佷簡鏁版嵁鐨勯『搴忔с傝繖绉嶇壒鎬т娇寰楅槦鍒楀湪璁稿鍦烘櫙涓緱...
绛旓細閾鹃槦鏄寚閲囩敤閾惧紡瀛樺偍缁撴瀯瀹炵幇鐨闃熷垪銆傞氬父閾鹃槦鐢ㄥ崟閾捐〃鏉ヨ〃绀猴紝涓涓摼闃熸樉鐒堕渶瑕佷袱涓垎鍒寚绀哄澶村拰闃熷熬鐨勬寚閽堬紙鍒嗗埆绉颁负澶存寚閽堝拰灏炬寚閽堬級鎵嶈兘鍞竴纭畾銆備负浜嗘搷浣滄柟渚匡紝鍚岀嚎鎬ц〃鐨勫崟閾捐〃涓鏍凤紝涓洪摼闃熸坊鍔犲ご缁撶偣锛屽苟瑙勫畾澶存寚閽堝缁堟寚鍚戝ご缁撶偣銆傞摼闃熷垪瀛樺偍缁撴瀯琛ㄧず濡備笅锛氶摼闃熸搷浣滃嵆涓哄崟閾捐〃鎻掑叆鍜屽垹闄ゆ搷浣...
绛旓細闃熷垪 涓绉嶇壒娈婄殑 绾挎ц〃 锛屼篃鏄父瑙佺殑涓绉鏁版嵁绫诲瀷銆傜壒娈婁箣澶勫湪浜庡畠鍙兘鍦ㄨ〃鐨勫墠绔(front)杩涜鍒犻櫎锛岃屽湪琛ㄧ殑鍚庣(rear)杩涜鎻掑叆鎿嶄綔銆傝繘琛屾彃鍏ユ搷浣滅殑绔О涓 闃熷熬 锛岃繘琛屽垹闄ゆ搷浣滅殑绔О涓 闃熷ご 銆傞槦鍒 鍙堢О涓哄厛杩涘厛鍑猴紙FIFO鈥攆irst in first out锛夌嚎鎬ц〃銆傜嚎鎬ц〃 鍒嗕负 椤哄簭瀛樺偍 鍜 閾惧紡瀛樺偍 ...
绛旓細鏁版嵁缁撴瀯鏄寚鐩镐簰涔嬮棿瀛樺湪涓绉嶆垨澶氱 鐗瑰畾鍏崇郴 鐨勬暟鎹厓绱犵殑 闆嗗悎 涓锛闃熷垪 鐗圭偣锛氬厛杩涘厛鍑猴紙FIFO: first in first out锛夋瘮濡傦細鎺掗槦涔扮エ锛屼細鏈夐槦鍒楀ご锛岄槦鍒楀熬锛岄槦鍒楀ご鐨勪汉鍏堜拱鍒扮エ锛屽厛绂诲紑锛岄槦鍒楀熬鐨勪汉鍚庝拱绁紝鍚庣寮銆傞槦鍒楀垎涓猴細鏅氶槦鍒楋紝鐜舰闃熷垪 鍐呭瓨浣跨敤涓婃槸鍗佸垎楂樻晥鐨勶紝鍙互鍏呭垎鐢ㄥ埌姣忎釜...
绛旓細鏁版嵁缁撴瀯锛氭爤涓闃熷垪鐨勬繁搴﹁В鏋 鏍堬紝杩欎釜鏈婧愯嚜鎷変竵鏂"staurus"锛屾剰涓"鐭涘皷"锛屽舰璞″湴鎻忕粯浜嗗叾鍍忕煕灏栦竴鏍峰彧鍏佽鍦ㄤ竴绔繘鍑虹殑鐗圭偣銆傚畠鏄嚎鎬ф暟鎹粨鏋勭殑涓绉嶏紝閬靛惊FILO锛團irst In Last Out锛屽厛杩涘悗鍑猴級鍘熷垯锛屽鍚屽瓙寮瑰嚭鑶涚殑椤哄簭銆備富瑕佹湁椤哄簭鏍堝拰閾炬爤涓ょ瀹炵幇鏂瑰紡銆備笌涔嬬浉瀵圭殑鏄槦鍒楋紝瀹冮伒寰殑鏄疐IFO...
绛旓細Java闈㈣瘯锛鏁版嵁缁撴瀯涔嬮槦鍒鐨勪娇鐢ㄩ槦鍒楀湪Java闈㈣瘯涓崰鎹噸瑕佸湴浣嶏紝瀹冩槸鏁版嵁缁撴瀯涓殑閲嶈缁勬垚閮ㄥ垎锛岀壒鍒槸闃熷垪鐨勫垎绫汇佹柟娉曞拰瀹炰緥搴旂敤銆傞槦鍒椾富瑕佹湁涓変釜涓昏绫诲埆锛氶樆濉為槦鍒楀拰闈為樆濉為槦鍒楋紝浠ュ強浼樺厛绾ч槦鍒椼傞樆濉為槦鍒桞lockingQueue锛屽LinkedBlockingQueue鍜孉rrayBlockingQueue锛屾彁渚涗簡绾跨▼瀹夊叏鐨勬彃鍏ュ拰鍒犻櫎鎿嶄綔锛屽綋闃熷垪婊℃垨...
绛旓細閫氳繃閫昏緫涓婄殑寰幆鍒╃敤绌洪棿銆傞摼琛ㄥ疄鐜板垯鏈夊崟閾捐〃鍜屽弻鍚戦摼琛ㄧ殑閫夋嫨锛屽叾涓甫澶磋妭鐐瑰拰灏炬寚閽堢殑鍗曢摼琛ㄦ槸鏈甯哥敤涓旀晥鐜囪緝楂樼殑鏂规銆傚弻鍚戦槦鍒楋紝濡侫rrayDeque锛屾彁渚涗簡闃熷ご鍜岄槦灏炬搷浣滐紝鏄槦鍒楀拰鏍堢殑缁撳悎浣擄紝闈炲父瀹炵敤銆傛荤粨鏉ヨ锛岀悊瑙闃熷垪鏁版嵁缁撴瀯鐨勫叧閿湪浜庢帉鎻″厛杩涘厛鍑虹殑姒傚康锛屼互鍙婂浣曠敤鏁扮粍鎴栭摼琛ㄨ繘琛屽疄闄呮搷浣溿
绛旓細缁撴瀯鐗圭偣 1銆佸潎鍖鎬э細铏界劧涓嶅悓鏁版嵁琛ㄧ殑鏁版嵁鍏冪礌鍙互鏄悇绉嶅悇鏍风殑锛屼絾瀵逛簬鍚屼竴绾挎ц〃鐨勫悇鏁版嵁鍏冪礌蹇呭畾鍏锋湁鐩稿悓鐨勬暟鎹被鍨嬪拰闀垮害銆2銆佹湁搴忔э細鍚勬暟鎹厓绱犲湪绾挎ц〃涓殑浣嶇疆鍙彇鍐充簬瀹冧滑鐨勫簭鍙凤紝鏁版嵁鍏冪礌涔嬪墠鐨勭浉瀵逛綅缃槸绾挎х殑锛屽嵆瀛樺湪鍞竴鐨勨滅涓涓滃拰鈥滄渶鍚庝竴涓濈殑鏁版嵁鍏冪礌锛岄櫎浜嗙涓涓拰鏈鍚庝竴涓...
绛旓細闃熷垪锛屽鍚孉rrayList銆丼tack鍜孡inkList锛屾槸涓绉嶉伒寰厛杩涘厛鍑(FIFO)鎵ц椤哄簭鐨勭嚎鎬鏁版嵁缁撴瀯銆傛兂璞′竴涓嬶紝瀹冨氨鍍忎竴涓祫婧愪娇鐢ㄨ呯殑闃熷垪锛屼紭鍏堝鐞嗛槦鍒楀ご閮ㄧ殑璇锋眰銆備笌ArrayList涓嶅悓锛岄槦鍒桻ueue鐨勭壒鎬у湪浜庡叾鎿嶄綔鐨勭壒瀹氭э細鍙兘鍦ㄩ槦鍒楀ご閮ㄦ墽琛屽垹闄わ紙鍗抽闃熸搷浣滐級锛屽搴斾簬ArrayList鐨勯殢鏈烘彃鍏ュ拰鍒犻櫎锛岃屽湪闃熷垪灏鹃儴娣诲姞...
绛旓細闃熷垪鐨勫畾涔 闃熷垪锛圦ueue锛変篃鏄竴绉嶈繍绠楀彈闄愮殑绾挎ц〃 瀹冨彧鍏佽鍦ㄨ〃鐨勪竴绔繘琛屾彃鍏 鑰屽湪鍙︿竴绔繘琛屽垹闄 鍏佽鍒犻櫎鐨勪竴绔О涓洪槦澶达紙Front锛 鍏佽鎻掑叆鐨勪竴绔О涓洪槦灏撅紙Rear锛 闃熷垪鐨勪慨鏀规槸鎸夊厛杩涘厛鍑虹殑鍘熷垯杩涜鐨 鍥犳 闃熷垪鍙堢О涓哄厛杩涘厛鍑猴紙First In First Out锛夌殑绾挎ц〃 绠绉颁负FIFO琛 闃熷垪鐨勫熀鏈...
