C++ Queues(隊列)C++隊列是一種容器適配器，它給予程序員一種先進先出(FIFO)的數據結構。
1.back() 返回一個引用，指向最后一個元素
2.empty() 如果隊列空則返回真
3.front() 返回第一個元素
4.pop() 刪除第一個元素
5.push() 在末尾加入一個元素
6.size() 返回隊列中元素的個數
隊列可以用線性表(list)或雙向隊列(deque)來實現(注意vector container 不能用來實現queue，因為vector 沒有成員函數pop_front!)：
queue<list<int>> q1;
queue<deque<int>> q2;
其成員函數有“判空(empty)” 、“尺寸(Size)” 、“首元(front)” 、“尾元(backt)” 、“加入隊列(push)” 、“彈出隊列(pop)”等操作。
例：
1 int main()
2 {
3 queue<int> q;
4 q.push(4);
5 q.push(5);
6 printf("%d\n",q.front());
7 q.pop();
8 }
C++ Priority Queues(優先隊列)
C++優先隊列類似隊列，但是在這個數據結構中的元素按照一定的斷言排列有序。
1.empty() 如果優先隊列為空，則返回真
2.pop() 刪除第一個元素
3.push() 加入一個元素
4.size() 返回優先隊列中擁有的元素的個數
5.top() 返回優先隊列中有最高優先級的元素
優先級隊列可以用向量(vector)或雙向隊列(deque)來實現(注意list container 不能用來實現queue，因為list 的迭代器不是任意存取iterator，而pop 中用到堆排序時是要求randomaccess iterator 的!)：
priority_queue<vector<int>, less<int>> pq1; // 使用遞增less<int>函數對象排序
priority_queue<deque<int>, greater<int>> pq2; // 使用遞減greater<int>函數對象排序
其成員函數有“判空(empty)” 、“尺寸(Size)” 、“棧頂元素(top)” 、“壓棧(push)” 、“彈棧(pop)”等。
例：
1 #include <iostream>
2 #include <queue>
3 using namespace std;
4
5 class T {
6 public:
7 int x, y, z;
8 T(int a, int b, int c):x(a), y(b), z(c)
9 {
10 }
11 };
12 bool operator < (const T &t1, const T &t2)
13 {
14 return t1.z < t2.z; // 按照z的順序來決定t1和t2的順序
15 }
16 main()
17 {
18 priority_queue<T> q;
19 q.push(T(4,4,3));
20 q.push(T(2,2,5));
21 q.push(T(1,5,4));
22 q.push(T(3,3,6));
23 while (!q.empty())
24 {
25 T t = q.top();
26 q.pop();
27 cout << t.x << " " << t.y << " " << t.z << endl;
28 }
29 return 1;
30 }
輸出結果為(注意是按照z的順序從大到小出隊的)：
3 3 6
2 2 5
1 5 4
4 4 3
再看一個按照z的順序從小到大出隊的例子：
1 #include <iostream>
2 #include <queue>
3 using namespace std;
4 class T
5 {
6 public:
7 int x, y, z;
8 T(int a, int b, int c):x(a), y(b), z(c)
9 {
10 }
11 };
12 bool operator > (const T &t1, const T &t2)
13 {
14 return t1.z > t2.z;
15 }
16 main()
17 {
18 priority_queue<T, vector<T>, greater<T> > q;
19 q.push(T(4,4,3));
20 q.push(T(2,2,5));
21 q.push(T(1,5,4));
22 q.push(T(3,3,6));
23 while (!q.empty())
24 {
25 T t = q.top();
26 q.pop();
27 cout << t.x << " " << t.y << " " << t.z << endl;
28 }
29 return 1;
30 }
輸出結果為：
4 4 3
1 5 4
2 2 5
3 3 6
如果我們把第一個例子中的比較運算符重載為： bool operator < (const T &t1, const T &t2) { return t1.z > t2.z; // 按照z的順序來決定t1和t2的順序} 則第一個例子的程序會得到和第二個例子的程序相同的輸出結果。
posted on 2012-06-05 13:21
王海光 閱讀(49390)
評論(0) 編輯 收藏 引用 所屬分類:
STL