Úvod
Fronta je sbírka položek, kde první položka přidaná do seznamu musí být první položkou, která bude dále odebrána. Jak se tedy do sbírky přidávají položky, jejich velikost roste, tj. Roste do délky. Kdykoli má být jakákoli položka odebrána, musí být první přidanou. Pokud jsou položky odstraňovány průběžně, pak další odstraněná je druhá položka; třetí se poté odstraní atd.
Poté, co byla odstraněna první položka z původního seznamu, se z druhé stane první položka. Po odebrání druhé položky se třetí stane první položkou atd.
Dobrým příkladem fronty v reálném životě je, když se lidé postaví do fronty, aby čekali na službu nebo dobro. První osobě se podává první před poslední. Fronta, o které se hovoří v tomto kurzu, je však softwarová fronta navržená v jazyce C ++.
FIFO
FIFO znamená First-In, First-Out. Je to další způsob, jak ocenit frontu. To znamená, že první položka, která vstoupí do seznamu, je první položkou, která bude odstraněna, kdykoli má dojít k odebrání. Začátek seznamu se nazývá hlava nebo přední část; konec seznamu se nazývá zadní nebo zadní.
Základní operace
Softwarová fronta musí mít alespoň následující operace:
tam
Tato operace přidá nový prvek na zadní stranu fronty. Tato operace se oficiálně nazývá enqueue.
posun
Tato operace odstraní první prvek fronty a druhý prvek se stane novým prvním prvkem. Tato operace se oficiálně nazývá dequeue. V C ++ se tomu říká pop.
Tento článek vysvětluje, jak používat datovou strukturu fronty C ++. Abyste porozuměli zbytku tohoto článku, měli byste znát ukazatele a odkazy v jazyce C ++.
Třída a objekty
Třída je sada proměnných a funkcí, které spolupracují, kde proměnné nemají přiřazené hodnoty. Když jsou proměnným přiřazeny hodnoty, třída se stane objektem. Různé hodnoty dané stejné třídě vedou k různým objektům; to znamená, že různé objekty jsou stejnou třídou s různými hodnotami. Vytváření objektu ze třídy se říká o instanci objektu.
Název, fronta, je třída. Objekt vytvořený ze třídy fronty má název zvolený programátorem.
Funkce, která patří do třídy, je potřebná k vytvoření instance objektu ze třídy. V C ++ má tato funkce stejný název jako název třídy. Objekty vytvořené (vytvořené instancí) ze třídy mají různá jména, která jim dal programátor.
Vytvoření objektu ze třídy znamená konstrukci objektu; to také znamená instanci.
Program C ++, který používá třídu fronty, začíná v horní části souboru následujícími řádky:
#zahrnout#zahrnout
pomocí oboru názvů std;
První řádek je pro vstup/výstup. Druhý řádek je umožnit programu využívat všechny funkce třídy fronty. Třetí řádek umožňuje programu používat jména ve standardním oboru názvů.
Přetížení funkce
Pokud mají dva nebo více různých podpisů funkcí stejný název, je tento název údajně přetížen. Při volání jedné funkce určuje počet a typ argumentů, která funkce je skutečně spuštěna.
Konstrukce
fronta<typ>název()Následující deklarace vytvoří instanci fronty s názvem que typu int.
fronta<int>že;Fronta je prázdná. Deklarace začíná vyhrazeným slovem, frontou následovanou hranatými závorkami s datovým typem. Pak máte programátorovi dané jméno pro frontu.
Konstrukce pomocí seznamu inicializátorů
Následující definice ukazuje, jak vytvořit frontu pomocí seznamu inicializátorů:
fronta<plovák>že({1.1, 2.2, 3.3, 4.4});Zničení fronty
Chcete -li zničit frontu, nechte ji mimo rozsah.
Přístup k prvkům fronty
push (hodnota)
Fronta je seznam First-In-First-Out. Každá hodnota je tedy přidána zezadu. Následující segment kódu vytvoří prázdnou frontu, po které se zezadu přidá pět plovoucích hodnot:
fronta<plovák>že;že.tam(1.1);
že.tam(2.2);
že.tam(3.3);
že.tam(4.4);
že.tam(5.5);
velikost () konst
Tím se vrátí počet prvků ve frontě. Následující kód ukazuje:
fronta<plovák>že;že.tam(1.1);že.tam(2.2);že.tam(3.3);že.tam(4.4);že.tam(5.5);
náklady<<že.velikost() << ' n';
Výstup je 5.
přední()
Tím se vrátí odkaz na první prvek fronty bez odebrání prvku. Výstupem následujícího kódu je 1.1.
fronta<plovák>že;že.tam(1.1);že.tam(2.2);že.tam(3.3);že.tam(4.4);že.tam(5.5);
náklady<<že.přední() << ' n';
Prvek není odebrán z fronty.
přední () konst
Když konstrukci fronty předchází const, provede se výraz front () const místo front (). Používá se například v následujícím kódu.
konstfronta<plovák>že({1.1, 2.2, 3.3, 4.4, 5.5});náklady<<že.přední() << ' n';
Je vrácena konstantní reference. Prvek není z vektoru odstraněn. Prvky fronty nelze změnit.
zadní()
Tím se vrátí odkaz na poslední prvek fronty bez odebrání prvku. Výstupem následujícího kódu je 5.5.
fronta<plovák>že;že.tam(1.1);že.tam(2.2);že.tam(3.3);že.tam(4.4);že.tam(5.5);
náklady<<že.zadní() << ' n';
zpět () konst
Když konstrukci fronty předchází const, provede se místo back () výraz back () const. Používá se například v následujícím kódu.
konstfronta<plovák>že({1.1, 2.2, 3.3, 4.4, 5.5});náklady<<že.zadní() << ' n';
Je vrácena konstantní reference. Prvek není odebrán z fronty. S předchozí konstantou pro konstrukci fronty nelze prvky ve frontě změnit.
Kapacita fronty
velikost () konst
- viz výše
prázdná () konst
To vrátí 1 pro true, pokud ve frontě nejsou žádné prvky, nebo 0 pro false, pokud je fronta prázdná. Následující kód to ilustruje:
fronta<plovák>že 1({1.1, 2.2, 3.3, 4.4, 5.5});náklady<<že 1.prázdný() << ' n';
fronta<plovák>že 2;
náklady<<že 2.prázdný() << ' n';
Výstupem je:
01
Modifikátory fronty
pop ()
Fronta je FIFO, takže jakýkoli prvek, který musí být odstraněn, musí být odstraněn z horní části (hlavy) fronty. Tato členská funkce odebere první prvek, aniž by jej vrátila. Následující kód to ilustruje:
fronta<plovák>že({1.1, 2.2, 3.3, 4.4, 5.5});náklady<<že.přední() << ' n';
že.pop();
náklady<<že.velikost() << ' n';
Výstupem je:
1.14
a.swap (b)
Dvě fronty lze vyměnit, jak je znázorněno v tomto segmentu kódu:
fronta<plovák>že 1({1.1, 2.2, 3.3, 4.4, 5.5});fronta<plovák>že 2({10, dvacet});
že 1.vyměnit(že 2);
náklady<< `` První prvek a velikost que1:
'<<že 1.přední() <<','<<že 1.velikost() << ' n';
náklady<< „První prvek a velikost que2“<<
že 2.přední() <<','<<že 2.velikost() << ' n';
Výstupem je:
První prvek a velikost que1: 10, 2
První prvek a velikost que2: 1,1, 5
V případě potřeby se délka fronty prodlouží. Také hodnoty, které neměly náhrady, jsou nahrazeny nějakou výchozí hodnotou. Datové typy musí být stejného typu.
Operátory rovnosti a relace pro fronty
U běžných znaků v C ++ jsou čísla ve vzestupném pořadí před velkými písmeny a před malými písmeny. Vesmírná postava přichází před nulou a všechny.
Provozovatelé rovnosti
Vrací 1 pro true a 0 pro false.
Operátor ==
Vrátí 1, pokud mají dvě fronty stejnou velikost a odpovídající prvky jsou stejné; jinak vrátí 0. Příklad:
fronta<konst char*>že 1({'druh', 'něco jiného'});fronta<konst char*>že 2({'zlý'});
intna jednom=že 1==že 2;
náklady<<na jednom<< ' n';
Výstup je: 0.
Operátor! =
- opak výše uvedeného. Příklad:
fronta<konst char*>že 1({'druh', 'něco jiného'});fronta<konst char*>že 2({'zlý'});
intna jednom=že 1! =že 2;
náklady<<na jednom<< ' n';
Výstupem je: 1.
Relační operátoři
Vrací 1 pro true a 0 pro false.
The
Vrátí 1, pokud je první fronta počáteční podmnožinou druhé fronty, přičemž prvky dvou stejných částí jsou stejné a ve stejném pořadí. Pokud jsou obě fronty stejné velikosti nebo různých velikostí a pohybují se zleva doprava, v první frontě se objeví prvek, který je menší než odpovídající prvek ve druhé frontě, pak bude stále vrácena 1. Jinak se vrátí 0. Příklad:
fronta<konst char*>že 1({'druh', 'něco jiného'});fronta<konst char*>že 2({'zlý'});
intna jednom=že 1<že 2;
náklady<<na jednom<< ' n';
Výstup je 1. > Operátor - opak výše uvedeného. Příklad: Výstup: 0 The<= Operator - stejný jako Výstup: 1 Operátor> = - opak výše uvedeného. Příklad: Výstup: 0 Hodnota je pro datový typ, protože instancovaný objekt je pro třídu. Konstrukce fronty může také přijmout třídu jako datový typ. Následující program to ilustruje: Výstup je 5. Seznam front se odborně nazývá propojený seznam. Pro frontu existují dva typy propojených seznamů: jednotlivě propojený seznam a dvakrát propojený seznam. Jednoduše propojený prvek seznamu může být implementován strukturou dvou členů. Jeden člen drží ukazatel na další prvek a druhý člen drží počátek (pro data singulární). Dvojitě propojený prvek seznamu lze implementovat strukturou tří členů. Prostřední člen drží počátek, zatímco první a třetí člen drží ukazatele na své sousední prvky. Fronta je datová struktura first-in-first-out. Existují situace v oblasti výpočetní techniky, když data přicházejí ve formě fronty, což vyžaduje chování první v první. Prostředek v počítači je jakákoli fyzická nebo virtuální součást s omezenou dostupností. Zahrnují procesor, grafickou kartu, pevný disk a paměť. Sdílení takového zdroje vyžaduje frontu. Periferní zařízení počítače musí čas od času počítač přerušit. Přerušení musí být řešeno stejným způsobem, jakým přišly. K tomu je potřeba fronta. Frontu lze použít například ke správě souborů aplikace pro úlohu, pokud jsou soubory uloženy v počítači. Fronta je datová struktura seznamu, která je buď jednotlivě propojeným seznamem, nebo dvojitě propojeným seznamem. Zpravidla platí, že první prvek, který vstoupí do seznamu, je prvním prvkem, který vyjde. C ++ poskytuje datovou strukturu fronty ve své standardní knihovně. Kategorie členských funkcí a operátorů dostupných pro tuto strukturu jsou konstrukce fronty, přístup k prvkům fronty, kapacita fronty, modifikátory fronty a operátoři přetížení fronty. Jakákoli datová struktura fronty musí poskytovat alespoň členské funkce push () a pop (). push () znamená odeslání nového prvku na zadní stranu fronty; a pop () znamená odebrání prvku, který je v přední části fronty. V C ++ tyto funkce bohužel nevracejí hodnotu, která byla vložena nebo vysunuta. Abychom tedy poznali poslední prvek před zatlačením, musí být použita funkce extra back (); a abyste znali první prvek před vyskakováním, musíte použít funkci extra front (). Hodnota je pro datový typ, protože instancovaný objekt je pro třídu. Konkrétní třídu lze tedy použít jako datový typ pro instanci šablony fronty. Různé objekty pro třídu se stávají jako různé hodnoty pro třídu. Fronta obsahuje aplikace v počítači. Lze jej použít například ke správě souborů aplikace pro úlohu, pokud jsou soubory uloženy v počítači. Chrys
fronta<konst char*>že 2({'zlý'});
intna jednom=že 1>že 2;
náklady<<na jednom<< ' n';
fronta<konst char*>že 2({'zlý'});
intna jednom=že 1<=že 2;
náklady<<na jednom<< ' n';
fronta<konst char*>že 2({'zlý'});
intna jednom=že 1> =že 2;
náklady<<na jednom<< ' n'; Třída a její instancované objekty
#zahrnout
pomocí oboru názvů std;
třída TheCla
{
veřejnost:
intna jednom;
statický charch;
prázdnéfunkce(charNe, konst char *p)
{
náklady<< 'Existují ' <<na jednom<< „knihy, které stojí za to“ <<Ne<<p<< ' v obchodě.' << ' n';
}
statický prázdnézábava(charch)
{
-li (ch== 'na')
náklady<< 'Oficiální statická členská funkce' << ' n';
}
};
inthlavní()
{
TheCla obj1;TheCla obj2;TheCla obj3;TheCla obj4;TheCla obj5;
fronta<TheCla>že;
že.tam(obj1);že.tam(obj2);že.tam(obj3);že.tam(obj4);že.tam(obj5);
náklady<<že.velikost() << ' n';
vrátit se 0;
} Spojový seznam
Aplikace fronty
Sdílení počítačových zdrojů
Manipulace s přerušeními
Spravovat informace.
Závěr