第8章隊列與deque類2025/6/171隊列的特點隊列的創(chuàng)建與獨特的函數隊列與回文串隊列與加密解密隊列與約瑟夫問題隊列與廣度搜索優(yōu)先隊列隊列與排隊8.1隊列的特點2025/6/172隊列擅長在線性表的頭、尾兩端實施刪除和添加操作，甚至可以把線性表實現成只在頭、尾兩端操作，所以人們也稱隊列是受限的線性表。入列時，最先進入的節(jié)點在隊頭，最后進入的節(jié)點在隊尾。出列時，從隊列的頭開始刪除節(jié)點，最后一個刪除的節(jié)點是隊尾的節(jié)點。隊列是一種先進先出的數據結構，簡稱FIFO（FirstInFirstout）8.1隊列的特點2025/6/173頭節(jié)點（隊頭）在左邊、尾節(jié)點（隊尾）在右邊。8.2隊列的創(chuàng)建與獨特函數2025/6/174std::deque是C++標準模板庫（StandardTemplateLibrary,STL）中的模板類，用于實現隊列這種數據結構，即提供先進先出的數據結構（也稱隊列是STL的容器之一），std::deque支持在隊列的兩端進行入列和出列操作（稱為雙端隊列）。需要注意，當std使用作用域運算符（也稱解析運算符））“：：”訪問deque時不要誤寫為str::Deque，即不可以將deque的首寫字母寫成大寫的D。稱std::deque類的實例（對象）為隊列，其中的節(jié)點的邏輯結構是線性結構。2025/6/1758.2隊列的創(chuàng)建與獨特函數1創(chuàng)建隊列使用std::deque類創(chuàng)建隊列時，必須要指定模板類中的參數類型的具體類型，類型是可以是C++允許的數據類型，比如int、float、char和類等，即指定隊列中節(jié)點里的數據的類型。例如，指定隊列deque的節(jié)點中的數據的類型是std::string類型：std::deque<str::string>queue;deque隊列棧的存儲方式是順序存儲，即使用數組管理節(jié)點，后面敘述中說隊列的節(jié)點中的數據或隊列中的數據都是正確的。注意：如果只在頭、尾端操作鏈表，就可以把鏈表當隊列來使用，那么這樣的隊列是鏈式存儲。2025/6/1768.2隊列的創(chuàng)建與獨特函數2獨特的函數

2025/6/1778.2隊列的創(chuàng)建與獨特函數2獨特的函數

2025/6/1788.2隊列的創(chuàng)建與獨特函數3單端隊列queuestd::queue是C++標準模板庫的隊列適配器，相對于雙端隊列std::deque，稱std::queue的實例是單端隊列，單端隊列std::queue只提供了隊列的基本操作接（只適配了雙端隊列的部分方法），如入列push()、出列pop()、返回隊頭數據front()，返回隊尾數據back(),但不提供從隊尾出列、從對頭入列的操作。因此，如果需要在隊列的兩端進行快速插入和刪除操作，包括從隊尾出列、對頭入列，可以使用雙端隊列std::deque；如果只需要隊列的基本操作，則可以使用單端隊列std::queue。創(chuàng)建單端隊列時，例如queueWithList,可以指定queueWithList的存儲方式是std:list,那么queueWithList將使用鏈式存儲（不可以指定雙端隊列的存儲方式是鏈式存儲）例如：std::queue<int,std::list<int>>queueWithList;2025/6/1798.2隊列的創(chuàng)建與獨特函數ch8_1.cpp例子1使用隊列的獨特函數ch8_1.cpp使用了隊列的獨特函數.8.3隊列與回文串2025/6/1710回文串是指和其反轉（倒置）相同的字符串，例如："racecar","123321"，"level”，"toot"，"civic"，"pop"，"eye"，"rotator"，"pip"都是回文串。我們曾在第3章例子4，使用遞歸方法判斷一個字符串是否是回文串。2025/6/17118.3隊列與回文串ch8_2.cpp例子2使用隊列也可以判斷一個字符串是否是回文串。將字符串中的全部字符按順序依次入列，然后開始分別從頭、尾出列，如果字符串是回文串，那么從頭出列的節(jié)點一定和從尾出列的節(jié)點相同，當隊列中剩余的節(jié)點數目不足2個時，停止出列。利用隊列判斷字符串是否是回文串讀者可以和第7章中的例7-2進行比較，分別體會棧和隊列的特點。8.4隊列與加密解密2025/6/1712用隊列可以方便地對字符串實施加密（解密）操作。出列的對象參與加密字符串中一個字符（出列的對象參與解密字符串中一個字符），然后再重新入列，一直到字符串中的字符全部被加密完畢（字符串中的全部字符被解密完畢）。2025/6/17138.4隊列與加密解密encryption_decryption.cpp例子3ch8_3.cpp使用隊列加密、解密字符串encryption_decryption.cpp中的函數使用隊列加密、解密字符串。8.5隊列與約瑟夫問題2025/6/1714簡單再重復一下約瑟夫問題：若干個人圍成一圈，從某個人開始順時針（或逆時針）數到第3個人，該人從圈中退出，然后繼續(xù)順時針（或逆時針）數到第3個人，該人從圈中退出，依此類推，程序輸出圈中最后剩下的一個人。

2025/6/17158.5隊列與約瑟夫問題joseph.cpp例子4和第4章的例4-11以及第5章的例5-3相比，使用隊列的算法不僅更加容易理解，而且所實現的代碼也具有很好的可讀性。ch8_4.cpp使用隊列解決約瑟夫問題8.6隊列與廣度搜索2025/6/1716廣度優(yōu)先搜索（BreadthFirstSearch，BFS）是圖的另一種遍歷方式，與深度搜索（DFS）相對，是以廣度優(yōu)先進行搜索。其特點是先訪問圖的頂點，然后廣度優(yōu)先：依次進行被訪問點的鄰接點，一層一層訪問，直至訪問完所有節(jié)點或搜索到指定的節(jié)點，算法結束。棧的特點是后進先出，恰好能體現深度優(yōu)先。隊列的特點是，先進先出，恰好體現廣度優(yōu)先。8.6隊列與廣度搜索2025/6/1717

8.6隊列與廣度搜索2025/6/1718排雷算法描述如下：①將開始的排雷點入列，進行②②檢查隊列是否是空列，如果為空（雷就都被排除了）進行④，否則進行③③隊列進行出列操作，將出列點的東西南北方向，沒有被排雷的點入列，然后檢查出列點是否是雷，并標記此點已排雷：如果是雷給出一個排雷的標記，如果是路給出一個路的標記，進行②④結束。2025/6/17198.6隊列與廣度搜索point.cpp例子5ch8_5.cpp

注不可以一行、一行的排雷，這樣做顯然沒有體現廣度優(yōu)先。用廣度優(yōu)先搜索算法進行排雷deminers.cpp8.7優(yōu)先隊列2025/6/1720std::priority_queue是C++標準庫中實現優(yōu)先隊的模板類。優(yōu)先隊列中的數據不是按入列順序出列、而是按優(yōu)先級別出列，級別高的先于級別低的出列。例如，對于int型優(yōu)先隊列，最大的整數最先出列（整數越大、優(yōu)先級別越高），如果隊列中的數據是對象，創(chuàng)建對象的類重載小于關系運算(關于重載運算符見附錄A),以便確定類的對象的優(yōu)先級。優(yōu)先隊列使用top()返回隊列中優(yōu)先級別最高的節(jié)點中的數據，但不刪除該節(jié)點。2025/6/17218.7優(yōu)先隊列例子6使用優(yōu)先隊列ch8_6.cppch8_6.cpp的Student對象按數學成績比較優(yōu)先級別，優(yōu)先隊列讓Student對象按著數學成績的優(yōu)先級別依次出列。8.8隊列與排隊2025/6/1722假設一個營業(yè)廳有2個服務窗口，低峰期間有一個窗口營業(yè)，高峰期間有2個窗口營業(yè)，每個窗口為一位顧客辦理業(yè)務的耗時不盡相同。程序模擬營業(yè)廳服務若干顧客，觀察兩個窗口分別服務了多少顧客，停止營業(yè)后，看看還有多少顧客未能辦理業(yè)務。2025/6/17238.8隊列與排隊例子7多線程ch8_7.cppC++11新增了<thread>線程庫，使得C++程序可以更加方便地創(chuàng)建線程、用于模擬實