Rekomenduojama, 2024

Redaktoriaus Pasirinkimas

Skirtumas tarp linijinės eilės ir apskrito eilės

Paprasta linijinė eilė gali būti įgyvendinama įvairiais trimis būdais, tarp kurių vienas iš tipų yra apvali eilė. Skirtumas tarp linijinės ir apvalios eilės yra struktūriniai ir našumo veiksniai. Esminis skirtumas tarp linijinės eilės ir apvalios eilės yra tai, kad tiesinė eilė sunaudoja daugiau vietos nei apvali eilė, o apvali eilė buvo sukurta riboti linijinės eilės atminties švaistymą.

Eilė gali būti apibūdinama kaip ne primityvi linijinė duomenų struktūra, atitinkanti FIFO tvarką, kurioje duomenų elementai yra įterpiami iš vieno galo (galinės dalies) ir ištrinami iš kito galo (priekinis galas). Kitos eilės variantai yra apvali eilė, dvigubai baigta eilė ir prioritetinė eilė.

Palyginimo diagrama

Palyginimo pagrindasLinijinė eilėApvali eilė
PagrindinisTvarko duomenų elementus ir instrukcijas viena po kitos.Duomenis išdėsto apskrito modelio, kuriame paskutinis elementas yra prijungtas prie pirmojo elemento.
Užduočių vykdymo tvarka
Užduotys vykdomos, kad jos būtų išdėstytos anksčiau (FIFO).Užduoties vykdymo tvarka gali pasikeisti.
Įterpimas ir ištrynimas
Naujas elementas pridedamas iš galinės dalies ir nuimamas iš priekio.Įterpimas ir ištrynimas gali būti atliekami bet kurioje padėtyje.
Spektaklis
Neefektyvus
Veikia geriau nei linijinė eilė.

Linijinės eilės apibrėžimas

Linijinė eilė yra racionaliai pirmasis iš pirmojo užsakyto sąrašo. Tai vadinama linijine, nes ji panaši į tiesią liniją, kurioje elementai yra vienas po kito. Jame yra vienodas elementų rinkinys, kuriame viename gale pridedami nauji elementai ir ištrinami iš kito galo. Eilutės koncepcija gali būti suprantama pagal pavyzdį, kai žiūrovų laukia ne bilietų skaitiklis, kad gautų teatro bilietą. Šioje eilutėje asmuo prisijungia prie užpakalinio eilės galo, kad pasiektų bilietą, o bilietas išduodamas eilės priekyje.

Eilėje atliekamos kelios operacijos

  • Pirma, eilė inicijuojama į nulį (ty tuščia).
  • Nustatykite, ar eilė yra tuščia, ar ne.
  • Nustatykite, ar eilė yra pilna, ar ne.
  • Naujo elemento įdėjimas iš galinės dalies („Enqueue“).
  • Elemento ištrynimas iš priekio (Dequeue).

Eilė gali būti įgyvendinama dviem būdais

  • Statiškai (masyvų naudojimas)
  • Dinamiškai (rodyklių naudojimas)

Linijinės eilės apribojimas yra tai, kad jis sukuria scenarijų, kuriame eilėje negali būti pridėta jokio naujo elemento, net jei eilėje yra tuščios vietos. Ši situacija yra parodyta toliau pateiktame paveiksle. Čia galinė dalis nukreipta į paskutinį indeksą, o visos dėžutės vis dar tuščios, naujų elementų negalima pridėti.

Apskritojo eilės apibrėžimas

Apvali eilė yra tiesinės eilės variantas, kuris veiksmingai įveikia tiesinės eilės ribojimą. Apskritojo eilėje nauja elementas pridedamas pačioje pirmoje eilės padėtyje, jei paskutinis užimtas ir erdvė yra prieinama. Kai kalbama apie linijinę eilę, įterpimas gali būti atliekamas tik iš galinės dalies ir išbraukimo iš priekio. Visoje eilėje, atlikus eilę eilės ištrynimų eilėje, atsiranda tam tikra situacija, kai naujas elementas negali būti papildomas, net jei laisvos vietos, nes vis dar egzistuoja nepakankamas srautas (galinis = max - 1).

Apvali eilė sujungia abu galus per žymiklį, kur pirmasis elementas yra po paskutinio elemento. Ji taip pat stebi priekinę ir galinę dalį, įgyvendindama papildomą logiką, kad galėtų atsekti elementus, kuriuos reikia įterpti ir ištrinti. Tokiu būdu apvali eilė nesukuria perpildymo būklės tol, kol eilė nebus užpildyta.

Kai kurios sąlygos, po kurių seka apvali eilė:

  • Priekyje turi būti nurodomas pirmasis elementas.
  • Eilutė bus tuščia, jei priekinė pusė - galinė.
  • Pridėjus naują elementą, eilė padidinama viena reikšme (gale = gale + 1).
  • Kai elementas ištrinamas iš eilės, priekis padidinamas vienu (priekyje = priekyje + 1).

Pagrindiniai skirtumai tarp linijinės eilės ir apskrito eilės

  1. Linijinė eilė yra užsakytas sąrašas, kuriame duomenų elementai yra išdėstyti eilės tvarka. Priešingai, apvali eilė saugo duomenis apskritai.
  2. Linijinė eilė vykdoma pagal FIFO užsakymą (pirmos pozicijos elementas bus ištrintas pirmoje pozicijoje). Ir atvirkščiai, apskrito eilėje eilės tvarka, kurią atlieka elementas, gali pasikeisti.
  3. Elementų įdėjimas ir ištrynimas yra fiksuotas linijinėje eilėje, ty papildymas iš galinės dalies ir išbraukimas iš priekio. Kita vertus, apskritoji eilė gali įterpti ir ištrinti elementą iš bet kurio taško, kol ji nėra užimta.
  4. Linijinė eilė eikvoja atminties erdvę, o apvali eilė daro efektyvų erdvės naudojimą.

Linijinės eilės įgyvendinimas

Toliau pateiktas algoritmas iliustruoja elementų įtraukimą į eilę:
Eilėje reikia trijų duomenų kintamųjų, įskaitant vieną masyvą, kad būtų galima išsaugoti eilę, o kitą - saugoti priekinę ir galinę pradinę padėtį, kuri yra -1.

 įterpti (elementas, eilė, n, galinis) {jei (galinis == n) tada spausdinti „eilės perpildymą“; dar {galinis = galinis + 1; eilė [galinis] = elementas; }} 

Toliau pateiktas algoritmas iliustruoja elementų ištrynimą eilėje:

 delete_circular (elementas, eilė, galinis, priekinis) {jei (galinis == priekis), tada atspausdinkite "eilės nutekėjimą"; dar {front = front + 1; elementas = eilė [priekinė]; }} 

Apvaliosios eilės įgyvendinimas

Algoritmas, skirtas interpretuoti elemento pridėjimą apvalioje eilėje:

 Insert_circular (elementas, eilė, galinė, priekinė) {rear = (rear + 1) mod n; jei (priekyje == gale) tada spausdinti „eilė yra pilna“; other {queue [rear] = elementas; }} 

Algoritmas paaiškina elemento išbraukimą iš apvalios eilės:

 delete_circular (elementas, eilė, galinis, priekinis) {jei (priekyje == gale) tada spausdinti ("eilė tuščia"); dar {front = front + 1; elementas = eilė [priekinė]; }} 

Išvada

Linijinė eilė yra neveiksminga tam tikrais atvejais, kai elementai yra reikalingi perkelti į laisvas vietas, kad būtų galima atlikti įterpimo operaciją. Tai yra priežastis, dėl kurios ji linkusi švaistyti saugyklą, o apvali eilė tinkamai naudoja saugojimo vietą, nes elementai yra pridedami bet kurioje padėtyje, jei yra tuščia erdvė.

Top