V minulΘm dφlu jsme zaΦali s odvozen²mi datov²mi strukturami, konkrΘtn∞ se zßsobnφkem. V tomto dφlu se budeme zab²vat podobnou strukturou nazvanou fronta. Po klasickΘ implementaci fronty si povφme jeÜt∞ o dvou jejφch modifikacφch - front∞ oboustrannΘ a v p°φÜtφm dφlu se setkßme jeÜt∞ s frontou prioritnφ.
Frontu budeme implementovat pomocφ pole a to konkrΘtn∞ pole dynamickΘho, abychom mohli vytvß°et r∙zn∞ dlouhΘ fronty. Stejn∞ jsme implementovali zßsobnφk v minulΘm dφlu. ZaΦneme frontou klasickou a pak p°ejdeme na frontu oboustrannou.
Nßzev fronta nßm napovφdß, ₧e prvky budou p°ib²vat z jednΘ strany pole a vybφrßny budou z druhΘ strany pole, podobn∞ jako tomu je v normßlnφm ₧ivot∞. Proto₧e prvky ub²vajφ z mφsta, kterΘ oznaΦujeme zaΦßtek fronty a p°ib²vajφ na konci, je struktura fronta strukturou typu FIFO (z angl. First in, first out (prvnφ dovnit°, prvnφ ven)). N∞kdy se takΘ oznaΦuje jako FCFS (z angl. First come, first served (Kdo prvnφ p°ijde, ten bude prvnφ obslou₧en;Kdo d°φv p°ijde, ten d°φv mele). GrafickΘ znßzorn∞nφ fronty:
NßÜ prvnφ nßvrh t°φdy zapouzd°ujφcφ datovou strukturu fronta:
#ifndef FRONTA_H
#define FRONTA_H
#include <iostream.h>
template<class T> class CFronta {
private :
T *m_Pole;
int m_Velikost; // maximalni velikost (delka) fronty
int m_Zacatek, m_Konec; // kde je zacatek a konec fronty
public :
CFronta(int _Velikost);
~CFronta();
bool Vloz(const T& _Vklad);
bool Vyjmi(T& _Vyber);
bool JePrazdna();
bool JePlna();
void Vypis();
};
// Zde budou tela metod
#endif
OvÜem pokud se nynφ zamyslφme nad implementacφ metod pro vklßdßnφ a vyjmutφ prvku dostaneme se do problΘmu. ╚lenskΘ prom∞nnΘ m_Zacatek a m_Konec budou udßvat indexy prvk∙ pole, kde se prßv∞ nachßzφ zaΦßtek a konec. P°i vlo₧enφ prvku budeme inkrementovat prom∞nnou m_Konec a p°i vyjmutφ prvku budeme inkrementovat prom∞nnou m_Zacatek. Tφm dojde po Φase k tomu, ₧e do fronty nep∙jde po urΦitΘ dob∞ (kterß bude zßviset na dΘlce fronty) vlo₧it dalÜφ prvek, proto₧e poslednφ prvek bude obsazen. Fronta vÜak nebude v∙bec zapln∞na. Ukß₧eme si pßr mo₧n²ch °eÜenφ:
P°i ka₧dΘm v²b∞ru bychom mohli posunout celou frontu o jeden prvek dop°edu, co₧ by m∞lo za nßsledek, ₧e se zaΦßtek fronty bude nachßzet v₧dy na prvnφm mφst∞ v poli. Postup je to sice velice jednoduch², ale znaΦn∞ neefektivnφ
M∙₧eme prvky posouvat a₧ v p°φpad∞, ₧e nep∙jde vlo₧it dalÜφ prvek, ale p°itom bude ve front∞ jeÜt∞ mφsto (tedy index zaΦßtku fronty nebude 0). Pole se tak bude p°emφs¥ovat jednou za Φas a hlavn∞ o v∞tÜφ vzdßlenost ne₧ tomu bylo v minulΘm °eÜenφ
P°edstavme si pole jako kruh, tedy po poslednφm prvku bude nßsledovat op∞t prvek prvnφ. V tomto p°φpad∞ tedy nebudeme muset v∙bec s prvky h²bat, co₧ je nejefektivn∞jÜφ, ale budeme muset troÜku pracovat s indexy. Tφm se nßm ovÜem mφrn∞ zkomplikuje test na to, zda je fronta prßzdnß nebo plnß. Proto zavedeme prom∞nnou m_Pocet, kterß bude udßvat aktußlnφ poΦet prvk∙ ve front∞.
My si vybereme samoz°ejm∞ poslednφ mo₧nost implementace, kterß takΘ nßsleduje:
#ifndef FRONTA_H
#define FRONTA_H
#include <iostream.h>
template<class T> class CFronta {
private :
T *m_Pole;
int m_Velikost; // maximalni velikost (delka) fronty
int m_Zacatek, m_Konec; // kde je zacatek a konec fronty
int m_Pocet; // pocet prvku prave se nachazejicich ve fronte
public :
CFronta(int _Velikost);
~CFronta();
bool Vloz(const T& _Vklad);
bool Vyjmi(T& _Vyber);
bool JePrazdna() { return ((0 == m_Pocet) ? true : false); }
bool JePlna() { return ((m_Pocet == m_Velikost) ? true : false); }
void Vypis();
};
template<class T> CFronta<T>::CFronta(int _Velikost)
{
m_Velikost = -1;
m_Pocet = 0;
m_Zacatek = 0;
m_Konec = -1; // abychom v metode Vloz dostali spravny
konec pri prvnim
vkladani
m_Pole = new T[_Velikost];
if(m_Pole)
{
// pokud se podarilo nastavime velikost
m_Velikost = _Velikost;
}
}
template<class T> CFronta<T>::~CFronta()
{
if(m_Pole)
{
delete[] m_Pole;
m_Pole = NULL;
m_Velikost = 0;
}
}
template<class T> bool CFronta<T>::Vloz(const T& _Vklad)
{
bool bNavrat = false;
if(m_Pole)
{
if(!JePlna())
{
if(m_Konec == (m_Velikost - 1))
{
// pokud konec dosahne konce pole, pak koncime na prvnim prvku pole
m_Konec = 0;
}
else
{
m_Konec++;
}
m_Pole[m_Konec] = _Vklad;
m_Pocet++; // pribyl prvek
bNavrat = true;
}
}
return bNavrat;
}
template<class T> bool CFronta<T>::Vyjmi(T& _Vyber)
{
bool bNavrat = false;
if(m_Pole)
{
if(!JePrazdna())
{
_Vyber = m_Pole[m_Zacatek];
if(m_Zacatek == (m_Velikost - 1))
{
// pokud zacatek dosahne konce pole, pak zaciname zase na prvnim prvku
m_Zacatek = 0;
}
else
{
// posun na novy zacatek
m_Zacatek++;
}
m_Pocet--; // ubyl prvek
bNavrat = true;
}
}
return bNavrat;
}
template <class T> void CFronta<T>::Vypis()
{
if(m_Pole)
{
if(!JePrazdna())
{
cout << "Obsahuje " << m_Pocet << " objektu (volnych " << m_Velikost - (m_Pocet)
<< ")" << endl;
for(int i = 0; i < m_Velikost; i++)
{
cout << m_Pole[i] << endl;
}
}
else
{
cout << "Fronta je prazdna" << endl;
}
}
}
#endif
Metoda Vypis() vypisuje pouze obsah pole, ne frontu od prvnφho k poslednφmu prvku. Podobn∞ jako u zßsobnφku se n∞kdy implementuje metoda Nakoukni(), kterß pouze vrßtφ prvnφ prvek fronty, ale neodebere ho z fronty. K≤d je stejn² jako u metody Vyjmi() s tφm rozdφlem, ₧e nem∞nφme ₧ßdnΘ indexy ani poΦet prvk∙.
Jak u₧ z nßzvu tuÜφte, jednß se o frontu, kterß umo₧≥uje p°idßvßnφ a samoz°ejm∞ vybφrßnφ prvk∙ z obou stran:
Implementace tΘto datovΘ struktury bude podobnß jako v minulΘm odstavci, ale mφsto metod Vloz() a Vyjmi() budou metody 4: VlozZacatek(), VlozKonec(), VyjmiZacatek() a VyjmiKonec(). Op∞t vyu₧ijeme mo₧nosti zacyklit pole a tedy budeme pracovat jen s indexy. Mo₧nß implementace t∞chto metod nßsleduje:
template<class T> bool CObouFronta<T>::VlozZacatek(const T&
_Vklad)
{
bool bNavrat = false;
if(m_Pole)
{
if(!JePlna())
{
if(m_Zacatek == 0)
{
// pokud zacatek dosahne zacatku pole, pak zaciname na poslednim prvku fronty
m_Zacatek = m_Velikost - 1;
}
else
{
// posun na novy zacatek, ale jen v pripade, ze nevkladame prvni prvek
if(!JePrazdna())
{
m_Zacatek--;
}
else
{
// pokud bylo pole prazdne, pak se zacatek i konec nachazi na stejnem miste
m_Zacatek = 0;
m_Konec = 0;
}
}
m_Pole[m_Zacatek] = _Vklad;
m_Pocet++; // pribyl prvek
bNavrat = true;
}
}
return bNavrat;
}
template<class T> bool CObouFronta<T>::VlozKonec(const T& _Vklad)
{
bool bNavrat = false;
if(m_Pole)
{
if(!JePlna())
{
if(m_Konec == (m_Velikost - 1))
{
// pokud konec dosahne konce pole, pak koncime na prvnim prvku pole
m_Konec = 0;
}
else
{
// posun na novy konec, ale jen v pripade, ze nevkladame prvni prvek
if(!JePrazdna())
{
m_Konec++;
}
else
{
// pokud bylo pole prazdne, pak se zacatek i konec nachazi na stejnem miste
m_Zacatek = 0;
m_Konec = 0;
}
}
m_Pole[m_Konec] = _Vklad;
m_Pocet++; // pribyl prvek
bNavrat = true;
}
}
return bNavrat;
}
template<class T> bool CObouFronta<T>::VyjmiZacatek(T& _Vyber)
{
bool bNavrat = false;
if(m_Pole)
{
if(!JePrazdna())
{
_Vyber = m_Pole[m_Zacatek];
if(m_Zacatek == m_Velikost - 1)
{
// pokud zacatek dosahne konce pole, pak zaciname zase na prvnim prvku
m_Zacatek = 0;
}
else
{
// posun na novy zacatek
m_Zacatek++;
}
m_Pocet--;
// ubyl prvek
bNavrat = true;
}
}
return bNavrat;
}
template<class T> bool CObouFronta<T>::VyjmiKonec(T& _Vyber)
{
bool bNavrat = false;
if(m_Pole)
{
if(!JePrazdna())
{
_Vyber = m_Pole[m_Konec];
if(m_Konec == 0)
{
// pokud konec dosahne zacatku pole, pak zaciname zase na poslednim prvku
m_Konec = m_Velikost - 1;
}
else
{
// posun na novy zacatek
m_Konec--;
}
m_Pocet--;
// ubyl prvek
bNavrat = true;
}
}
return bNavrat;
}
U oboustrannΘ fronty se op∞t implementujφ metody, kterΘ umo₧≥ujφ nahlΘdnout na prvek, kter² je prßv∞ na jednom z konc∙ fronty.
V p°φÜtφm dφlu se setkßme s poslednφ modifikacφ fronty - frontou prioritnφ. PotΘ p°ejdeme k datovΘ struktu°e lineßrnφ spojov² seznam, kterß nßm umo₧nφ jednoduÜe vytvß°et nekoneΦn∞ dlouhΘ zßsobnφky nebo fronty. V n∞kterΘm z nßsledujφcφch dφlu se pak seznßmφme se strukturou zvanou strom, kterß je podobnß lineßrnφmu spojovΘmu seznamu.
PřφÜtě nashledanou.