数据结构与算法-队列
同样是线性表，队列也有类似线性表的各种操作，不同的就是插入数据只能在队尾进行，删除数据只能在队头进行。线性表有顺序存储和链式存储，栈是线性表，所以有这两种存储方式。同样，队列作为一种特殊的线性表，也同样存在这两种存储方式。
我们假设一个队列有n个元素，则顺序存储的队列需建立一个大于n的数组，并把队列的所有元素存储在数组的前n个单元，数组下标为0的一端即是队头。所谓的入队列操作，其实就是在队尾追加一个元素，不需要移动任何元素，因此时间复杂度为 。
与栈不同的是，队列元素的出列是在队头，即下标为0的位置，那也就意味着，队列中的所有元素都得向前移动，以保证队列的队头，也就是下标为0的位置不为空，此时时间复杂度为 。
可有时想想，为什么出队列时一定要全部移动呢，如果不去限制队列的元素必须存储在数组的前n个单元这一条件，出队的性能就会大大增加。也就是说，队头不需要一定在下标为0的位置，
为了避免当只有一个元素时，队头和队尾重合使处理变得麻烦，所以引入两个指针，front指针指向队头元素，rear指针指向队尾元素的下一个位置，这样当front等于rear时，此队列不是还剩一个元素，而是空队列。
假设是长度为5的数组，初始状态，空队列列如图所示，front与rear指针均指向下标为0的位置。然后入队a1、a2、a3、a4，front指针依然指向下标为0位置，而rear指针指向下标为4的位置。
出队a1、a2，则front指针指向下标为2的位置，rear不变，如图4-12-5的左图所示，再入队a5，此时front指针不变，rear指针移动到数组之外。嗯？数组之外，那将是哪里？如下图的右图所示。
假设这个队列的总个数不超过5个，但目前如果接着入队的话，因数组末尾元素已经占用，再向后加，就会产生数组越界的错误，可实际上，我们的队列在下标为0和1的地方还是空闲的。我们把这种现象叫做“假溢出”。
所以解决假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。
如果将rear的指针指向下标为0的位置，那么就不会出现指针指向不明的问题了，如下图所示。
接着入队a6，将它放置于下标为0处，rear指针指向下标为1处，如下图的左图所示。若再入队a7，则rear指针就与front指针重合，同时指向下标为2的位置，如下图的右图所示。
由于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。因此通用的计算队列满队公式为：
单是顺序存储，若不是循环队列，算法的时间性能是不高的，但循环队列又面临着数组可能会溢出的问题，所以我们还需要研究一下不需要担心队列长度的链式存储结构。
队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向终端结点。
空队列时，front和rear都指向头结点。
链队列的结构为：
初始化一个空队列
入队操作时，其实就是在链表尾部插入结点，如图所示。
出队操作时，就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需将rear指向头结点，如图所示。
对于循环队列与链队列的比较，可以从两方面来考虑，从时间上，其实它们的基本操作都是常数时间，即都为O(1)的，不过循环队列是事先申请好空间，使用期间不释放，而对于链队列，每次申请和释放结点也会存在一些时间开销，如果入队出队频繁，则两者还是有细微差异。对于空间上来说，循环队列必须有一个固定的长度，所以就有了存储元素个数和空间浪费的问题。而链队列不存在这个问题，尽管它需要一个指针域，会产生一些空间上的开销，但也可以接受。所以在空间上，链队列更加灵活。
总的来说，在可以确定队列长度最大值的情况下，建议用循环队列，如果你无法预估队列的长度时，则用链队列。
栈和队列也都可以通过链式存储结构来实现，实现原则上与线性表基本相同如图所示。
绛旓細閫昏緫缁撴瀯鏈4绉嶅熀鏈被鍨嬶細闆嗗悎銆佺嚎鎬х粨鏋勩佹爲褰缁撴瀯鍜鍥惧舰缁撴瀯銆傜嚎鎬ц〃鍜屾爲鏄渶甯哥敤鐨勪袱绉嶉珮鏁鏁版嵁缁撴瀯锛岃澶氶珮鏁堢殑绠楁硶閮借兘鐢ㄨ繖涓ょ鏁版嵁缁撴瀯鏉ヨ璁″疄鐜般備笅闈㈤氳繃瀹炰緥鏉ヨ繘涓姝ョ悊瑙ｅ悗3绫绘暟鎹粨鏋勩1.绾挎х粨鏋 濡傚浘1-2鎵绀虹殑鑻辨枃瀛楁瘝琛ㄦ弿杩扮殑閫昏緫缁撴瀯鏄嚎鎬х粨鏋勶紝琛ㄤ腑鐨勬瘡涓涓嫳鏂囧瓧姣嶆槸涓涓暟鎹厓绱犮傝琛...
绛旓細include <stack>:鏍 include <queue>:闃熷垪 杩欎釜闃熷垪閲岄潰杩樻湁涓涓猵riority_queue锛屼篃灏辨槸浼樺厛绾ч槦鍒楋紝瀹為檯鏄敤鍫嗗疄鐜扮殑 鑷充簬浜屽弶鏍戝槢锛屽叾涓湁涓猻et锛屽厓绱犲间笉寰楅噸澶嶏紝鍐呴儴鎸夊厓绱犲艰嚜鍔ㄦ帓搴忥紝澶у鏁版槸鐢ㄥ钩琛′簩鍙夋爲鏉ュ疄鐜扮殑(涔熷彲鑳芥槸绾㈤粦鏍戝疄鐜)锛屼絾鏄繖涓や釜閮藉苟涓嶆槸骞冲父鎰忎箟涓婄殑浜屽弶鏍 ...
绛旓細鏁版嵁缁撴瀯鍒嗕负8绫绘湁锛氭暟缁勩佹爤銆闃熷垪銆侀摼琛ㄣ佹爲銆佹暎鍒楄〃銆佸爢銆佸浘銆傛暟鎹粨鏋勬槸鎸囩浉浜掍箣闂村瓨鍦ㄧ潃涓绉嶆垨澶氱鍏崇郴鐨勬暟鎹厓绱犵殑闆嗗悎鍜岃闆嗗悎涓暟鎹厓绱犱箣闂寸殑鍏崇郴缁勬垚 銆1銆佹暟缁 鏁扮粍鏄彲浠ュ啀鍐呭瓨涓繛缁瓨鍌ㄥ涓厓绱犵殑缁撴瀯锛屽湪鍐呭瓨涓殑鍒嗛厤涔熸槸杩炵画鐨勶紝鏁扮粍涓殑鍏冪礌閫氳繃鏁扮粍涓嬫爣杩涜璁块棶锛屾暟缁勪笅鏍囦粠0寮濮嬨
绛旓細3銆侀亶鍘嗘暟鎹熷害涓嶅悓銆傛爤鍙兘浠庡ご閮ㄥ彇鏁版嵁锛屼篃灏辨渶鍏堟斁鍏ョ殑闇瑕侀亶鍘嗘暣涓爤鏈鍚庢墠鑳藉彇鍑烘潵锛岃屼笖鍦ㄩ亶鍘嗘暟鎹殑鏃跺欒繕寰椾负鏁版嵁寮杈熶复鏃剁┖闂达紝淇濇寔鏁版嵁鍦ㄩ亶鍘嗗墠鐨勪竴鑷存с闃熷垪鍒欎笉鍚岋紝瀹冨熀浜庡湴鍧鎸囬拡杩涜閬嶅巻锛岃屼笖鍙互浠庡ご鎴栧熬閮ㄥ紑濮嬮亶鍘嗭紝浣嗕笉鑳藉悓鏃堕亶鍘嗭紝鏃犻渶寮杈熶复鏃剁┖闂达紝鍥犱负鍦ㄩ亶鍘嗙殑杩囩▼涓笉褰卞儚鏁版嵁缁撴瀯...
绛旓細queue *q=锛坬ueue*锛塵alloc锛坰izeof锛坬ueue锛夛級锛//璇彞锛屽簲璇ユ斁鍦 锛宖or寰幆閲岄潰銆//鍥犱负 姣忔 閮借鐢宠鑺傜偣銆
绛旓細缂栫▼璇█涓庣▼搴忚璁★細瀛︿範涓绉嶆垨澶氱缂栫▼璇█锛堝C銆丆++銆丣ava銆丳ython绛夛級锛屾帉鎻＄紪绋嬬殑鍩烘湰璇硶銆佺紪绋嬭寖寮忓拰甯哥敤搴擄紝鍩瑰吇缂栫▼瀹炶返鑳藉姏銆備簩銆佹牳蹇冧笓涓氱煡璇 鏁版嵁缁撴瀯涓庣畻娉锛氬涔犲浣曟湁鏁堝湴缁勭粐鍜屽瓨鍌ㄦ暟鎹紝浠ュ強绠楁硶鍒嗘瀽鍜岃璁＄殑鍩烘湰鏂规硶銆傝繖鍖呮嫭鏁扮粍銆侀摼琛ㄣ佹爤銆闃熷垪銆佹爲銆佸浘绛夋暟鎹粨鏋勶紝浠ュ強鎺掑簭銆佹悳绱佸浘...
绛旓細绋嬪簭=鏁版嵁缁撴瀯+绠楁硶 闃熷垪鍜屽爢鏍堝氨鏄竴绉嶆暟鎹粨鏋勪簡锛屽叾浠栫殑杩樻湁閾捐〃銆佹爲绛夛紝鏄竴绉嶅瓨鍌ㄦ暟鎹殑褰㈠紡銆傚爢鏍堝氨鏄疄鐜板厛杩涘悗鍑虹殑鏁版嵁缁撴瀯锛屾瘮濡備竴绔紑鍙ｄ竴绔湁搴曠摱瀛愰噷锛屼綘鎶婇ゼ骞(鏁版嵁)浠庡乏绔斁鍏ョ摱瀛愪腑锛屾嬁楗煎共涔熻浠庡乏绔嬁锛岃屽厛鏀惧叆鐨勯ゼ骞叉渶鍚庢墠鑳藉彇鍑恒傞槦鍒楀氨鏄疄鐜板厛杩涘厛鍑虹殑鏁版嵁缁撴瀯锛屾瘮濡備竴涓袱绔兘...
绛旓細浜屻鏁版嵁缁撴瀯涓庣畻娉 鏁版嵁缁撴瀯鍜岀畻娉鏄紪绋嬩腑鐨勫叧閿绱犮傛暟鎹粨鏋勭爺绌舵暟鎹殑瀛樺偍鏂瑰紡锛屽鏁扮粍銆侀摼琛ㄣ佹爤銆闃熷垪銆佹爲鍜屽浘绛夈傜畻娉曞垯鏄В鍐崇壒瀹氶棶棰樼殑姝ラ搴忓垪銆傚涔犳暟鎹粨鏋勫拰绠楁硶鑳芥彁鍗囩紪绋嬫晥鐜囷紝瑙ｅ喅澶嶆潅闂銆備笁銆佽蒋浠跺紑鍙戝伐鍏蜂笌鐜 瀛︿範杞欢缂栫▼杩橀渶浜嗚В鍚勭寮鍙戝伐鍏峰拰鐜锛屽闆嗘垚寮鍙戠幆澧冦佺増鏈帶鍒剁郴缁熴...
绛旓細璁＄畻鏈虹瀛﹁仈鑰冧富瑕佹兜鐩鏁版嵁缁撴瀯涓庣畻娉銆佽绠楁満缃戠粶銆佹搷浣滅郴缁熶互鍙婅绠楁満缁勬垚鍘熺悊绛夊唴瀹广傝繖鏄绠楁満涓撲笟鑰冪爺鐨勫熀纭绉戠洰锛岃冨療鑰冪敓瀵硅绠楁満鍩虹鐭ヨ瘑鎺屾彙鐨勭▼搴﹀拰搴旂敤鑳藉姏銆備簩銆佹暟鎹粨鏋勪笌绠楁硶鐨勯噸瑕佹 鏁版嵁缁撴瀯涓庣畻娉曟槸璁＄畻鏈虹瀛﹁仈鑰冧腑鐨勬牳蹇冮儴鍒嗐傝繖涓绉戠洰涓昏鑰冨療鑰冪敓瀵瑰熀鏈暟鎹粨鏋勫鏁扮粍銆侀摼琛ㄣ佹爤銆闃熷垪銆佹爲銆...
绛旓細鍚屾椂鍙互鏇存柟渚跨殑鍦ㄩ亶鍘嗚繃绋嬩腑瀵逛簩鍙夋爲涓殑缁撶偣杩涜鎿嶄綔锛屼緥濡傚婊¤冻鏌愪釜鏉′欢鐨勫厓绱犺繘琛岃祴鍊肩瓑銆備娇鐢ㄨ妭鐐瑰璞′綔涓闃熷垪鎴愬憳涔熸槸鍙互瀹炵幇寰幆闃熷垪鐨勫嚭闃鍜鍏ラ槦鐨勶紝姣忔鍏ラ槦鏃跺皢瀵瑰簲缁撶偣鐨鏁版嵁鎷疯礉锛堣祴鍊硷級缁欏搴旂殑闃熷垪缁撶偣瀵硅薄鎴愬憳鍗冲彲锛屼絾鏄叾澶嶆潅搴︽樉鐒舵瘮鎸囬拡鏇撮珮锛岄拡瀵逛簩鍙夋爲鐨勭粨鐐硅闂搷浣滀篃娌℃湁閭ｄ箞鐏垫椿銆
