Pe scurt despre ce este un stack. Acesta este un tip de date în care acestea sunt organizate în conformitate cu principiul LIFO (ultimul out-first out). În vorbitoare de limbă rusă, a venit ultimul, a ieșit mai întâi. Un excelent exemplu de vizualizare este un teanc de cărți, a venit cartea de sus și dacă nu o să speriați pisica cu un zgomot, primul a plecat.
Implementarea celor mai simple structuri de date este o modalitate foarte bună de a le studia. Puteți citi o sută de cărți despre stack, dar până când o veți scrie singur, nu veți fi prieteni. Am scris o implementare în limba de programare C ++ utilizând clase. Două stive sunt două clase și, dacă doriți, puteți să le împachetați într-un fișier separat și să vă conectați la alte proiecte.
Dragi cititori, să ne facem prieteni cu stackul, hai să mergem!
Funcțiile stivei
împingeți elementul deasupra stivei;
pop - scoateți elementul de sus;
sus - returnați elementul în partea de sus fără a îl elimina de acolo;
dimensiune - returnați mărimea stivei.
Implementarea unui stive bazate pe matrice
Ideea este că datele sunt stocate într-o rețea normală, dar accesul la ele este strict reglementat de noi prin utilizarea funcțiilor. Neajunsul imens este că mărimea stivei este limitată. Este rezolvată folosind matrice extensibile. Când spațiul din matrice se termină, o nouă zonă de memorie de dimensiune mai mare este pur și simplu alocată și totul este copiat acolo. Din câte știu, în biblioteca STL, stiva este implementată pe rețelele extensibile.
Codul sursă C ++
Implementarea unui teanc bazat pe o listă liniară
Lista liniară este o structură de date foarte populară, chiar dacă nu este foarte rapidă. Foarte des se întâmplă în implementarea funcțiilor sistemului. Viteza de lucru este compensată prin flexibilitate. Lista este pur și simplu conectată, realizăm setul minimal de funcții, despre care am vorbit mai devreme. Avantaj incontestabil față de matrice - dimensiunea maximă a stivei este nelimitată.
Codul sursă C ++
Testarea performanțelor
A implementat două stive, un păcat cu ei, pentru a nu fi răsfățat. Să vedem care funcționează mai repede. Și comparați viteza de lucru cu stivuirea STL. dar dacă am reușit să implementăm mai repede?
Funcția de testare
concluzie
Această dimensiune de stivă a fost selectat experimental, cu o cantitate mai mare de sistemul meu tocmai sa prăbușit, întreaga resursă de sistem din stânga în testul (bănuiesc că cant Ubuntu). Ce vedem? matrice noastre bazate pe stiva de toate udelal, iar acest lucru nu este surprinzător, deoarece STL-stiva este extensibil, și Dumnezeu știe cât de multe resurse pe care le-a petrecut pe extinderea în acest test. Stack-ul nostru a fost cel mai rapid, dar nu foarte flexibil. În principiu, dacă dimensiunea datelor de intrare este cunoscută în prealabil și neschimbată, puteți utiliza această implementare.
Tema este bătută și veche, ca lumea, dar mi-am făcut contribuția. Nu pierdeți același cod, nu? Sper că oricine va avea nevoie de experiența mea, vă mulțumesc pentru atenție!
Trimiteți-le prietenilor: