Shpjegoni në teori dhe zbatimin e strukturës së të dhënave të stackit dhe radhës.

Prezantimi

Përshëndetje, siç premtova, sot do të flasim për dy strukturat themelore të të dhënave: Stack dhe Queue. Këto dy struktura të dhënash janë thelbësore për shumë algoritme si kalimet e pemëve dhe grafikëve, renditja topologjike dhe shumë gjëra të tjera interesante. Të kuptosh në thellësi këto dy struktura të dhënash do të thotë të ndërtosh një bazë të mirë për njohuritë e tua të programimit.

Në implementim, unë do të përdorja Listën e Lidhur si zbatimin bazë për këto struktura të dhënash. Nëse nuk jeni të njohur me Listën e Lidhur, mos ngurroni t'i referoheni artikullit tim në lidhje me këtë strukturë të të dhënave. Mirë, le të hyjmë në të!

Çfarë është një Stack?

Një Stack është një kontejnerë objektesh ku objektet operohen duke ndjekur rendin First In Last Out (FILO) ose Last In First Out (LIFO). Hmm, kjo tingëllon mjaft konfuze, apo jo? Një shembull i thjeshtë që mund të mendoni është një pirg librash në një bibliotekë. Libri i parë që vendosni në pirg do të ishte libri i fundit që mund të përdorni. Nga këtu vjen urdhri FILO.

Këtu është një fotografi e mirë që gjeta që mendoj se përfaqëson më së miri këtë strukturë të të dhënave:

Stacki ka vetëm një pikë fundore aksesi, ne e quajmë atë maja e pirgut.

Stack mbështet disa operacione që na lejojnë të luajmë me këtë strukturë të dhënash. Unë do të prezantoj 5 operacionet kryesore: push, pop, peek, getSize dhe isEmpty. Ne do të shqyrtojmë detajet e këtyre 5 operacioneve në pjesën tjetër.

Zbatimi i stivit

Mirë, nuk do të presim më, koha për pjesën emocionuese!

Le të përcaktojmë një strukturë të të dhënave të pirgut. Por së pari, ne duhet të përcaktojmë komponentin bazë të një pirg: një nyje

Një nyje do të përmbajë një fushë të dhëna dhe një tregues për elementin e ardhshëmnë pirg. Tani, ne mund të përcaktojmë strukturën tonë të të dhënave të stivës me një tregues bosh lartë dhe një madhësi zero:

Tani, ne kemi pirgun, le ta bëjmë këtë rafte interesante duke i prezantuar disa sjellje të reja, apo jo? Tre funksionet e para që mund të mendohen lehtësisht janë marrja e madhësisë së kësaj rafte, kontrollimi nëse pirgu është bosh dhe marrja e elementit të sipërm të pirgut.

Këto tre funksione janë mjaft të drejtpërdrejta, apo jo? Pra, tani, ne kalojmë te dy funksionet që e bëjnë grupin unik: shtytje dhe pop.

push(të dhëna): ky funksion merr një pjesë të të dhënave dhe e shtyn atë në krye të stivit

Sipas diagramit, për këtë metodë, ne në thelb bëjmë tre gjëra:

  1. Lidhni treguesin tjetër të nyjës së shtuar me treguesin aktual lart.
  2. Cakto treguesin e ri lart.
  3. Rritni madhësinëtë pirgut.

pop(): ky funksion nxjerr elementin e parë nga grumbulli dhe e kthen atë.

Sipas diagramit, ne kemi tre hapa në këtë metodë:

  1. Ruani nyjen e hequr.
  2. Ndrysho treguesin lart.
  3. Zvogëloni madhësinë me 1.

Në këtë zbatim, unë kam një kontroll sanitar për të siguruar që një pirg i zbrazët nuk mund të shfaqet. Nuk janë aspak të zbukuruara, apo jo? Më pas, do të diskutojmë strukturën e të dhënave të Radhës.

Çfarë është një Radhë?

Ashtu si një Stack, një Radhë është gjithashtu një enë objektesh ku shtimi dhe heqja e elementeve ndjek një renditje specifike. Megjithatë, në vend që të ndjekë rendin First In Last Out (FILO), një Radhë vendos një urdhër First In First (FIFO) për operacionet e tyre.

Nëse jeni njohur me Stack deri tani, të kuptuarit e Queue do të jetë aq e lehtë sa të hash një copë tortë. Ju mund të mendoni për një radhë studentësh në kafene. Studenti i parë në linjë do të shërbehet i pari.

Struktura e të dhënave në radhë ka dy pika aksesi: përpara dhe prapa. Përdoruesi mund t'i qaset lehtësisht të dhënave nga koka dhe fundi i një radhe.

Një Radhë zotëron gjithashtu disa metoda me të cilat mund të luajmë. Unë do të prezantoj disa prej tyre: në radhë, dequeue, getFront, getRear, getSize, isEmpty. Mirë, jam shumë i emocionuar, le të zhytemi në zbatimin.

Zbatimi i radhës

Siç e përmenda më parë, ne do të përdorim Listën e Lidhur për të zbatuar një Radhë ashtu si një Stack. Prandaj, do të kapërcej përkufizimin e klasës Node dhe do të filloj të zhytem në përkufizimin e klasës Queue me topdhe rear tregues së bashku me një madhësi prej 0:

Tani, ne kemi strukturën e të dhënave Queue, le ta bëjmë më interesante duke i dhënë disa sjellje, apo jo? Ngjashëm me një Stack, ne mund të përcaktojmë disa metoda që kontrollojnë nëse radha është bosh, ose marrim madhësinë e radhës, ose aksesin në pjesën e përparme dhe të pasme të radhës.

Shumë e lehtë, apo jo? Por pjesa emocionuese nuk do të përfundojë këtu. Ne do të përcaktojmë dy operacionet kryesore që e bëjnë një Radhë unike: radhë dhe dequeue.

radhë(të dhëna): shtoni një pjesë të re të të dhënave në pjesën e pasme të radhës.

Sipas diagramit, ka tre hapa të përfshirë në këtë funksion:

  1. Vendosni treguesin tjetër të rear në nyjen e shtuar.
  2. Vendosni treguesin e pasme në nyjen e shtuar rishtazi.
  3. Rritni madhësinë me 1.

Ekziston një rast i skajshëm që duhet të mbulojmë: kur radha është bosh. Kur kjo të ndodhë, algoritmi i mëparshëm nuk do të funksionojë. Ajo që duhet të bëjmë është të vendosim treguesit para dhe të pasëm tek nyja e shtuar.

dequeue(): nxirr elementin e përparmë nga radha dhe ktheje atë.

Sipas diagramit, përfshihen tre hapa:

  1. Ruaje treguesin përpara si treguesin e hequr.
  2. Vendosni treguesin përpara në treguesin tjetër.
  3. Zvogëloni madhësinë me 1.

Njësoj si funksioni enqueue, ne duhet të trajtojmë rastin e skajit kur ka vetëm një element në radhë: duhet t'i vendosim të dyja front dhe prapa te Asnjë. Gjithashtu, duhet të bëjmë një kontroll sanitar për t'u siguruar që nuk do të heqim një radhë bosh.

Më në fund, ne kemi përfunduar zbatimin tonë të strukturës së të dhënave Stack dhe Queue. Nëse e keni ndjekur deri në këtë pikë, atëherë punë të mbarë! I gjithë kodi burimor vendoset në këtë lidhje Github për referencën tuaj. Në kodin burim, kam shtuar disa teste shtesë për funksionet tona. Mos ngurroni të luani me këto teste për të përmirësuar kuptimin tuaj të këtyre dy strukturave të të dhënave.

Analiza e kompleksitetit të kohës së ekzekutimit dhe kompleksitetit të hapësirës

Analiza e kohës dhe hapësirës luajnë rolin më të rëndësishëm në një algoritëm. Këto matje tregojnë avantazhet dhe disavantazhet e përdorimit të algoritmit.

Është një mrekulli që të dy operacionet e Stack-it dhe të Radhës ekzekutohen në kohë O(1) (konstante) dhe zënë hapësirën O(1) (konstante) (nëse nuk llogarisim kontejnerin që "përmban të gjitha objektet). Kjo i jep Stack and Queue avantazhin kur trajtojnë aksesin e të dhënave që ndjekin një renditje specifike (FILO ose FIFO), pasi ato mund të funksionojnë shumë shpejt dhe të zënë kaq pak hapësirë ​​shtesë.

konkluzioni

Kaq për këtë artikull! Shpresoj se mund të mësoni diçka të dobishme nga postimi im. Kuptimi i Stack dhe Queue do t'ju japë një avantazh të madh kur mësoni struktura dhe algoritme të tjera komplekse të të dhënave më vonë. Argëtohu me Stack and Queue dhe shihemi herën tjetër!

Referenca

[1]: Python Stack and Queue: https://www.javatpoint.com/python-stack-and-queue