Úvod
Fronta je zbierka položiek, pričom prvá položka pridaná do zoznamu musí byť prvou položkou, ktorá sa bude ďalej odstraňovať. Keďže položky do zbierky pribúdajú, narastá do veľkosti, t.j. rastie do dĺžky. Kedykoľvek má byť ktorákoľvek položka odstránená, musí byť prvou pridanou. Ak sa položky odstraňujú nepretržite, potom je ďalšou odstránenou položkou druhá položka; tretí sa potom odstráni atď.
Po odstránení prvej položky z pôvodného zoznamu sa z druhej stane prvá položka. Po odstránení druhej položky sa z tretej stane prvá položka a podobne.
Dobrým príkladom frontu v reálnom živote je, keď sa ľudia postavia do radu, aby čakali na službu alebo dobro. Prvá osoba je podaná ako prvá pred poslednou. Frontom, o ktorom sa hovorí v tomto návode, je však softvérový front navrhnutý v jazyku C ++.
FIFO
FIFO znamená First-In, First-Out. Je to ďalší spôsob, ako oceniť front. To znamená, že prvá položka, ktorá vstúpi do zoznamu, je prvou položkou, ktorá sa má odstrániť, kedykoľvek sa má odstránenie vykonať. Začiatok zoznamu sa nazýva hlava alebo predná časť; koniec zoznamu sa nazýva chrbát alebo chvost.
Základné operácie
Softwarový front musí mať aspoň tieto operácie:
tlačiť
Táto operácia pridá nový prvok na koniec frontu. Táto operácia sa oficiálne nazýva enqueue.
smena
Táto operácia odstráni prvý prvok frontu a z druhého prvku sa stane nový prvý prvok. Táto operácia sa oficiálne nazýva dequeue. V C ++ sa tomu hovorí pop.
Tento článok vysvetľuje, ako používať dátovú štruktúru frontu C ++. Pochopte zvyšok tohto článku a mali by ste vedieť ukazovatele a odkazy v jazyku C ++.
Trieda a objekty
Trieda je množina premenných a funkcií, ktoré spolupracujú a kde premenným nie sú priradené žiadne hodnoty. Keď sú premenným priradené hodnoty, trieda sa stane objektom. Rôzne hodnoty dané tej istej triede vedú k rôznym predmetom; to znamená, že rôzne objekty sú rovnakou triedou s rôznymi hodnotami. Vytvorenie objektu z triedy je údajne inštanciou objektu.
Názov, front, je trieda. Objekt vytvorený z triedy frontu má názov zvolený programátorom.
Funkcia, ktorá patrí do triedy, je potrebná na vytvorenie inštancie objektu z triedy. V C ++ má táto funkcia rovnaký názov ako názov triedy. Objekty vytvorené (inštancované) z triedy majú programátor rôzne názvy.
Vytvorenie objektu z triedy znamená zostrojenie objektu; to tiež znamená inštancovanie.
Program C ++, ktorý používa triedu frontov, začína na nasledujúcich riadkoch v hornej časti súboru:
#zahrnúť#zahrnúť
pomocou priestoru názvov std;
Prvý riadok je pre vstup/výstup. Druhý riadok má umožniť programu využívať všetky funkcie triedy front. Tretí riadok umožňuje programu používať názvy v štandardnom priestore názvov.
Preťaženie funkcie
Keď majú dva alebo viac rôznych podpisov funkcií rovnaký názov, tento názov je údajne preťažený. Pri volaní jednej funkcie určuje počet a typ argumentov, ktorá funkcia sa skutočne vykoná.
Konštrukcia
fronta<typ>názov()Nasledujúca deklarácia vytvára inštanciu frontu s názvom que typu int.
fronta<int>že;Fronta je prázdna. Deklarácia začína vyhradeným slovom, frontom a uhlovými zátvorkami s údajovým typom. Potom programátorovi dáte názov frontu.
Konštrukcia so zoznamom inicializátorov
Nasledujúca definícia ukazuje, ako vytvoriť front so zoznamom inicializátorov:
fronta<plavák>že({1.1, 2.2, 3.3, 4.4});Zničenie radu
Ak chcete frontu zničiť, nechajte ju mimo dosahu.
Prístup k prvkom frontu
push (hodnota)
Fronta je zoznam First-In-First-Out. Každá hodnota je teda pridaná zozadu. Nasledujúci segment kódu vytvorí prázdny front, po ktorom sa zozadu pridá päť pohyblivých hodnôt:
fronta<plavák>že;že.tlačiť(1.1);
že.tlačiť(2.2);
že.tlačiť(3.3);
že.tlačiť(4.4);
že.tlačiť(5.5);
veľkosť () konšt
Tým sa vráti počet prvkov vo fronte. Nasledujúci kód ilustruje:
fronta<plavák>že;že.tlačiť(1.1);že.tlačiť(2.2);že.tlačiť(3.3);že.tlačiť(4.4);že.tlačiť(5.5);
náklady<<že.veľkosť() << ' n';
Výstup je 5.
vpredu ()
Tým sa vráti odkaz na prvý prvok frontu bez odstránenia prvku. Výstupom nasledujúceho kódu je 1.1.
fronta<plavák>že;že.tlačiť(1.1);že.tlačiť(2.2);že.tlačiť(3.3);že.tlačiť(4.4);že.tlačiť(5.5);
náklady<<že.vpredu() << ' n';
Prvok nie je odstránený z frontu.
predná () konšt
Keď konštrukcii frontu predchádza príkaz const, namiesto výrazu front () sa vykoná výraz front () const. Používa sa napríklad v nasledujúcom kóde.
konštfronta<plavák>že({1.1, 2.2, 3.3, 4.4, 5.5});náklady<<že.vpredu() << ' n';
Vráti sa konštantná referencia. Prvok nie je odstránený z vektora. Prvky frontu nie je možné zmeniť.
späť()
Tým sa vráti odkaz na posledný prvok frontu bez odstránenia prvku. Výstupom nasledujúceho kódu je 5.5.
fronta<plavák>že;že.tlačiť(1.1);že.tlačiť(2.2);že.tlačiť(3.3);že.tlačiť(4.4);že.tlačiť(5.5);
náklady<<že.späť() << ' n';
späť () konšt
Keď konštrukcii frontu predchádza príkaz const, namiesto príkazu back () sa vykoná výraz back () const. Používa sa napríklad v nasledujúcom kóde.
konštfronta<plavák>že({1.1, 2.2, 3.3, 4.4, 5.5});náklady<<že.späť() << ' n';
Vráti sa konštantná referencia. Prvok nie je odstránený z frontu. S predchádzajúcou konštantou pre stavbu frontu nemožno prvky vo fronte meniť.
Kapacita frontu
veľkosť () konšt
- viď vyššie
prázdna () konšt
Vráti hodnotu 1 pre hodnotu true, ak vo fronte nie sú žiadne prvky, alebo 0 pre hodnotu false, ak je front prázdny. Nasledujúci kód to ilustruje:
fronta<plavák>že 1({1.1, 2.2, 3.3, 4.4, 5.5});náklady<<že 1.prázdny() << ' n';
fronta<plavák>že2;
náklady<<že2.prázdny() << ' n';
Výstupom je:
01
Modifikátory frontu
pop ()
Fronta je FIFO, takže každý prvok, ktorý je potrebné odstrániť, musí byť odstránený z hornej časti (hlavy) frontu. Táto členská funkcia odstráni prvý prvok bez jeho vrátenia. Nasledujúci kód to ilustruje:
fronta<plavák>že({1.1, 2.2, 3.3, 4.4, 5.5});náklady<<že.vpredu() << ' n';
že.pop();
náklady<<že.veľkosť() << ' n';
Výstupom je:
1.14
a. výmena (b)
Dve fronty je možné zameniť, ako je znázornené v tomto segmente kódu:
fronta<plavák>že 1({1.1, 2.2, 3.3, 4.4, 5.5});fronta<plavák>že2({10, dvadsať});
že 1.vymeniť(že2);
náklady<< „Prvý prvok a veľkosť que1:
'<<že 1.vpredu() <<','<<že 1.veľkosť() << ' n';
náklady<< „Prvý prvok a veľkosť que2“<<
že2.vpredu() <<','<<že2.veľkosť() << ' n';
Výstupom je:
Prvý prvok a veľkosť que1: 10, 2
Prvý prvok a veľkosť que2: 1,1, 5
V prípade potreby sa dĺžka frontu zvýši. Tiež hodnoty, ktoré nemali nahradenia, sú nahradené nejakou predvolenou hodnotou. Dátové typy musia byť rovnakého typu.
Operátory rovnosti a relacie pre fronty
Pri bežných znakoch v C ++ sú čísla vo vzostupnom poradí pred veľkými písmenami a pred malými písmenami. Vesmírna postava prichádza pred nulu a všetky.
Operátori rovnosti
Vráti 1 pre true a 0 pre false.
Operátor ==
Vráti hodnotu 1, ak majú dva fronty rovnakú veľkosť a zodpovedajúce prvky sú rovnaké; inak vráti 0. Príklad:
fronta<konšt char*>že 1({'milý', 'niečo iné'});fronta<konšt char*>že2({„zlý“});
intna jeden=že 1==že2;
náklady<<na jeden<< ' n';
Výstup je: 0.
Operátor! =
- opak vyššie uvedeného. Príklad:
fronta<konšt char*>že 1({'milý', 'niečo iné'});fronta<konšt char*>že2({„zlý“});
intna jeden=že 1! =že2;
náklady<<na jeden<< ' n';
Výstupom je: 1.
Relační operátori
Vráti 1 pre true a 0 pre false.
The
Vráti hodnotu 1, ak je prvý front počiatočnou podmnožinou druhého frontu, pričom prvky dvoch rovnakých častí sú rovnaké a v rovnakom poradí. Ak sú obidva fronty rovnakej veľkosti alebo rôznych veľkostí a pohybujú sa zľava doprava, v prvom fronte sa vyskytne prvok, ktorý je menší ako zodpovedajúci prvok v druhom rade, potom bude 1 vrátený. V opačnom prípade sa vráti 0. Príklad:
fronta<konšt char*>že 1({'milý', 'niečo iné'});fronta<konšt char*>že2({„zlý“});
intna jeden=že 1<že2;
náklady<<na jeden<< ' n';
Výstup je 1. > Operátor - opak vyššie uvedeného. Príklad: Výstup: 0 The<= Operator - rovnaké ako Výstup: 1 Operátor> = - opak vyššie uvedeného. Príklad: Výstup: 0 Hodnota je pre dátový typ, pretože inštancovaný objekt je pre triedu. Konštrukcia frontu môže tiež akceptovať triedu ako dátový typ. Nasledujúci program to ilustruje: Výstup je 5. Zoznam frontov sa odborne nazýva prepojený zoznam. Existujú dva typy prepojených zoznamov pre front: jednoducho prepojený zoznam a dvakrát prepojený zoznam. Jedine prepojený prvok zoznamu môže byť implementovaný štruktúrou dvoch členov. Jeden člen drží ukazovateľ na nasledujúci prvok a druhý člen drží vzťažný bod (pre údaje jednotné číslo). Dvojnásobne prepojený prvok zoznamu môže byť implementovaný štruktúrou troch členov. Stredný prvok drží vzťažný bod, zatiaľ čo prvý a tretí prvok ukazujú na susedné prvky. Fronta je dátová štruktúra first-in-first-out. V práci na počítači existujú situácie, keď údaje prichádzajú vo forme frontu, čo si vyžaduje správanie prvý v prvom rade. Prostriedok v počítači je akýkoľvek fyzický alebo virtuálny komponent s obmedzenou dostupnosťou. Zahŕňajú procesor, grafickú kartu, pevný disk a pamäť. Na zdieľanie takéhoto zdroja je potrebný front. Periférne zariadenia počítača musia počítač z času na čas prerušiť. Prerušenia je potrebné zvládnuť rovnakým spôsobom, akým prišli. Na to je potrebný front. Frontu je možné použiť napríklad na správu súborov aplikácií pre úlohu, ak sú súbory uložené v počítači. Fronta je dátová štruktúra zoznamu, ktorá je buď jednotlivo prepojeným zoznamom, alebo dvakrát prepojeným zoznamom. Prvý prvok, ktorý vstúpi do zoznamu, je spravidla prvým prvkom, ktorý vyjde. C ++ poskytuje dátovú štruktúru frontu vo svojej štandardnej knižnici. Kategórie členských funkcií a operátorov, ktoré sú k dispozícii pre túto štruktúru, sú vytváranie frontov, prístup k prvkom frontu, kapacita frontu, modifikátory frontu a preťažené operátory. Akákoľvek dátová štruktúra frontu musí poskytovať aspoň členské funkcie push () a pop (). push () znamená odoslanie nového prvku na koniec frontu; a pop () znamená odstránenie prvku, ktorý je v prednej časti frontu. V C ++ tieto funkcie bohužiaľ nevracajú hodnotu posunutú alebo vyskočenú. Aby ste poznali posledný prvok pred stlačením, musíte použiť funkciu extra back (); a aby ste poznali prvý prvok pred vyskočením, musíte použiť funkciu extra front (). Hodnota je pre dátový typ, pretože inštancovaný objekt je pre triedu. Konkrétnu triedu je teda možné použiť ako typ údajov pre inštanciu šablóny frontu. Rôzne objekty pre triedu sa stávajú ako rôzne hodnoty pre triedu. Fronta obsahuje aplikácie v počítači. Dá sa použiť napríklad na správu súborov aplikácií pre úlohu, ak sú súbory uložené v počítači. Chrys
fronta<konšt char*>že2({„zlý“});
intna jeden=že 1>že2;
náklady<<na jeden<< ' n';
fronta<konšt char*>že2({„zlý“});
intna jeden=že 1<=že2;
náklady<<na jeden<< ' n';
fronta<konšt char*>že2({„zlý“});
intna jeden=že 1> =že2;
náklady<<na jeden<< ' n'; Trieda a jej inštancionálne objekty
#zahrnúť
pomocou priestoru názvov std;
trieda TheCla
{
verejná:
intna jeden;
statický charch;
prázdnyfunkciu(charč, konšt char *p)
{
náklady<< 'Existujú ' <<na jeden<< „knihy, ktoré stoja za to“ <<č<<p<< ' v obchode.' << ' n';
}
statický prázdnyzábava(charch)
{
keby (ch== „do“)
náklady<< „Oficiálna statická členská funkcia“ << ' n';
}
};
intHlavná()
{
TheCla obj1;TheCla obj2;TheCla obj3;TheCla obj4;TheCla obj5;
fronta<TheCla>že;
že.tlačiť(obj1);že.tlačiť(obj2);že.tlačiť(obj3);že.tlačiť(obj4);že.tlačiť(obj5);
náklady<<že.veľkosť() << ' n';
vrátiť sa 0;
} Prepojený zoznam
Aplikácie vo fronte
Zdieľanie počítačových zdrojov
Manipulácia s prerušeniami
Spravovať informácie.
Záver