Introducere
O coadă este o colecție de articole, în care primul element adăugat în listă trebuie să fie primul element care trebuie eliminat în continuare. Deci, pe măsură ce elementele sunt adăugate la colecție, aceasta crește în dimensiune, adică crește în lungime. Ori de câte ori un element trebuie eliminat, acesta trebuie să fie primul adăugat. Dacă articolele sunt eliminate în mod continuu, atunci următorul element eliminat este al doilea articol; al treilea este îndepărtat după aceea și așa mai departe.
După ce primul element din lista originală a fost eliminat, al doilea devine primul element. După ce al doilea element a fost eliminat, al treilea devine primul articol și așa mai departe.
Un bun exemplu din viața reală a unei cozi este atunci când oamenii se aliniază pentru a aștepta serviciul sau bine. Prima persoană este servită prima înainte de ultima. Cu toate acestea, coada despre care am vorbit în acest tutorial este coada software, așa cum a fost proiectată în C ++.
FIFO
FIFO înseamnă First-In, First-Out. Este un alt mod de a aprecia coada. Aceasta înseamnă că primul articol care intră pe listă este primul articol care trebuie eliminat, de fiecare dată când va avea loc eliminarea. Începutul listei se numește cap sau față; sfârșitul listei se numește spate sau coadă.
Operațiuni esențiale
O coadă de software trebuie să aibă cel puțin următoarele operații:
Apăsați
Această operație adaugă un element nou în spatele cozii. Această operațiune este denumită oficial, coadă.
schimb
Această operație elimină primul element al cozii, iar al doilea element devine noul element. Această operațiune se numește oficial dequeue. Se numește pop în C ++.
Acest articol explică modul de utilizare a structurii de date a cozii C ++. Ar trebui să cunoașteți indicii și referințe C ++ pentru a înțelege restul acestui articol.
Clasa și obiecte
O clasă este un set de variabile și funcții care funcționează împreună, unde variabilele nu au valori atribuite. Când valorile sunt atribuite variabilelor, clasa devine un obiect. Valori diferite date aceleiași clase rezultă în obiecte diferite; adică diferite obiecte sunt aceeași clasă cu valori diferite. Se spune că crearea unui obiect dintr-o clasă este instanțierea obiectului.
Numele, coadă, este o clasă. Un obiect creat din clasa de coadă are un nume ales de programator.
O funcție care aparține unei clase este necesară pentru a crea un obiect din clasă. În C ++, acea funcție are același nume ca și numele clasei. Obiectele create (instanțiate) din clasă au nume diferite date de către programator.
Crearea unui obiect din clasă înseamnă construirea obiectului; înseamnă și instanțierea.
Un program C ++ care folosește clasa de coadă, începe cu următoarele linii în partea de sus a fișierului:
#include#include
folosind spațiul de nume std;
Prima linie este pentru intrare / ieșire. A doua linie este de a permite programului să utilizeze toate caracteristicile clasei de coadă. A treia linie permite programului să utilizeze numele din spațiul de nume standard.
Supraîncărcarea unei funcții
Când două sau mai multe semnături de funcții diferite au același nume, se spune că acel nume este suprasolicitat. Când se apelează o funcție, numărul și tipul argumentelor, determinați ce funcție este efectiv executată.
Constructie
coadă<tip>Nume()Următoarea declarație instanțiază o coadă numită, que de tip int.
coadă<int>acea;Coada este goală. Declarația începe cu cuvântul rezervat, coadă urmat de paranteze unghiulare cu tipul de date. Apoi, aveți numele programatorului dat pentru coadă.
Construirea cu lista inițializatorului
Următoarea definiție arată cum să creați o coadă cu lista de inițializatoare:
coadă<pluti>acea({1.1, 2.2, 3.3, 4.4});Distrugerea unei cozi
Pentru a distruge o coadă, lăsați-o să iasă din domeniul de aplicare.
Acces la element de coadă
împinge (valoare)
O coadă este o listă First-In-First-Out. Deci, fiecare valoare este adăugată din spate. Următorul segment de cod creează o coadă goală, după care se adaugă cinci valori flotante din spate:
coadă<pluti>acea;acea.Apăsați(1.1);
acea.Apăsați(2.2);
acea.Apăsați(3.3);
acea.Apăsați(4.4);
acea.Apăsați(5.5);
size () const
Aceasta returnează numărul de elemente din coadă. Următorul cod ilustrează:
coadă<pluti>acea;acea.Apăsați(1.1);acea.Apăsați(2.2);acea.Apăsați(3.3);acea.Apăsați(4.4);acea.Apăsați(5.5);
cost<<acea.mărimea() << ' n';
Ieșirea este 5.
față()
Aceasta returnează o referință la primul element al cozii, fără a elimina elementul. Ieșirea următorului cod este 1.1.
coadă<pluti>acea;acea.Apăsați(1.1);acea.Apăsați(2.2);acea.Apăsați(3.3);acea.Apăsați(4.4);acea.Apăsați(5.5);
cost<<acea.față() << ' n';
Elementul nu este eliminat din coadă.
front () const
Când construcția cozii este precedată de const, expresia front () const este executată în loc de front (). Este folosit, de exemplu, în următorul cod.
constcoadă<pluti>acea({1.1, 2.2, 3.3, 4.4, 5.5});cost<<acea.față() << ' n';
Se returnează o referință constantă. Elementul nu este eliminat din vector. Elementele cozii nu pot fi modificate.
înapoi()
Aceasta returnează o referință la ultimul element al cozii, fără a elimina elementul. Ieșirea următorului cod este 5.5.
coadă<pluti>acea;acea.Apăsați(1.1);acea.Apăsați(2.2);acea.Apăsați(3.3);acea.Apăsați(4.4);acea.Apăsați(5.5);
cost<<acea.înapoi() << ' n';
back () const
Când construcția cozii este precedată de const, expresia back () const este executată în loc de back (). Este folosit, de exemplu, în următorul cod.
constcoadă<pluti>acea({1.1, 2.2, 3.3, 4.4, 5.5});cost<<acea.înapoi() << ' n';
Se returnează o referință constantă. Elementul nu este eliminat din coadă. Cu constanta precedentă pentru construcția cozii, elementele din coadă nu pot fi modificate.
Capacitate coadă
size () const
- Vezi deasupra
empty () const
Aceasta returnează 1 pentru adevărat dacă nu există elemente în coadă sau 0 pentru fals dacă coada este goală. Următorul cod ilustrează acest lucru:
coadă<pluti>că1({1.1, 2.2, 3.3, 4.4, 5.5});cost<<că1.gol() << ' n';
coadă<pluti>că2;
cost<<că2.gol() << ' n';
Ieșirea este:
01
Modificatori de coadă
pop ()
O coadă este FIFO, deci orice element care trebuie eliminat trebuie eliminat din partea de sus (cap) a cozii. Această funcție membru elimină primul element fără a-l returna. Următorul cod ilustrează acest lucru:
coadă<pluti>acea({1.1, 2.2, 3.3, 4.4, 5.5});cost<<acea.față() << ' n';
acea.pop();
cost<<acea.mărimea() << ' n';
Ieșirea este:
1.14
a. swap (b)
Două cozi pot fi schimbate, după cum este ilustrat în acest segment de cod:
coadă<pluti>că1({1.1, 2.2, 3.3, 4.4, 5.5});coadă<pluti>că2({10, douăzeci});
că1.swap(că2);
cost<< „Primul element și dimensiunea que1:
'<<că1.față() <<','<<că1.mărimea() << ' n';
cost<< „Primul element și dimensiunea que2”<<
că2.față() <<','<<că2.mărimea() << ' n';
Ieșirea este:
Primul element și dimensiunea que1: 10, 2
Primul element și dimensiunea que2: 1.1, 5
Rețineți că lungimea unei cozi este mărită, dacă este necesar. De asemenea, valorile care nu au avut înlocuiri sunt înlocuite cu o valoare implicită. Tipurile de date trebuie să fie de același tip.
Egalitatea și operatorii relaționali pentru cozi
Pentru caracterele obișnuite în C ++, în ordine crescătoare, numerele vin înaintea literelor mari, care vin înainte de literele mici. Caracterul spațial vine înainte de zero și de toate.
Operatori de egalitate
Returnează 1 pentru adevărat și 0 pentru fals.
Operatorul ==
Returnează 1 dacă cele două cozi au aceeași dimensiune și elementele corespunzătoare sunt egale; altfel returnează 0. Exemplu:
coadă<const char*>că1({'drăguț', 'altceva'});coadă<const char*>că2({'rău'});
intpe unu=că1==că2;
cost<<pe unu<< ' n';
Ieșirea este: 0.
Operatorul! =
- opus celor de mai sus. Exemplu:
coadă<const char*>că1({'drăguț', 'altceva'});coadă<const char*>că2({'rău'});
intpe unu=că1! =că2;
cost<<pe unu<< ' n';
Ieșirea este: 1.
Operatori relaționali
Returnează 1 pentru adevărat și 0 pentru fals.
The
Returnează 1 dacă prima coadă este subsetul inițial al celei de-a doua cozi, elementele celor două porțiuni egale fiind aceleași și în aceeași ordine. Dacă ambele cozi au aceeași dimensiune sau dimensiuni diferite și se deplasează de la stânga la dreapta, un element este întâlnit în prima coadă care este mai mic decât elementul corespunzător din a doua coadă, atunci 1 va fi totuși returnat. Altfel se returnează 0. Exemplu:
coadă<const char*>că1({'drăguț', 'altceva'});coadă<const char*>că2({'rău'});
intpe unu=că1<că2;
cost<<pe unu<< ' n';
Ieșirea este 1. > Operatorul - opus celor de mai sus. Exemplu: Ieșire: 0 The<= Operator - la fel ca Ieșire: 1 Operatorul> = - opus celor de mai sus. Exemplu: Ieșire: 0 O valoare este pentru un tip de date, așa cum un obiect instanțiat este pentru o clasă. Construcția cozii poate accepta, de asemenea, o clasă ca tip de date. Următorul program ilustrează acest lucru: Ieșirea este 5. Lista de cozi se numește tehnic o listă legată. Există două tipuri de liste legate pentru coadă: listă legată individual și listă legată dublu. Un element de listă legat individual poate fi implementat de o structură de doi membri. Un membru deține un pointer către elementul următor, iar celălalt membru deține datum (singular pentru date). Un element de listă dublu legat poate fi implementat de o structură de trei membri. Membrul mijlociu deține baza de date, în timp ce primul și al treilea membru dețin indicatori către elementele lor adiacente. Coada este o structură de date first-in-first-out. Există situații în calcul când datele sosesc sub forma unei cozi, necesitând un comportament primul-în-primul-ieșit. O resursă dintr-un computer este orice componentă fizică sau virtuală cu disponibilitate limitată. Acestea includ procesorul, placa video, hard diskul și memoria. Partajarea unei astfel de resurse necesită o coadă. Perifericele computerului trebuie să întrerupă computerul din când în când. Întreruperile trebuie gestionate în același mod în care au ajuns. Aceasta are nevoie de o coadă. Coada poate fi utilizată, de exemplu, pentru a gestiona fișierele aplicației pentru o lucrare, dacă fișierele sunt stocate în computer. O coadă este o structură de date a listei, care este fie o listă legată individual, fie o listă dublă legată. De regulă, primul element care intră în listă este primul element care iese. C ++ oferă o structură de date în coadă în biblioteca sa standard. Categoriile de funcții membre și operatori disponibile pentru această structură sunt construcția cozii, accesul la elementele cozii, capacitatea cozii, modificatorii cozii și operatorii supraîncărcați. Orice structură de date în coadă trebuie să ofere cel puțin funcțiile de membru push () și pop (). push () înseamnă, trimiterea unui element nou în spatele cozii; și pop () înseamnă, eliminând elementul care se află în partea din față a cozii. Din păcate, în C ++, aceste funcții nu returnează valoarea împinsă sau pop-up. Deci, pentru a cunoaște ultimul element înainte de a împinge, trebuie folosită funcția extra back (); și pentru a cunoaște primul element înainte de popping, trebuie folosită funcția extra front (). O valoare este pentru un tip de date, așa cum un obiect instanțiat este pentru o clasă. Deci, o anumită clasă poate fi utilizată ca tip de date pentru instanțierea șablonului de coadă. Diferite obiecte pentru clasă devin ca valori diferite pentru clasă. Coada are aplicații pe computer. Poate fi folosit, de exemplu, pentru a gestiona fișiere de aplicații pentru o lucrare, dacă fișierele sunt stocate în computer. Chrys
coadă<const char*>că2({'rău'});
intpe unu=că1>că2;
cost<<pe unu<< ' n';
coadă<const char*>că2({'rău'});
intpe unu=că1<=că2;
cost<<pe unu<< ' n';
coadă<const char*>că2({'rău'});
intpe unu=că1> =că2;
cost<<pe unu<< ' n'; Class și obiectele sale instanțiate
#include
folosind spațiul de nume std;
clasa TheCla
{
public:
intpe unu;
static charcap;
nulfunc(charNu, const char *str)
{
cost<< 'Sunt ' <<pe unu<< „cărți care merită” <<Nu<<str<< ' in magazin.' << ' n';
}
static nuldistracţie(charcap)
{
dacă (cap== 'la')
cost<< „Funcția statică oficială de membru” << ' n';
}
};
intprincipal()
{
TheCla obj1;TheCla obj2;TheCla obj3;TheCla obj4;TheCla obj5;
coadă<TheCla>acea;
acea.Apăsați(obj1);acea.Apăsați(obj2);acea.Apăsați(obj3);acea.Apăsați(obj4);acea.Apăsați(obj5);
cost<<acea.mărimea() << ' n';
întoarcere 0;
} Listă legată
Aplicațiile cozii
Partajarea resurselor informatice
Manipularea întreruperilor
Gestionați informațiile.
Concluzie