|
Äëя î÷åðåäè (îïðåäåëåíèå ñì. ðaçäåë «Î÷åðåäè», ñ. 121) äîïóñêaþòñя äâå îïåða- öèè, èçìåíяþùèå åå ðaçìåð — äîáaâëåíèå ýëåìåíòa â êîíåö è âûáîðêa èç ía÷aëa. Î÷åðåäü яâëяåòñя aäaïòåðîì, êîòîðûé ìîæíî ðåaëèçîâaòü ía îñíîâå äâóñòîðîí-
íåé î÷åðåäè èëè ñïèñêa (âåêòîð íå ïîäõîäèò, ïîñêîëüêó â íåì íåò îïåðaöèè âû- áîðêè èç ía÷aëa).
 STL î÷åðåäü îïðåäåëåía ïî óìîë÷aíèþ ía áaçå äâóñòîðîííåé î÷åðåäè:
template > Class queue {
prOteCted:
COntainer C; publiC:
expliCit queue(COnst COntainer& = COntainer());
bOOl empty() COnst {return C.empty();} size_type size() COnst {return C.size();} value_type& frOnt() {return C.frOnt();} COnst value_type& frOnt() COnst {return C.frOnt();} value_type& baCk() {return C.baCk();} COnst value_type& baCk() COnst {return C.baCk();} vOid push(COnst value_type& x) {C.push_baCk(x);} vOid pOp() {C.pOp_frOnt();}
};
Ìåòîäû frOnt è baCk èñïîëüçóþòñя äëя ïîëó÷åíèя çía÷åíèé ýëåìåíòîâ, íaõîäя- ùèõñя ñîîòâåòñòâåííî â ía÷aëå è â êîíöå î÷åðåäè (ïðè ýòîì ýëåìåíòû îñòaþòñя â î÷åðåäè).
Ïðèìåð ðaáîòû ñ î÷åðåäüþ (ïðîãðaììa ââîäèò èç ôaéëa ÷èñëa â î÷åðåäü è âû- ïîëíяåò âûáîðêó èç íåå, ïîêa î÷åðåäü íå îïóñòååò):
inClude inClude inClude using namespaCe std; int main(){
ifstream in ("inpnum"); queue > q; int x;
while ( in >> x, !in.eOf()) q.push(x);
COut << "q.frOnt(): " << q.frOnt() << " "; COut << "q.baCk(): " << q.baCk() << endl; while (! q.empty()){
q.pOp();
COut << "q.frOnt(): " << q.frOnt() << " "; COut << "q.baCk(): " << q.baCk() << endl;
}
}
Cîäåðæèìîå ôaéëa inpnum:
56 34 540 76 23 51 11 51 11 76 88
Ðåçóëüòaò ðaáîòû ïðîãðaììû:
q.frOnt(): 56 q.baCk(): 88
q.frOnt(): 34 q.baCk(): 88
q.frOnt():
|
54
|
q.baCk():
|
88
|
q.frOnt():
|
0
|
q.baCk():
|
88
|
q.frOnt():
|
76
|
q.baCk():
|
88
|
q.frOnt():
|
23
|
q.baCk():
|
88
|
q.frOnt():
|
51
|
q.baCk():
|
88
|
q.frOnt():
|
11
|
q.baCk():
|
88
|
q.frOnt():
|
51
|
q.baCk():
|
88
|
q.frOnt():
|
11
|
q.baCk():
|
88
|
q.frOnt():
|
76
|
q.baCk():
|
88
|
q.frOnt():
|
88
|
q.baCk():
|
88
|
q.frOnt():
|
0
|
q.baCk():
|
0
|
Ê ñòåêaì è î÷åðåäяì ìîæíî ïðèìåíяòü aëãîðèòìû ñòaíäaðòíîé áèáëèîòåêè, îïè- ñaííûå â ðaçäåëå «Àëãîðèòìû» (ñ. 343).
Очереди с приоритетами (priority_queue)
 î÷åðåäè ñ ïðèîðèòåòaìè êaæäîìó ýëåìåíòó ñîîòâåòñòâóåò ïðèîðèòåò, îïðåäå- ëяþùèé ïîðяäîê âûáîðêè èç î÷åðåäè. Ïî óìîë÷aíèþ îí îïðåäåëяåòñя ñ ïîìî- ùüþ îïåðaöèè <; òaêèì îáðaçîì, èç î÷åðåäè êaæäûé ðaç âûáèðaåòñя ìaêñèìaëü- íûé ýëåìåíò.
Äëя ðåaëèçaöèè î÷åðåäè ñ ïðèîðèòåòaìè ïîäõîäèò êîíòåéíåð, äîïóñêaþùèé ïðîèçâîëüíûé äîñòóï ê ýëåìåíòaì, òî åñòü, íaïðèìåð, âåêòîð èëè äâóñòîðîííяя î÷åðåäü. Òèï êîíòåéíåða ïåðåäaåòñя âòîðûì ïaðaìåòðîì øaáëîía (ïåðâûé, êaê îáû÷íî, òèï ýëåìåíòîâ). Òðåòüèì ïaðaìåòðîì óêaçûâaåòñя ôóíêöèя èëè ôóíê- öèîíaëüíûé îáúåêò (ñì. ñ. 195 è 334), ñ ïîìîùüþ êîòîðûõ âûïîëíяåòñя îïðåäå- ëåíèå ïðèîðèòåòa:
template ,
Class COmpare = less > Class priOrity_queue {
prOteCted:
COntainer C;
COmpare COmp;
publiC:
expliCit priOrity_queue(COnst COmpare& x = COmpare(), COnst COntainer& = COntainer());
template priOrity_queue(InputIter first, InputIter last,
COnst COmpare& x = COmpare(), COnst COntainer& = COntainer()); bOOl empty() COnst {return C.empty();}
size_type size() COnst {return C.size();} COnst value_type& tOp() COnst {return C.frOnt();} vOid push(COnst value_type& x);
vOid pOp();
};
Äëя ýëåìåíòîâ ñ ðaâíûìè ïðèîðèòåòaìè î÷åðåäü ñ ïðèîðèòåòaìè яâëяåòñя ïðî- ñòîé î÷åðåäüþ. Êaê è äëя ñòåêîâ, îñíîâíûìè ìåòîäaìè яâëяþòñя push, pOp è tOp.
Ïðîñòîé ïðèìåð:
inClude inClude inClude inClude
using namespaCe std; int main(){
priOrity_queue , less > P; int x;
P.push(13); P.push(51); P.push(200); P.push(17); while (!P.empty()){
x = P.tOp(); COut << "Âûáðaí ýëåìåíò: " << x << endl; P.pOp();
}
}
Ðåçóëüòaò ðaáîòû ïðîãðaììû:
Âûáðaí ýëåìåíò: 200
Âûáðaí ýëåìåíò: 51
Âûáðaí ýëåìåíò: 17
Âûáðaí ýëåìåíò: 13
 ýòîì ïðèìåðå òðåòüèì ïaðaìåòðîì øaáëîía яâëяåòñя øaáëîí, îïðåäåëåííûé â çaãîëîâî÷íîì ôaéëå (ñì. ðaçäåë «Ôóíêöèîíaëüíûå îáúåêòû», ñ. 334). Îí çaäaåò îïåðaöèþ ñðaâíåíèя ía «ìåíüøå». Ìîæíî çaäaòü ñòaíäaðòíûå øaáëîíû greater<òèï>, greater_equal<òèï>, less_equal<òèï>. Åñëè òðåáóåòñя îïðåäå- ëèòü äðóãîé ïîðяäîê âûáîðêè èç î÷åðåäè, ââîäèòñя ñîáñòâåííûé ôóíêöèîíaëü- íûé îáúåêò.  ïðèâåäåííîì íèæå ïðèìåðå âûáîðêa âûïîëíяåòñя ïî íaèìåíüøåé ñóììå öèôð â ÷èñëå:
inClude inClude inClude inClude
using namespaCe std;
Class COmpareSum{
publiC:
bOOl OperatOr()(int x, int y){ int sx= 0, sy= 0;
while (x){sx += x % 10; x /= 10;} while (y){sy += y % 10; y/=10;} return sx > sy ;
}
};
int main(){
priOrity_queue , COmpareSum > P; int x;
P.push(13); P.push(51); P.push(200); P.push(17); while (!P.empty()){
x = P.tOp(); COut << "Âûáðaí ýëåìåíò: " << x << endl; P.pOp();
}
}
Ðåçóëüòaò ðaáîòû ïðîãðaììû:
Âûáðaí ýëåìåíò: 200
Âûáðaí ýëåìåíò: 13
Âûáðaí ýëåìåíò: 51
Âûáðaí ýëåìåíò: 17
Do'stlaringiz bilan baham: |
