Rindu var raksturot kā ne-primitīvu lineāru datu struktūru, kas seko FIFO secībai, kurā datu elementi tiek ievietoti no viena gala (aizmugurē) un izdzēsti no otrā gala (priekšējais gals). Pārējās rindas variācijas ir apļveida rinda, divkārši pabeigta rinda un prioritātes rinda.
Salīdzinājuma diagramma
| Salīdzināšanas pamats | Lineārā rinda | Cirkulārā rinda |
|---|---|---|
| Pamata | Organizē datu elementus un instrukcijas pēc kārtas pēc kārtas. | Sakārto datus apļveida rakstā, kur pēdējais elements ir savienots ar pirmo elementu. |
| Uzdevumu izpildes kārtība | Uzdevumi tiek izpildīti, lai tos ievietotu iepriekš (FIFO). | Uzdevuma izpildes kārtība var mainīties. |
| Ievietošana un dzēšana | Jaunais elements tiek pievienots no aizmugures un noņemts no priekšpuses. | Ievietošanu un dzēšanu var veikt jebkurā pozīcijā. |
| Veiktspēja | Neefektīva | Darbojas labāk nekā lineārā rinda. |
Linear rindas definīcija
Lineārā rinda ir racionāli pirmais pirmais ārā pasūtītajā sarakstā. Tā ir tā saukta lineāra, jo tā atgādina taisnu līniju, kur elementi atrodas viens otram. Tas satur viendabīgu to elementu kolekciju, kuros vienā galā tiek pievienoti jauni elementi un izdzēsti no cita gala. Rindas jēdzienu var saprast ar piemēru, kad skatītāju rinda gaida ārpus biļešu skaitītāja, lai iegūtu teātra biļeti. Šajā rindā persona pievienojas rindas aizmugurējai daļai, lai paņemtu biļeti, un biļete tiek izsniegta rindas priekšpusē.
Ir vairākas operācijas rindā
- Pirmkārt, rinda tiek inicializēta uz nulli (ti, tukša).
- Nosakiet, vai rinda ir tukša vai nav.
- Nosakiet, vai rinda ir pilna vai nav.
- Jaunā elementa ievietošana no aizmugures (Enqueue).
- Elementa dzēšana no priekšējā gala (Dequeue).
Rindu var īstenot divos veidos
- Statiski (masīvu izmantošana)
- Dinamiski (rādītāju izmantošana)
Lineārās rindas ierobežojums ir tāds, ka tas rada scenāriju, kurā rindā nav iespējams pievienot jaunu elementu pat tad, ja rindā ir tukšas telpas. Šī iepriekš minētā situācija ir parādīta zemāk redzamajā attēlā. Šeit aizmugure ir vērsta uz pēdējo indeksu, kamēr visas kastes ir tukšas, jaunus elementus nevar pievienot.
Apļveida rindas definīcija
Apļveida rinda ir lineārās rindas variants, kas faktiski pārvar lineārās rindas ierobežojumu. Apļveida rindā jaunais elements tiek pievienots pirmajā rindas pozīcijā, ja pēdējais ir aizņemts un vieta ir pieejama. Kad runa ir par lineāro rindu, ievietošanu var veikt tikai no aizmugures un dzēšanu no priekšpuses. Pilnā rindā pēc secīgu rindu dzēšanas rindā rodas kāda situācija, kad jaunu elementu nevar pievienot vēl pat tad, ja pieejamā vieta ir nepietiekama, jo nepietiekama plūsma (aizmugurē = max - 1) joprojām pastāv.
Apļveida rinda savieno abus galus ar rādītāju, kur pirmais elements ir pēc pēdējā elementa. Tas arī seko priekšējai un aizmugurējai daļai, ieviešot papildu loģiku, lai varētu izsekot elementiem, kas jāievieto un jāizdzēš. Ar to, apļveida rinda nerada pārpildes stāvokli, līdz rinda faktiski nav pilna.
Daži nosacījumi, kam seko apļveida rinda:
- Priekšpusē jānorāda uz pirmo elementu.
- Ja priekšpuse = aizmugurē, rinda būs tukša.
- Ja tiek pievienots jauns elements, rinda tiek palielināta par vienu vērtību (aizmugurē = aizmugurē + 1).
- Kad elements tiek izdzēsts no rindas, priekšpusi palielina par vienu (priekšā = priekšā + 1).
Galvenās atšķirības starp lineāro rindu un apļveida rindu
- Lineārā rinda ir sakārtots saraksts, kurā datu elementi ir sakārtoti secīgā secībā. Turpretī apļveida rindā dati tiek glabāti apļveida veidā.
- Lineārā rinda seko FIFO rīkojumam uzdevuma izpildei (pirmajā pozīcijā iekļautais elements tiks dzēsts pirmajā pozīcijā). Turpretī apļveida rindā var mainīties elementiem veikto darbību secība.
- Elementu ievietošana un dzēšana ir fiksēta lineārā rindā, ti, pievienošana no aizmugures un izdzēšana no priekšējā gala. No otras puses, apļveida rinda spēj ievietot un dzēst elementu no jebkura punkta, līdz tā nav aizņemta.
- Lineārā rinda tērē atmiņas vietu, bet apļveida rinda ļauj efektīvi izmantot telpu.
Lineārās rindas īstenošana
Turpmāk sniegtais algoritms ilustrē rindas elementu pievienošanu:
Līnijai ir vajadzīgi trīs datu mainīgie, tostarp viens masīvs, lai saglabātu rindu, un citi, lai saglabātu priekšējo un aizmugurējo sākotnējo pozīciju, kas ir -1.
ievietot (vienums, rinda, n, aizmugurē) {if (aizmugurē == n), tad izdrukājiet "rindas pārplūdi"; cits {aizmugurē = aizmugurē + 1; rinda [aizmugurē] = vienums; }} Turpmāk sniegtais algoritms ilustrē rindas elementu dzēšanu :
delete_circular (vienums, rinda, aizmugurē, priekšā) {if (aizmugurē == priekšā), tad izdrukājiet "rindas nepietiekamu plūsmu"; cits {front = front + 1; postenis = rinda [priekšā]; }} Apļveida rindas īstenošana
Algoritms, lai interpretētu elementa pievienošanu apļveida rindā:
insert_circular (postenis, rinda, aizmugurē, priekšā) {rear = (aizmugurē + 1) mod n; ja (priekšā == aizmugurē) tad izdrukāt "rinda ir pilna"; cits {queue [rear] = vienums; }} Algoritms izskaidro elementa dzēšanu apļveida rindā:
delete_circular (vienums, rinda, aizmugurē, priekšā) {ja (priekšā == aizmugurē), tad izdrukājiet ("rinda ir tukša"); cits {front = front + 1; postenis = rinda [priekšā]; }} Secinājums
Lineārā rinda ir neefektīva dažos gadījumos, kad elementi ir nepieciešami, lai pārietu uz brīvajām telpām, lai veiktu ievietošanas operāciju. Tas ir iemesls, kāpēc tam ir tendence izšķērdēt uzglabāšanas telpu, bet apļveida rinda nodrošina piemērotu uzglabāšanas vietu, jo elementi tiek pievienoti jebkurā vietā, ja ir tukša vieta.
