0基礎學演算法 第三彈 隊列
- 2020 年 3 月 17 日
- 筆記
接觸過一點oi的應該都知道，在初賽試題中，總會考一些關於棧，隊列，類的知識，而因為隊列或棧需要額外的頭文件，所以有的同學就不知道這方面的內容，然而這個隊列(棧)也是一個非常常用的一個技巧類的東西，你要是會有可能就比別人搶到先機，那麼，今天我就教大家搶奪先機。在搶奪先機之前，可不可以先關注我呢，關注我可以持續為你帶來多樣的演算法知識?
首先我們學隊列的話，要先搞清楚他的運行方式，因為他很容易和棧搞混，他和棧的區別就在於，隊列是先進先出，棧是先進後出，跟大家解釋一下吧，在隊列中(或棧)是沒有下標的，不像數組裡可以定點打擊，把對應下標的值取出來，他們只能按照順序一個一個取，放當然也是順序放入，給大家看一個圖就知道什麼意思了
這樣就很清晰了，大致了解他工作過程後我們就可以開始看程式碼了
今天我們主要是講隊列，棧會在下一篇博文講，如果你期待講棧的話，記得關注我
一，定義一個隊列
隊列和string一樣是需要額外的頭文件，也和他一樣是個數據類型，如果你要使用隊列，你需要先添加頭文件queue，然後再在程式中定義隊列，定義方法為queue<數據類型> 隊列名; 然後你就可以通過隊列名來調用隊列了。
二，隊列的溢出
如果還有新元素進行入隊列容易造成假溢出。
假溢出：順序隊列因多次入隊列和出隊列操作後出現的尚有存儲空間但是不能進行入隊操作的溢出。
真溢出：順序隊列的最大存儲空間已經存滿而又要求進行入隊列操作所引起的溢出。
事實上你基本不用擔心溢出的情況，首先是因為溢出情況並不多見，更重要的是如果你一直想著怎麼防止溢出，會阻斷你的思考
三，隊列的基本操作
隊列在經定義後，就可以進行一些基本操作了，基本操作包括入隊，出隊，判斷是否為空隊列，檢測有多少元素在其中，當然還有提取隊列頂部和底部的元素的操作，給大家綜合看一下程式碼的效果吧
#include<queue> using namespace std; int main(){ queue<int> q; q.empty(); //如果隊列為空返回true，否則返回false q.size(); //返回隊列中元素的個數 q.pop(); //刪除隊列首元素但不返回其值 q.front(); //返回隊首元素的值，但不刪除該元素 q.push(); //在隊尾壓入新元素 q.back(); // 返回隊列尾元素的值，但不刪除該元素 return 0; }
上面我是定義了一個q，並集合了他的常用的操作，但沒有進行輸出，當中的隊首指的是第一個入隊的，隊尾是最後一個入隊的，上面定義的隊列是整型的，你也可以定義長整型，字元型等等，而q.xxx指對隊列q調用函數xxx，別忘了在後面打括弧，大致熟悉了一下隊列的基本操作後就去實戰一下吧
洛谷實戰題講解
P1996https://www.luogu.com.cn/problem/P1996請獨立完成不要看題解，如果不會就繼續看我講解
我希望你是這的思考過的，不一定要想出來，但是請一定自己嘗試一番，不管你會也好，不會也罷，你都繼續看這篇博文就對了。
這道題應該是非常經典的，大家應該不僅在新人時期做過這題，之前數學課也有講過吧，約瑟夫問題的做法很多樣可以用數組做，或者模擬他的過程，但今天這道題，我要告訴你們，可以用隊列做！在做之前，確保你打開了約瑟夫問題，手上有筆紙，並編譯器沒有bug，確定之後，我們就開始吧。
這道題也是我新人時期做的題，首先，要輸入m和n兩個數，n決定了一圈有多少人，m決定了數幾個數出去一人，那麼肯定是要有計數的變數來不斷的數人出去啊，然後我們可以通過隊列將數到的人彈出去，好了，我們可以先用第一彈講過的流程圖來梳理一下
現在，思路已經很清晰了，那麼我們就來程式碼實現吧
#include <iostream> #include <queue> using namespace std; int main() { queue<int>q; int n,m,s=1; cin>>n>>m; for(int i=1;i<=n;i++) { q.push(i); } while(!q.empty()) { if (s==m) { cout<<q.front()<<" "; q.pop(); s=1; } else { q.push(q.front()); q.pop(); s++; } } return 0; }
你看，約瑟夫問題這麼容易的寫出來了，流程圖幫我們梳理了思路後程式碼實現都不是問題，重點是你思路要清晰，並可以熟練使用演算法，這樣做題效率就會很高。
今天的0基礎學演算法系列就到這裡吧，最後麻煩你點贊?，還有關注➕，關注我，會給你帶來更多的演算法學習，最後如果你想鞏固知識，洛谷上有題，最後再強調一遍，如果你喜歡我的部落格，請關注我，以後會有更多精彩內容
