這是一道很典型的隊列題目，因為題目中很明顯的說：“若內存中已存入 M 個單詞，軟件會清空最早進入內存的那個單詞，騰出單元來，存放新單詞。”非常符合隊列先進先出的思想，所以我們可以用隊列來模仿內存。

然后值得考慮的一個問題是：我們如何快速的判斷當前這個單詞是否在內存中呢？

如果遍歷內存的話，時間的消耗是O(m)的，但我們注意到題目條件

“第二行為 N 個非負整數，按照文章的順序，每個數（大小不超過 1000）代表一個英文單詞。”

這說明最多也就只有1000個單詞（單詞都是以非負整數的形式表示），所以，我們可以使用Hash表來記錄當前內存中單詞是否存在，存在為1，不存在為0，這樣我們維護內存時同時維護Hash表，這樣就可以用O(1)的時間來判斷單詞是否在內存中了。

#include <iostream>
#include <queue>
using namespace std;
queue<int> mem; //隊列模擬內存 
int Hash[1005]; //用于快速判斷內存中是否存在單詞 
int main()
{int m,n;int ans=0;int letter;//單詞 cin>>m>>n;for(int i=1;i<=n;i++){cin>>letter;if(Hash[letter]==0){//內存中沒有 ans++;//查字典mem.push(letter);Hash[letter]=1;//放入內存 //注意無論內存滿沒滿，都要先放進隊列里，然后再對內存做判斷 if(mem.size()>m){//內存滿了int temp=mem.front();Hash[temp]=0;mem.pop();//清空最早進入內存的單詞  } } }cout<<ans; return 0;
}

經典的約瑟夫環問題，在這里我們選擇采用list來模擬這個過程，整個過程比較簡單，主要要掌握list的增刪與迭代器遍歷的使用。

#include <iostream>
#include <list>
using namespace std;
list<int> circle;
int main()
{	int n,m;cin>>n>>m;for(int i=1;i<=n;i++) circle.push_back(i);//圍成一圈 list<int>::iterator it = circle.begin();//迭代器 while(circle.size()>1){for(int i=1;i<m;i++){//模擬報數過程,注意這里自己也算個數,所以<m即可 it++;if(it==circle.end()) it=circle.begin();//到末尾了就重新去到頭 } cout<<*it<<" ";list<int>::iterator next = ++it;//記錄下一個將指向的位置 if(next==circle.end()) next=circle.begin();circle.erase(--it);//刪除當前位置需要的數 it=next;}cout<<*it;return 0;
} 

這題是利用單調隊列解決滑動窗口的模板題。我們這里用雙端隊列（deque）來模擬滑動窗，雙端隊列的特點是可以從頭出也可以從尾出。我們以維護窗口最小值的代碼為例，來講解一下維護的過程：

首先看隊列是否為空，如果空的話，當前元素就可以入隊（不過在這里我們在隊列中存儲下標即可，為什么呢？因為這樣方便我們判斷哪些數超出了窗口范圍了），

如果隊不空，就要做判斷，如果當前隊尾元素比當前i指向的元素小，那就保留，否則就要出隊，給i指向的元素讓位，在這種維護規則下，我們隊列里的數據，從隊頭到隊尾，就都是單調遞增的，故而稱之為單調隊列，那誰是當前窗口最小的呢？顯然是隊頭。

那么如何判斷當前隊頭是不是在窗口內呢？因為i是窗口現在掃描到的最新的位置，k是窗口長度，所以窗口的首位置就應該是i-k+1，所以如果隊頭比i-k+1還小，那就肯定不在窗口內，直接從隊頭出隊。

i=k時第一個窗口就填滿了，故而i>=k時窗口總是滿的，可以輸出。

#include <iostream>
#include <queue>
using namespace std;
const int N=1e6+10;
int a[N];
deque<int> dq;//雙端隊列模擬滑動窗 
int main()
{	int n,k;cin>>n>>k;for(int i=1;i<=n;i++) cin>>a[i];//維護最窗口最小值for(int i=1;i<=n;i++){while(!dq.empty()&&a[dq.back()]>a[i]) dq.pop_back();dq.push_back(i);while(dq.front()<i-k+1) dq.pop_front();if(i>=k) cout<<a[dq.front()]<<" ";//窗口已經滿了，可以輸出} cout<<endl;dq.clear();//清空隊列 //維護窗口最大值for(int i=1;i<=n;i++){while(!dq.empty()&&a[dq.back()]<a[i]) dq.pop_back();dq.push_back(i);while(dq.front()<i-k+1) dq.pop_front();if(i>=k) cout<<a[dq.front()]<<" ";//窗口已經滿了} return 0;	
} 

本題是單調棧經典題目

單調棧的應用場景：通常是一維數組，要尋找任一個元素的右邊或者左邊第一個比自己大或者小的元素的位置，此時我們就要想到可以用單調棧了。

感覺單調棧的想法和單調隊列的很像，題目要求向右看齊，即找任意一個元素的右邊第一個比自己大的元素，這時我們就可以利用單調棧。

首先，找右邊比自己大的就倒序遍歷數據，在棧不空的情況下，如果當前元素大于棧頂元素，那么棧頂元素就不是其仰望的對象，故棧頂元素出棧，直到棧頂元素比當前元素大了，那此時棧頂元素即為當前元素右邊最近的仰望對象，這樣我們維護出來的棧從棧頂到棧底總是單調遞增的，故而稱為單調棧。請讀者自己模擬一遍這個過程，就會非常清楚，單調棧在其中的應用。

#include <iostream>
#include <stack>
using namespace std;
const int N=1e5+10;
int h[N];//存儲奶牛們的身高 
int ans[N];//存放答案
stack<int> st;//單調棧 
int main()
{int n;cin>>n;for(int i=1;i<=n;i++) cin>>h[i];for(int i=n;i>=1;i--){//因為是向右看齊，所以我們倒序遍歷 //注意是找最近的仰望對象，所以等于的也要出棧 while(!st.empty()&&h[i]>=h[st.top()]) st.pop();if(st.empty()) ans[i]=0;//棧空，證明沒有仰望對象了else ans[i]=st.top();//棧不空，說明現在棧頂是它的仰望對象 st.push(i);//入棧，存的是下標} for(int i=1;i<=n;i++) cout<<ans[i]<<endl; return 0; 
}

本題是優先隊列的經典應用。

題目要求我們找出能將所有堆果子合并為一堆果子，并且要求體力值最小。讀完題目我們不難發現，最佳的方案其實就是每次選取兩堆最小數目的果子進行合并，那我們如何找到兩堆最小的果子呢，第一個想法是排序，但是每次都要排序實在是太過麻煩，而且每次合并后又會產生新的一堆果子，所以如果有這么一個數據結構，我每次放數據進去就會自動排序就好了。

誒！還真有，優先隊列可以做到，它可以進行自動排序，對于這道題，我們設置一個小頂堆，每次找兩個最小數量的果子，就是取兩次堆頂，然后合并后放回堆中，直到堆里只有一個元素，就是剩一堆的時候，就結束。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int main()
{int n,x;int ans=0;priority_queue<int,vector<int>,greater<int> > q;//小頂堆 cin>>n;while(n--)//輸入 {cin>>x;q.push(x); } while(q.size()!=1)//當只剩下一堆果子時循環結束 {int a=q.top(); //從堆頂取出最小的兩堆合并 q.pop();int b=q.top();q.pop();ans+=a+b;q.push(a+b);}cout<<ans;return 0;
}

優先隊列太重要了，我們再練習一道有關優先隊列結構體排序的題目。

這道題的意思其實就是給你N條帶A，B，C參數的式子，然后讓你不斷變化變量x（從1開始，每次自增1），然后找出m個最小的值。

所以最主要的地方還是在找最小，我們可以這樣做，設計一個node結構體來存儲式子的ABC參數，和變量X與函數值Y，然后創建一個節點類型為node類型的優先隊列（所以我們要掌握，結構體優先隊列怎么控制小頂堆），然后我們每次取堆頂，因為堆頂是最小的，然后取出來之后自增變量x，然后更新y，重新放回堆里。然后重復這個過程。

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef struct node{ int a;int b;int c;int x;int y;//函數值 
}node;
bool operator <(const node &a,const node &b){return a.y>b.y;//最小值優先 
} 
int fun(node p){return p.a*p.x*p.x+p.b*p.x+p.c;
}
const int N=1e4+5;
node a[N];
int main()
{int n,m; vector<int> ans;priority_queue<node> que;//找最小函數值 cin>>n>>m;for(int i=0;i<n;i++){cin>>a[i].a>>a[i].b>>a[i].c;a[i].x=1;a[i].y=fun(a[i]);que.push(a[i]);}while(ans.size()<m){node temp=que.top();que.pop();ans.push_back(temp.y);temp.x++;temp.y=fun(temp);que.push(temp);}for(int i=0;i<ans.size();i++) cout<<ans[i]<<" ";return 0;
}