stack/queue的使用方法

stack/queue的使用方法

stack(棧)和queue(隊列)也是在程式設計中經常會用到的資料容器，STL為我們提供了友善的

stack(棧)的queue(隊列)的實作。

準确地說，STL中的stack和queue不同于vector、list等容器，而是對這些容器的重新包裝。

這裡我們不去深入讨論STL的stack和queue的實作細節，而是來了解一些他們的基本使用。

1、stack

stack模闆類的定義在<stack>頭檔案中。

stack模闆類需要兩個模闆參數，一個是元素類型，一個容器類型，但隻有元素類型是必要

的，在不指定容器類型時，預設的容器類型為deque。

定義stack對象的示例代碼如下：

stack<int>s1;

stack<string>s2;

stack的基本操作有：

入棧，如例：s.push(x);

出棧，如例：s.pop();注意，出棧操作隻是删除棧頂元素，并不傳回該元素。

通路棧頂，如例：s.top()

判斷棧空，如例：s.empty()，當棧空時，傳回true。

通路棧中的元素個數，如例：s.size()

2、queue

queue模闆類的定義在<queue>頭檔案中。

與stack模闆類很相似，queue模闆類也需要兩個模闆參數，一個是元素類型，一個容器類

型，元素類型是必要的，容器類型是可選的，預設為deque類型。

定義queue對象的示例代碼如下：

queue<int>q1;

queue<double>q2;

queue的基本操作有：

入隊，如例：q.push(x);将x接到隊列的末端。

出隊，如例：q.pop();彈出隊列的第一個元素，注意，并不會傳回被彈出元素的值。

通路隊首元素，如例：q.front()，即最早被壓入隊列的元素。

通路隊尾元素，如例：q.back()，即最後被壓入隊列的元素。

判斷隊列空，如例：q.empty()，當隊列空時，傳回true。

通路隊列中的元素個數，如例：q.size()

3、priority_queue

在<queue>頭檔案中，還定義了另一個非常有用的模闆類priority_queue(優先隊列）。優先隊

列與隊列的差别在于優先隊列不是按照入隊的順序出隊，而是按照隊列中元素的優先權順序

出隊（預設為大者優先，也可以通過指定算子來指定自己的優先順序）。

priority_queue模闆類有三個模闆參數，第一個是元素類型，第二個容器類型，第三個是比

較算子。其中後兩個都可以省略，預設容器為vector，預設算子為less，即小的往前排，大

的往後排（出隊時序列尾的元素出隊）。

定義priority_queue對象的示例代碼如下：

priority_queue<int>q1;

priority_queue<pair<int,int> >q2;// 注意在兩個尖括号之間一定要留白格。

priority_queue<int,vector<int>,greater<int>>q3;// 定義小的先出隊

priority_queue的基本操作與queue相同。

初學者在使用priority_queue時，最困難的可能就是如何定義比較算子了。

如果是基本資料類型，或已定義了比較運算符的類，可以直接用STL的less算子和greater

算子——預設為使用less算子，即小的往前排，大的先出隊。

如果要定義自己的比較算子，方法有多種，這裡介紹其中的一種：重載比較運算符。優先隊

列試圖将兩個元素x和y代入比較運算符(對less算子，調用x<y，對greater算子，調用x>y)，

若結果為真，則x排在y前面，y将先于x出隊，反之，則将y排在x前面，x将先出隊。

看下面這個簡單的示例：

#include<iostream>
#include<queue>
usingnamespacestd;
classT
{
public:
intx,y,z;
T(inta,intb,intc):x(a),y(b),z(c)
{
}
};
booloperator<(constT&t1,constT&t2)
{
returnt1.z<t2.z;// 按照z的順序來決定t1和t2的順序
}
main()
{
priority_queue<T>q;
q.push(T(4,4,3));
q.push(T(2,2,5));
q.push(T(1,5,4));
q.push(T(3,3,6));
while(!q.empty())
{
Tt=q.top();q.pop();
cout<<t.x<<""<<t.y<<""<<t.z<<endl;
}
return1;
}      

輸出結果為(注意是按照z的順序從大到小出隊的)：

336

225

154

443

再看一個按照z的順序從小到大出隊的例子：

#include<iostream>
#include<queue>
usingnamespacestd;
classT
{
public:
intx,y,z;
T(inta,intb,intc):x(a),y(b),z(c)
{
}
};
booloperator>(constT&t1,constT&t2)
{
returnt1.z>t2.z;
}
main()
{
priority_queue<T,vector<T>,greater<T>>q;
q.push(T(4,4,3));
q.push(T(2,2,5));
q.push(T(1,5,4));
q.push(T(3,3,6));
while(!q.empty())
{
Tt=q.top();q.pop();
cout<<t.x<<""<<t.y<<""<<t.z<<endl;
}
return1;
}      

輸出結果為：

443

154

225

336

如果我們把第一個例子中的比較運算符重載為：

booloperator<(constT&t1,constT&t2)

{

     returnt1.z>t2.z;// 按照z的順序來決定t1和t2的順序

}

則第一個例子的程式會得到和第二個例子的程式相同的輸出結果。

1.6 nth_element指定元素排序

nth_element一個容易看懂但解釋比較麻煩的排序。用例子說會更友善：

班上有10個學生，我想知道分數排在倒數第4名的學生。

如果要滿足上述需求，可以用sort排好序，然後取第4位（因為是由小到大排), 更聰明的

朋友會用partial_sort,隻排前4位，然後得到第4位。其實這是你還是浪費，因為前兩位你

根本沒有必要排序，此時，你就需要nth_element:

template<classRandomAccessIterator>

voidnth_element(RandomAccessIteratorfirst,RandomAccessIteratornth,

RandomAccessIteratorlast);

template<classRandomAccessIterator,classStrictWeakOrdering>

voidnth_element(RandomAccessIteratorfirst,RandomAccessIteratornth,

RandomAccessIteratorlast,StrictWeakOrderingcomp);

對于上述執行個體需求，你隻需要按下面要求修改1.4中的程式：

stable_sort(vect.begin(),vect.end(),less<student>());