Egy köteg végrehajtása tömbön és lineáris listán

Kedves nappali! Ma egy nagyon egyszerű dolog megvalósítását nézzük - a saját verem egy tömb alapján és egy lineáris lista alapján. A kódot írtam nekem a második évben, régen, a cikk megírása előtt lefújtam a port és kicsit korrigáltam a változók szörnyű nevét, irányítottam a maratont. Most azonban megmutatható, bár óvatosan.

Röviden, hogy mi a verem. Ez egyfajta adat, amelyben a LIFO elvének megfelelően kerülnek sorba (utoljára az első ki). Oroszul beszélt, utoljára jött, először jött ki. Kiváló példája a vizualizációnak egy könyvecsomag, a legfontosabb könyv, és ha nem akarod megijeszteni a macskát, akkor az első maradt.

A legegyszerűbb adatszerkezetek megvalósítása kiváló módja annak tanulmányozásához. Olvasta el száz könyvet a veremről, de amíg maga meg nem írja, nem leszek barát. A C ++ programnyelvben egy bevezetést írtam osztályok segítségével. Két stack két osztály, és ha akarod, külön csomagba csomagolhatod őket, és csatlakozhatsz más projektekhez.

Tisztelt olvasók, barátkozzunk a verembe, menjünk!

Stack funkciók

nyomja meg - tegye az elemet a verem tetejére;
pop - távolítsa el az elemet a tetejéről;
tetejére - tegye vissza az elemet a tetejére anélkül, hogy eltávolítaná azt;
méret - visszaadja a köteg méretét.

Tömb alapú verem megvalósítása

Az ötlet az, hogy az adatokat egy normál tömbben tárolják, de a hozzáférést rájuk szigorúan szabályozza. A hatalmas hátrány az, hogy a verem mérete korlátozott. Ez megoldható bővíthető tömbökkel. Amikor a tömb helyzete befejeződik, egy nagyobb méretű memória új területét egyszerűen kiosztják, és mindent átmásolnak ott. Amennyire én tudom, az STL könyvtárban a verem bővíthető tömbökön valósul meg.

C ++ forráskód

Egy köteg megvalósítása lineáris listán alapulva

A lineáris lista nagyon népszerű adatstruktúra, bár nem túl gyors. Nagyon gyakran fordul elő a rendszerfunkciók végrehajtása. A munka sebességét a rugalmasság kompenzálja. A lista egyszerűen kapcsolódik, rájövünk a minimális funkciókra, amelyekről korábban beszéltem. Kérdéses előny a tömb felett - a verem maximális mérete korlátlan.

C ++ forráskód

Teljesítményvizsgálat

Végrehajtott két halom, egy bűn azzal, hogy ne kényszerítsék őket. Lássuk, melyik dolgozik gyorsabban. És hasonlítsa össze munkájuk sebességét az STL kötegével. de mi lenne, ha gyorsabban sikerült végrehajtanunk?

Tesztfunkció

következtetés

Ilyen veremméretet választottam kísérletileg, nagyobb méretben, rendszerem csak leesett, az egész rendszer erőforrása bejutott a tesztbe (gyanítom, hogy ez egy jamb ubunt). Mit látunk? A tömb alapjain mindent megtettünk, és ez nem meglepő, hiszen az STL-verem kiterjeszthető, és Isten tudja, mennyi erőforrást költött a kiterjesztésekre ebben a tesztben. A tömbünk a leggyorsabb, de egyáltalán nem rugalmas. Elvben, ha a bemeneti adatok mérete előre ismert és változatlan, akkor ezt a megvalósítást használhatja.

A témát megverték és régiek, mint a világ, de hozzájárultam. Ne pazarolja ugyanazt a kódot, ugye? Remélem, hogy bárki is szüksége lesz az én tapasztalataimra, köszönöm figyelmedet!