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
Kód naleznete v sekci Downloads (projekt Fronta).
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;
}
Kód naleznete v sekci Downloads (projekt Fronta2).
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.
