Informatikos moksle eilė yra linijinė duomenų struktūra, kai komponentai dedami į vieną galą ir pašalinami iš kito galo pagal FIFO principą. Ši duomenų struktūra gali būti naudojama veiksmų sekai valdyti arba duomenims saugoti. C yra kompiuterinė kalba su eilės galimybe, įtraukta į masyvus arba susietus sąrašus.
Charakteristikos:
- Eilė yra linijinės duomenų struktūros tipas, kurį galima sudaryti naudojant masyvą arba susietą sąrašą.
- Elementai perkeliami į eilės galą, o pašalinami iš priekio.
- Eilė (pridėkite elementą į galą) ir dequeue (pašalinkite elementą iš priekio) yra dvi eilės operacijos.
- Kai elementai dažnai pridedami ir pašalinami, eilė gali būti sudaryta kaip apskrita eilė, kad būtų išvengta atminties švaistymo.
Naudojant masyvą:
Norėdami įdiegti eilę C naudojant masyvą, pirmiausia nustatykite maksimalų eilės dydį ir deklaruokite tokio dydžio masyvą. Priekiniai ir galiniai sveikieji skaičiai buvo atitinkamai nustatyti į 1. Priekinis kintamasis reiškia priekinį eilės elementą, o užpakalinis kintamasis – užpakalinį elementą.
Prieš stumdami naują elementą į galutinę eilės padėtį, turime padidinti kintamąjį atgal 1. Eilė dabar pilna ir negalima pridėti kitų papildomų elementų, kai galinė padėtis pasiekia didžiausią eilės talpą. Pridedame elementą prie eilės priekio ir priekinį kintamąjį padidiname tik vienu, kad pašalintume elementą iš eilės. Jei priekinė ir galinė padėtis yra vienodos ir daugiau komponentų negalima ištrinti, galime sakyti, kad eilė tuščia.
global var in js
Toliau pateikiamas eilės pavyzdys, parašytas C, kuriame naudojamas masyvas:
C programavimo kalba:
#define MAX_SIZE 100 int queue[MAX_SIZE]; int front = -1; int rear = -1; void enqueue(int element) { if (rear == MAX_SIZE - 1) { printf('Queue is full'); return; } if (front == -1) { front = 0; } rear++; queue[rear] = element; } int dequeue() { if (front == -1 || front > rear) { printf('Queue is empty'); return -1; } int element = queue[front]; front++; return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } Kodo išvestis bus tokia:
Išvestis:
romėniškas skaitmuo nuo 1 iki 100
10 20 30 Queue is empty-1
Paaiškinimas:
- Pirmiausia į eilę įtraukiame tris elementus 10, 20 ir 30.
- Tada ištraukiame eilę ir išspausdiname priekinį eilės elementą, kuris yra 10.
- Tada ištraukiame eilę ir vėl išspausdiname priekinį eilės elementą, kuris yra 20.
- Tada ištraukiame eilę ir vėl išspausdiname priekinį eilės elementą, kuris yra 30.
- Galiausiai sukuriame iš tuščios eilės, kuri išveda „Eilė tuščia“ ir grąžina -1.
Susieto sąrašo naudojimas:
Kitas alternatyvus būdas sukurti eilę programavimo kalba C yra susieto sąrašo naudojimas. Kiekvienas eilės mazgas šiuo metodu išreiškiamas mazgu, kuriame yra elemento reikšmė ir rodyklė į kitą eilės mazgą. Norint sekti pirmąjį ir paskutinįjį eilės mazgus, atitinkamai naudojami priekiniai ir galiniai rodyklės.
Mes sukuriame naują mazgą su elemento reikšme ir nustatome kitą jo žymeklį į NULL, kad įtrauktume elementą į eilę. Į naują mazgą nustatome priekines ir galines rodykles, jei eilė tuščia. Jei ne, atnaujiname galinį žymeklį ir nustatome kitą senojo galinio mazgo žymeklį, kad jis nukreiptų į naują mazgą.
Ištrinant mazgą iš eilės, pirmiausia ištrinamas ankstesnis mazgas, tada priekinis rodyklė atnaujinama į kitą eilės mazgą ir galiausiai atlaisvinama atmintis, kurią užėmė pašalintas mazgas. Jei po pašalinimo priekinis žymeklis yra NULL, eilė tuščia.
for loop in shell scenarijus
Štai eilės, įdiegtos C, naudojant susietą sąrašą, pavyzdys:
C programavimo kalba:
#include #include struct Node { int data; struct Node* next; }; struct Node* front = NULL; struct Node* rear = NULL; void enqueue(int element) { struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = element; new_node->next = NULL; if (front == NULL && rear == NULL) { front = rear = new_node; return; } rear->next = new_node; rear = new_node; } int dequeue() { if (front == NULL) { printf('Queue is empty'); return -1; } struct Node* temp = front; int element = temp->data; if (front == rear) { front = rear = NULL; } else { front = front->next; } free(temp); return element; } int main() { enqueue(10); enqueue(20); enqueue(30); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); printf('%d ', dequeue()); return 0; } Kodo išvestis bus tokia:
Išvestis:
10 20 30 Queue is empty-1
Paaiškinimas:
- Pirmiausia į eilę įtraukiame tris elementus 10, 20 ir 30.
- Tada ištraukiame eilę ir išspausdiname priekinį eilės elementą, kuris yra 10.
- Tada ištraukiame eilę ir vėl išspausdiname priekinį eilės elementą, kuris yra 20.
- Tada ištraukiame eilę ir vėl išspausdiname priekinį eilės elementą, kuris yra 30.
- Galiausiai bandome ištraukti iš tuščios eilės, kuri išspausdina pranešimą „Eilė tuščia“ ir grąžina -1.
Privalumai:
- Eilės ypač naudingos diegiant algoritmus, kurių elementus reikia apdoroti tikslia seka, pvz., paiešką pagal plotį ir užduočių planavimą.
- Kadangi eilės operacijos turi O(1) laiko sudėtingumą, jas galima greitai atlikti net esant didžiulėms eilėms.
- Eilės yra ypač lanksčios, nes jas galima tiesiog įdiegti naudojant masyvą arba susietą sąrašą.
Trūkumai:
- Eilė, skirtingai nei krūva, negali būti sudaryta naudojant vieną žymeklį, todėl eilės įgyvendinimas yra šiek tiek labiau įtrauktas.
- Jei eilė sudaryta kaip masyvas, ji gali greitai užsipildyti, jei bus pridėta per daug elementų, todėl gali kilti problemų dėl našumo arba gali kilti gedimas.
- Kai eilei įgyvendinti naudojamas susietas sąrašas, kiekvieno mazgo atminties viršija gali būti didelė, ypač mažų elementų atveju.
Išvada:
Programos, kurios naudoja eiles, svarbią duomenų struktūrą, apima operacines sistemas, tinklus ir žaidimus, kad būtų galima paminėti tik keletą. Jie idealiai tinka algoritmams, kurie turi tvarkyti elementus tam tikra tvarka, nes juos paprasta sukurti naudojant masyvą arba susietą sąrašą. Tačiau eilės turi trūkumų, į kuriuos reikia atsižvelgti renkantis duomenų struktūrą konkrečiai programai, pvz., atminties suvartojimą ir diegimo sudėtingumą.