STL提供3種特殊的數據結構：棧，隊列與優先隊列

1.棧：符合“后進后出”，有push和pop兩種操作

其中push把元素壓入棧頂，而pop從棧頂把元素“彈出”。頭文件<stack>

聲明棧：stack<int>s;

#include<iostream> #include<stack> #include<set> #include<vector> #include<map> using namespace std; typedef set<int> myset; map<myset,int> IDcache;//把集合映射成ID vector<myset> Setcache;//根據ID取集合 //查找集合的ID,如果找不到分配一個新ID int ID(myset x) {if(IDcache.count(x))return IDcache[x];Setcache.push_back(x);return IDcache[x]=Setcache.size()-1;} #define ALL(x) x.begin(),x.end() #define INS(x) inserter(x,x.begin()) int main() {stack<int> s;int n;cin>>n;for(int i=0;i<n;i++){string op;cin>>op;if(op[0]=='p') //push操作 s.push(ID(myset()));else if(op[0]=='D')s.push(s.top());else{myset x1=Setcache[s.top()];s.pop();myset x2=Setcache[s.top()];s.pop();myset x;if(op[0]=='U')set_union(ALL(x1),ALL(x2),INS(x));if(op[0]=='I')set_intersection(ALL(x1),ALL(x2),INS(x));if(op[0]=='A'){x=x2;x.insert(ID(x1));}s.push(ID(x));}cout<<Setcacher[s.top()].size()<<endl;} } View Code

?

2.優先隊列：是一種抽象數據類型，行為有些像隊列，但先進隊列的元素不是先進隊列的元素，而是隊列中優先級最高的元素，這樣就可以允許類似于“急診病人插隊”這樣的事件發生。

頭文件:#include<queue>

聲明優先隊列：priority_queue<int>pq;

出隊列的方式：由于出隊元素并不是最先進隊的元素，出隊的方法由queue的front()變成了top().

在一些特殊情況下，需要使用自定義方式定義比較優先級。? ?

只要元素定義了“小于”運算符，就可以使用優先隊列。

對于一些常見的優先隊列，STL提供了

例如：要實現一個“個位數大的整數優先級反而小”的優先隊列。

可以定義一個結構體cmp，重載“（）”運算符，使其“看上去”想一個函數（在c++中，重載了“（）”運算符的類或結構體叫做仿函數），然后用“priority_queue<int,vector<int>,cmp> pq”的方式定義

struct cmp{

bool operator() (const int a,const int b) const{

return a%10>b%10;

}

};

?

轉載于:https://www.cnblogs.com/Aiahtwo/p/10358104.html

總結

以上是生活随笔為你收集整理的栈，队列与优先队列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。