Apstraktās datu struktūras –

• Kaudzes (stacks)

• un Rindas (Queues)

Tātad, kāda ir atšķirība starp kaudzi (stack) un rindu (queue)? Un ko nozīmē izmantot vienu no šīm datu struktūrām, nevis citas?

Šajā rakstā jūs uzzināsiet par kaudzēm un rindām. Atšķirība starp abiem un kāpēc jūs varētu izvēlēties izmantot vienu, nevis otru atkarībā no risinājuma prasībām. Stacks jeb kaudzes un Queue jeb rindas ir abstraktas datu struktūras, kurām ir daudz dažādu implementāciju atkarībā no programmēšanas valodas. Unikālie principi, kas ir kopīgi abiem, ir elementu pievienošana un noņemšana.

Lai gan saraksti un masīvi nodrošina nejaušu piekļuvi, kaudzes un rindas izmanto secīgu piekļuvi.

Šī ierobežotā pieeja datu glabāšanai var būt ļoti noderīga, ja vēlaties kontrolēt, kā datiem tiek piekļūts. Sāksim ar kaudzīšu izpēti nedaudz sīkāk.

Stack, jeb kaudze

Stacks ir lineāras datu struktūras ar stingriem vienumu pievienošanas un noņemšanas veidiem. Kā norāda nosaukums, kaudze ir elementu kopums, kas ir sakrauti viens virs otra. Tas nozīmē, ka nav iespējams izvilkt priekšmetus no vidus. Tā vietā stack darbojas ar stingru First-In, Last-Out (Pirmais iekšā, Pēdējais ārā) vai FILO principu. To var arī formulēt kā Last-In, First-Out (Pēdējais iekšā, Pirmais ārā) vai LIFO. Tā ir vienkārša, taču jaudīga koncepcija, kas informē, ka vienumus var izgūt tikai no kaudzes augšdaļas, kas nosaka secību, kādā varat tos izgūt. Šī principa piemērs darbībā ir Ctrl+Z nospiešana URL, Word dokumentā vai jebkurā kodēšanas vidē. Ctrl+Z atceļ pašu pēdējo darbību. Nospiežot to vēlreiz, tiks atsaukta iepriekšējā darbība un tā tālāk. Lai paplašinātu analoģiju, Ctrl+Y atkārtos darbību vai nospiedīs to, pievienojot to atpakaļ kaudzītei. Stackiem parasti ir ļoti maz metožu:

• Push, – Pievienot
• Pop, – Noņemt
• isEmpty, Pārbauda
• isFull – Boolean vaicājums
• un Peek. – Palūrēt/Apskatīt

Šo metožu funkcijas korelē ar to nosaukumiem, push pievienos vienumu stakam un pop noņems. isEmpty, pārbauda, vai kaudzē nav nekā. Un isFull ir Būlean vērtība, kas atgriezīsies kā (true) patiesa, ja kaudzē vairs nebūs vietas.

Iespējams, esat dzirdējuši par populāro datora jautājumu un atbilžu platformu, kas nosaukta tieši šīs problēmas vārdā, proti, StackOverflow , (Jeb Kaudzes pārplūde). Tātad, izlaižot vienumu, paņemot to no kaudzes augšdaļas un vēlreiz izsaucot Pop, tiks atgriezts nākamais vienums kaudzē. Popu var saukt tik ilgi, kamēr stekā nekas nav palicis. Nospiežot, vienums tiks novietots kaudzes augšpusē. Ir vērts atzīmēt, ka, izsaucot pop vai push, jūs maināt steku.

Tagad esat uzzinājis par visām metodēm, izņemot palūrēšanu Peek…

Palūrēt/Apskatīt – PEEK

Tātad, ko tas nozīmē? Lai apskatītu saturu, var saukt par peek, kas ļauj skatīt augšējo vienumu, neizņemot to no kaudzes. Tā izsaukšana nemainīs struktūras stāvokli atšķirībā no pop vai push, kas neatgriezeniski maina steku. Dažās implementācijās būs iekļauta meklēšanas funkcija, lai pārlūkotu steku, lai gan tas ne vienmēr notiks. Tagad izpētīsim piemēru.

Iedomājieties, ka lietojumprogramma ģenerēja kāršu komplektu, jūs varat izveidot 52 spēļu kāršu kaudzi, un katru reizi, kad tiek izdalīta kārts, tā tiek noņemta no kaudzes augšdaļas, tāpat kā īstā kāršu kavā. Izmantojot steku šādā veidā, tiktu vienkāršots kods, kas nepieciešams klāja stāvokļa uzturēšanai.

Vienkāršs piemērs JavaScript Stack:

class Stack {
constructor() {
// izveido jaunu tukšu masīvu
this.items = [];
}
push(element) {
// pievieno elementu virsū
this.items.push(element);
}
pop() {
// pārbauda, vai masīvā ir elementi
if (this.items.length == 0)
return "Underflow";
// izņem elementu no virsmas
return this.items.pop();
}
}

Rinda, jeb Queue

Tagad izpētīsim rindas. Rinda ir ļoti līdzīga stack kaudzei, jo tai mēdz būt tādas pašas metodes. Tas var izveidot, ievietot, noņemt un pārbaudīt rindas stāvokli. Atšķirībā no kaudzes, rinda darbojas pēc principa First-In, First-Out (Pirmais iekšā, Pirmais ārā) vai FIFO. Atkal, nosaukums ir labs rādītājs tam, kā struktūra darbojas.

Piemēram, iedomājieties, ka ātrās ēdināšanas restorānā ir cilvēku rinda, kas gaida, lai saņemtu burgeru. Pirmā persona, kas ieiet rindā, tiek apkalpota, un katrs nākamais klients stāv aiz priekšā esošā un tiek apkalpots pēc kārtas. Tāpat kā ar stack, rinda izliks atlasīto vienumu no struktūras, lai gan dažādās valodās tas tiek īstenots atšķirīgi. Elements, kas tiek noņemts no rindas, ir apakšā. Citiem vārdiem sakot, vismazāk pievienotais vienums vai pirmais, kas pievienojās rindai. Izmantojot reālās pasaules IT piemēru, serveru balansēšanas sistēma uzdevumu izgūšanai parasti izmanto rindu. Struktūra saturēs katru uzdevumu ievietošanas secībā. Kad uzdevuma apstrādei kļūst pieejams serveris, pirmais rindā ievadītais uzdevums tiks noņemts un nosūtīts šim serverim.

Vienkāršs JavaScript piemērs Queue klasei:

class Queue {
constructor() {
// izveido jaunu tukšu masīvu
this.items = [];
}
enqueue(element) {
// pievieno elementu rindā
this.items.push(element);
}
dequeue() {
// pārbauda, vai masīvā ir elementi
if (this.isEmpty())
return "Underflow";
// izņem elementu no rindas
return this.items.shift();
}
front() {
// pārbauda, vai masīvā ir elementi
if (this.isEmpty())
return "No elements in Queue";
// atgriež pirmo elementu rindā
return this.items[0];
}
isEmpty() {
// pārbauda, vai masīvā ir elementi
return this.items.length == 0;
}
}

Šajā piemērā ir izveidota Queue klase ar enqueue, dequeue, front un isEmpty metodēm. enqueue metode pievieno elementu rindā, dequeue metode izņem elementu no rindas, front metode atgriež pirmo elementu rindā un isEmpty metode pārbauda, vai rinda ir tukša.

Šajā raksta daļā jūs uzzinājāt par kaudzēm (stack) un rindām (Queue), kā arī par atšķirībām starp tām. Šie ir ļoti noderīgi rīki, kas jāiekļauj jūsu programmēšanas rīku komplektā, un to pārzināšana būs priekšrocība, risinot problēmas, kurām nepieciešams strukturēts datu piekļuves un ievietošanas veids.

Stacks un Queues dažādās programmēšanas valodās

Stacks ir pamata datu struktūra, kas ierobežo veidu, kā dati tiek glabāti lietojumprogrammā. Proti, precēm ir jāatbilst iebraukšanas vai izvešanas politikai, kas ir “pēdējais iekšā pirmais ārā“. Dažādām valodām ir dažādas ieviešanas, lai gan kopumā rezultāts ir vienāds. Rinda ir ļoti līdzīga kaudzītei; tomēr ievadīšanas secība ir atšķirīga, dodot priekšroku politikai “pirmais iekšā, pirmais ārā”.

Šajā raksta daļā jūs uzzināsiet par dažām raksturīgajām atšķirībām gan kaudzēs, gan rindās dažādās programmēšanas valodās.

Stacks / Kaudzes

Kā jau raksta sākumā noskaidrojām Stacks ir abstrakta datu tipa piemērs. Datorzinātnēs tas nozīmē, ka ir daži ļoti svarīgi raksturlielumi, kas ir jāievēro, to ieviešot, taču nav reālu iebūvētu versiju, ko varētu vienkārši importēt. Stackiem svarīgs princips ir LIFO jeb pēdējais iekšā-pirmais ārā. Analoģija ar stackiem var būt šķīvju kaudzes vizualizācija uz. Mazgājot katru nākamo šķīvi, tas tiek novietots uz iepriekšējā. To žāvēšanai katrs šķīvis jāņem sākot no augšas. Tātad pirmais tiek žāvēts pēdējais kaudzītē pievienotais, bet pirmais šķīvis kaudzītē tiek žāvēts pēdējais. Parasti stacks tiek izmantoti pārlūkprogrammas vēstures saglabāšanai. Katru reizi, kad nospiežat atpakaļ, iepriekš apmeklētā lapa tiek ielādēta un, ejot uz priekšu, nolasa to kaudzē.

Izplatīta stack ieviešana JavaScript programmā ir, izmantojot masīvu un pārliecinoties, ka tas darbojas tikai tā, kā darbotos stack. Tiek uzskatīts, ka, ņemot datu struktūru un izmantojot to cita veida datu struktūras izveidošanai, tiek izmantots konteinera adapteris. Tātad šeit masīvs ir konteiners, un adaptācija liek tam rīkoties tā, kā vajadzētu. Svarīgas stack funkcijas ir push, pop, peek un count. Push pievieno vienumu kaudzes augšpusē. Masīva izmantošana nozīmē, ka skaitīšanai vienmēr ir jāzina, kur masīvā aizgāja pēdējais vienums. Tāpat pop metodei ir svarīgi noteikt masīvu skaitu, jo pop atgriež tikai pēdējo kaudzē ievadīto vienumu.

Queues / Rindas

Rinda, tāpat ,kā kaudze, ir lineāra datu struktūra, kas saglabā lietu ievadīšanas secību. Ja runā par lineāru struktūru, tas nozīmē, ka vienumi tiek glabāti tādā secībā, kādā tie tika pievienoti. Tāpat kā kaudze, arī rindā ir stingri noteikts, kā tiek pievienoti un noņemti vienumi. Kamēr stack īsteno LIFO pieeju, rindas darbojas ar FIFO pieeju. Tātad pirmais vienums, kas tiek pievienots rindai, būs pirmais vienums, kas tiks noņemts. Tāpat kā klients, kas stāv rindā, lai veiktu pirkumu, rindas izskatās, lai īstenotu politiku, kurā svarīgs ir ierašanās laiks. Tam ir dažas reālās priekšrocības, ieviešot tādas lietas kā CPU un diska plānošana, kur ir svarīgi veikt uzdevumus, tiklīdz tie tiek sasniegti.

Rinda arī ir ir abstrakts datu tips Swift, kas nozīmē, ka, lai izmantotu rindas funkcionalitāti, vispirms ir jāiekodē struktūra, kas darbosies šādā veidā. Divi svarīgi termini, kas saistīti ar rindām, ir iekļauti rindā enqueued (lai rindai pievienotu vienumu) un dequeue (lai noņemtu vienumu no saraksta aizmugures). Vienkāršākā pieeja rindas izveidošanai ir izmantot masīvu kā konteinera adapteri. Tā kā rindā tiek parādīti elementi tikai no rindas priekšpuses, meklēšanas laiks vienmēr būs O(1), tāpēc jebkura lietojumprogramma, kas izveidota, izmantojot šo pieeju, var sagaidīt ļoti ātru apkalpošanu. Tāpat kā stacks gadījumā, rindai pieejamās metodes tiek saglabātas minimālas, un vissvarīgākās ir maksimums, pop, push un lielums.

Python ievieš vairākas rindu klases, kas visas ir sinhronizētas. Sinhronizācija ir datorzinātnes koncepcija, kas nozīmē, ka visa pieeja tur atrastajiem datiem tiek pārvaldīta tā, lai datu struktūrai vienlaikus varētu piekļūt tikai viens process. Tas ir svarīgi, ja domājat par mākoņdatošanu un daudziem dažādiem avotiem, kas mēģina vienlaikus meklēt un mainīt datus. Papildus FIFO un LIFO Python rindas ieviešana ietver prioritāro rindu. Prioritārā rinda, kā norāda nosaukums, ir saistīta ar svarīguma piešķiršanu rindā atrastajiem elementiem. Tātad, nevis rindas kārtībā, bet pakalpojumu pamatā ir nozīme. Tas nedaudz atgādina VIP līniju koncertā.

Nobeiguma secinājums

Atbilstošajam uzdevumam atbilstošas datu struktūras izvēle ir ļoti svarīgs programmēšanas lēmums, jo tas var ietekmēt visu projektu. Jūs varētu atlasīt kaudzīti, ja ir nepieciešams sekot līdzi preču ievadīšanas secībai un tās atgriezt ļoti specifiskā veidā. Rinda tiek izmantota, lai uzturētu kārtību, taču tā ievēros citus noteikumus nekā kaudze. Visbeidzot, ja vēlaties datu struktūru, kurā varat piešķirt svarīgumu, ir vērts apskatīt prioritāro rindu.