Bevezetés

Az adatszerkezetek úgy szervezik a tárolást a számítógépekben, hogy az adatokhoz hatékonyan hozzáférhessünk és módosíthassuk azokat. A veremek és a sorok a számítástechnikában definiált legkorábbi adatszerkezetek közé tartoznak.

Egyszerűen megtanulható és könnyen megvalósítható, használatuk gyakori, és nagy valószínűséggel te is bele fogod építeni őket a szoftveredbe különböző feladatokhoz.

A veremeket és sorokat általában tömbökkel vagy kapcsolt listákkal valósítják meg. Mi a List adatszerkezetre támaszkodunk, hogy mind a Stack-eket, mind a Queue-okat befogadjuk.

Hogyan működnek?

Stack

A Stack-ek, ahogy a nevük is mutatja, a Last-in-First-Out (LIFO) elvet követik. Mintha érméket raknánk egymásra, az utolsó érmét, amit a tetejére teszünk, később elsőként távolítjuk el a veremről.

A verem megvalósításához tehát két egyszerű műveletre van szükségünk:

• push – hozzáad egy elemet a verem tetejére:

• pop – eltávolítja a verem tetején lévő elemet:

Queue

A sorok, ahogy a neve is mutatja, a FIFO (First-in-First-Out) elvet követik. Mintha sorban állnánk a mozijegyekért, aki először áll sorba, az vehet jegyet és élvezheti a filmet.

A sorban állás megvalósításához tehát két egyszerű műveletre van szükségünk:

• enqueue – hozzáad egy elemet a sor végéhez:

• dequeue – eltávolítja a sor elején lévő elemet:

Stack and Queue using Lists

Python beépített List adatszerkezete olyan módszereket tartalmaz, amelyek mind a stack, mind a queue műveleteket szimulálják.

Lássunk egy levelekből álló veremet:

Ezekkel a függvényekkel megvalósíthatunk egy várólistát is. A pop függvény opcionálisan argumentumként elfogadja a lekérdezni kívánt elem indexét.

Így használhatjuk a pop függvényt a lista első indexével, azaz 0, hogy sorban állásszerű viselkedést kapjunk.

Gondoljunk egy gyümölcsökből álló “sorba”:

Itt is a lista append és pop műveleteit használjuk, hogy szimuláljuk a várólista alapvető műveleteit.

Folyók és sorok a Deque könyvtárral

Python rendelkezik egy deque (ejtsd: ‘pakli’) könyvtárral, amely egy sor hatékony módszerekkel biztosítja a halomként vagy várólistaként való működést.

deque a Double Ended Queue rövidítése – egy általánosított várólista, amely az első vagy az utolsó tárolt elemet kaphatja meg:

Ha többet szeretnél megtudni a deque könyvtárról és a Python által biztosított más típusú gyűjteményekről, akkor olvasd el a Bevezetés a Python gyűjtemények moduljába című cikkünket.

Stricter implementációk Pythonban

Ha a kódodnak szüksége volt egy veremre, és biztosítasz egy List-t, semmi sem akadályozza meg a programozót abban, hogy meghívja a insert, remove vagy más listafunkciókat, amelyek befolyásolják a verem sorrendjét! Ez alapvetően tönkreteszi a verem definiálásának értelmét, mivel az már nem úgy működik, ahogyan kellene.

Vannak olyan esetek, amikor szeretnénk biztosítani, hogy csak érvényes műveleteket hajthassunk végre az adatainkon.

Létrehozhatunk olyan osztályokat, amelyek csak a szükséges metódusokat tárják fel az egyes adatstruktúrákhoz.

Ezért hozzunk létre egy új, stack_queue.py nevű fájlt, és definiáljunk két osztályt:

A Stack és Queue osztályainkat használó programozókat most arra ösztönözzük, hogy inkább a megadott metódusokat használják az adatok manipulálására.

Példák

Képzeljük el, hogy egy fejlesztő egy vadonatúj szövegszerkesztőn dolgozik. Azt a feladatot kapod, hogy hozz létre egy visszavonási funkciót – amely lehetővé teszi a felhasználók számára, hogy a műveleteiket a munkamenet elejéig visszamenőleg elvégezhessék.

A stack ideális erre a forgatókönyvre. A felhasználó minden egyes műveletét rögzíthetjük a verembe tolva. Amikor a felhasználó vissza akar vonni egy műveletet, akkor azt a veremből kiugrik. A funkciót gyorsan szimulálhatjuk így:

A sorozatoknak a programozásban is széles körben elterjedt felhasználási területei vannak. Gondoljunk csak az olyan játékokra, mint a Street Fighter vagy a Super Smash Brothers. Ezekben a játékokban a játékosok speciális mozdulatokat hajthatnak végre gombok kombinációjának megnyomásával. Ezeket a gombkombinációkat egy sorban lehet tárolni.

Most képzeld el, hogy egy fejlesztő vagy, aki egy új verekedős játékon dolgozik. A játékodban minden alkalommal, amikor egy gombot megnyomnak, egy bemeneti eseményt lőnek ki. Egy tesztelő észrevette, hogy ha túl gyorsan nyomod meg a gombokat, a játék csak az elsőt dolgozza fel, és a speciális mozdulatok nem működnek!

Ezt egy várólistával meg tudod oldani. Minden beviteli eseményt sorba tudunk állítani, ahogy beérkeznek. Így nem számít, ha a bemeneti események kis időközzel érkeznek, mindegyik tárolva lesz és feldolgozható. Amikor feldolgozzuk a mozgásokat, akkor törölhetjük őket a sorból. Egy speciális lépés így dolgozható ki:

Következtetés

A verem és a várólisták egyszerű adatstruktúrák, amelyek lehetővé teszik számunkra az adatok szekvenciális tárolását és kinyerését. Egy veremben az utolsó elem, amit beviszünk, az jön ki elsőként. Egy sorban az első elem, amit beírunk, az jön ki elsőként.

Egy veremhez a push művelettel adhatunk hozzá elemeket, és a pop művelettel hívhatunk le elemeket. A sorok esetében a enqueue művelettel adunk hozzá elemeket, és a dequeue művelettel hívunk elő elemeket.

A Pythonban a veremeket és a sorokat egyszerűen a beépített List adatszerkezet használatával valósíthatjuk meg. A Python rendelkezik a deque könyvtárral is, amely hatékonyan képes stack és queue műveleteket biztosítani egy objektumban. Végül pedig elkészítettük a verem és a várólista osztályainkat az adataink szigorúbb ellenőrzése érdekében.

A veremeknek és a várólistáknak számos valós felhasználási esete van, megértésük lehetővé teszi számunkra, hogy számos adattárolási problémát egyszerűen és hatékonyan oldjunk meg.