Panaši į eilę yra linijinė duomenų struktūra, kuri atitinka tam tikrą duomenų saugojimo operacijų atlikimo tvarką. Užsakymas yra pirmas pirmas (FIFO) . Eilę galima įsivaizduoti kaip eilę žmonių, laukiančių, kol ką nors gaus eilės tvarka, kuri prasideda nuo eilutės pradžios. Tai sutvarkytas sąrašas, kurio viename gale įterpiama, žinoma kaip užpakalinė dalis, o išbraukiama iš kito galo, vadinamo priekine. Geras eilės pavyzdys yra bet kokia vartotojų eilė prie išteklių, kur pirmas aptarnaujamas vartotojas, kuris buvo pirmasis.
Skirtumas tarp krūvų ir eilių yra pašalinimas. Į krūvą pašaliname paskutinį kartą pridėtą elementą; eilėje pašaliname mažiausiai neseniai pridėtą elementą.
Eilių duomenų struktūra
Pagrindinės operacijos eilėje:
- enqueue(): įterpia elementą eilės gale, ty gale. dequeue(): Ši operacija pašalina ir grąžina elementą, esantį eilės priekyje. front (): Ši operacija grąžina elementą priekiniame gale jo nepašalinant. rear(): Ši operacija grąžina elementą galinėje dalyje jo nepašalinant. isEmpty(): Ši operacija nurodo, ar eilė tuščia, ar ne. isFull(): Ši operacija parodo, ar eilė pilna, ar ne. size(): Ši operacija grąžina eilės dydį, t. y. bendrą joje esančių elementų skaičių.
Eilių tipai:
- Paprasta eilė: paprasta eilė, dar žinoma kaip linijinė eilė, yra pati paprasčiausia eilės versija. Čia elementas, ty eilės operacija, įterpiamas galinėje dalyje, o elemento pašalinimas, t. y. pašalinimo operacija atliekama priekiniame gale. Problema ta, kad jei kurį nors elementą iš priekio, o paskui iš galo pasiekiame iki eilės talpos ir nors priešais priekyje yra tuščių tarpų, tai reiškia, kad eilė nėra pilna, bet pagal funkcijos isFull() sąlygą, tai parodys, kad tada eilė pilna. Norėdami išspręsti šią problemą, naudojame apskritą eilę.
- Žiedinė eilė : Apvalioje eilėje eilės elementas veikia kaip apskritas žiedas. Apskritos eilės veikimas yra panašus į linijinę eilę, išskyrus tai, kad paskutinis elementas yra prijungtas prie pirmojo elemento. Jo pranašumas yra tas, kad atmintis išnaudojama geriau. Taip yra todėl, kad jei yra tuščia vieta, t. y. jei tam tikroje eilės vietoje nėra elemento, elementą toje vietoje galima lengvai pridėti naudojant modulo pajėgumą ( %n ).
- Prioritetinė eilė : Ši eilė yra specialus eilės tipas. Jo ypatumas yra tas, kad jis sutvarko elementus į eilę pagal tam tikrą prioritetą. Prioritetas gali būti toks, kai didžiausią vertę turintis elementas turi prioritetą, todėl sukuriama eilė su mažėjančia reikšmių tvarka. Prioritetas taip pat gali būti toks, kad mažiausią reikšmę turinčiam elementui būtų suteiktas didžiausias prioritetas, todėl jis savo ruožtu sukuria eilę su didėjančia reikšmių tvarka. Iš anksto nustatytoje prioriteto eilėje C++ pirmenybę teikia didžiausiai reikšmei, o Java – mažiausia.
- Atitinkamai : Dequeue taip pat žinomas kaip Double Ended Queue. Kaip rodo pavadinimas, dvigubas galas, tai reiškia, kad elementą galima įterpti arba pašalinti iš abiejų eilės galų, skirtingai nei kitose eilėse, kuriose tai galima padaryti tik iš vieno galo. Dėl šios savybės jis gali nepaklusti pirmajam pirmam išeinant.
Eilės programos:
Eilė naudojama tada, kai dalykų nereikia apdoroti iš karto, bet juos reikia apdoroti F irst aš n F irst O ut užsisakyti patinka Pirmoji paieška . Dėl šios eilės ypatybės ji taip pat naudinga įvairiuose scenarijuose.
- Kai išteklius dalijasi keli vartotojai. Pavyzdžiui, procesoriaus planavimas, disko planavimas. Kai duomenys perduodami asinchroniškai (duomenys nebūtinai gaunami tokiu pačiu greičiu kaip ir siunčiami) tarp dviejų procesų. Pavyzdžiai: IO buferiai, vamzdžiai, failas IO ir kt. Eilė gali būti naudojama kaip esminis įvairių kitų duomenų struktūrų komponentas.
Eilės masyvo įgyvendinimas:
Norėdami įdiegti eilę, turime sekti du indeksus – priekinį ir galinį. Prekės eilę statome gale, o prekę – iš priekio. Jei tiesiog padidinsime priekinius ir galinius indeksus, gali kilti problemų, priekis gali pasiekti masyvo galą. Šios problemos sprendimas yra padidinti priekinę ir galinę dalį apskritimu.
Eilės žingsniai:
- Patikrinkite, ar eilė pilna, ar ne
- Jei pilna, spausdinkite perpildymą ir išeikite
- Jei eilė nepilna, padidinkite uodegą ir pridėkite elementą
Nutraukimo eilės žingsniai:
- Patikrinkite, ar eilė tuščia, ar ne
- jei tuščia, išspausdinkite apatinį srautą ir išeikite
- jei ne tuščias, spausdinkite elementą ant galvos ir padidinkite galvutę
Žemiau yra programa, skirta atlikti aukščiau nurodytą operaciją eilėje
C++
// CPP program for array> // implementation of queue> #include> using> namespace> std;> // A structure to represent a queue> class> Queue {> public>:> >int> front, rear, size;> >unsigned capacity;> >int>* array;> };> // function to create a queue> // of given capacity.> // It initializes size of queue as 0> Queue* createQueue(unsigned capacity)> {> >Queue* queue =>new> Queue();> >queue->talpa = talpa;> >queue->priekis = eilė->dydis = 0;> >// This is important, see the enqueue> >queue->galinis = talpa - 1;> >queue->masyvas =>new> int>[queue->talpa];> >return> queue;> }> // Queue is full when size> // becomes equal to the capacity> int> isFull(Queue* queue)> {> >return> (queue->dydis == eilė->pajėgumas);> }> // Queue is empty when size is 0> int> isEmpty(Queue* queue)> {> >return> (queue->dydis == 0);> }> // Function to add an item to the queue.> // It changes rear and size> void> enqueue(Queue* queue,>int> item)> {> >if> (isFull(queue))> >return>;> >queue->galinis = (eilė->galas + 1)> >% queue->talpa;> >queue->masyvas[eilė->galinis] = elementas;> >queue->dydis = eilė->dydis + 1;> >cout << item <<>' enqueued to queue
'>;> }> // Function to remove an item from queue.> // It changes front and size> int> dequeue(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >int> item = queue->masyvas[eilė->priekis];> >queue->priekis = (eilė->priekis + 1)> >% queue->talpa;> >queue->dydis = eilė->dydis - 1;> >return> item;> }> // Function to get front of queue> int> front(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->masyvas[eilė->priekis];> }> // Function to get rear of queue> int> rear(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->masyvas[eilė->galinis];> }> // Driver code> int> main()> {> >Queue* queue = createQueue(1000);> >enqueue(queue, 10);> >enqueue(queue, 20);> >enqueue(queue, 30);> >enqueue(queue, 40);> >cout << dequeue(queue)> ><<>' dequeued from queue
'>;> >cout <<>'Front item is '> ><< front(queue) << endl;> >cout <<>'Rear item is '> ><< rear(queue) << endl;> >return> 0;> }> // This code is contributed by rathbhupendra> |
>
>
C
java daryti kol
// C program for array implementation of queue> #include> #include> #include> // A structure to represent a queue> struct> Queue {> >int> front, rear, size;> >unsigned capacity;> >int>* array;> };> // function to create a queue> // of given capacity.> // It initializes size of queue as 0> struct> Queue* createQueue(unsigned capacity)> {> >struct> Queue* queue = (>struct> Queue*)>malloc>(> >sizeof>(>struct> Queue));> >queue->talpa = talpa;> >queue->priekis = eilė->dydis = 0;> >// This is important, see the enqueue> >queue->galinis = talpa - 1;> >queue->masyvas = (>int>*)>malloc>(> >queue->talpa *>>>int>));> >return> queue;> }> // Queue is full when size becomes> // equal to the capacity> int> isFull(>struct> Queue* queue)> {> >return> (queue->dydis == eilė->pajėgumas);> }> // Queue is empty when size is 0> int> isEmpty(>struct> Queue* queue)> {> >return> (queue->dydis == 0);> }> // Function to add an item to the queue.> // It changes rear and size> void> enqueue(>struct> Queue* queue,>int> item)> {> >if> (isFull(queue))> >return>;> >queue->galinis = (eilė->galas + 1)> >% queue->talpa;> >queue->masyvas[eilė->galinis] = elementas;> >queue->dydis = eilė->dydis + 1;> >printf>(>'%d enqueued to queue
'>, item);> }> // Function to remove an item from queue.> // It changes front and size> int> dequeue(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >int> item = queue->masyvas[eilė->priekis];> >queue->priekis = (eilė->priekis + 1)> >% queue->talpa;> >queue->dydis = eilė->dydis - 1;> >return> item;> }> // Function to get front of queue> int> front(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->masyvas[eilė->priekis];> }> // Function to get rear of queue> int> rear(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->masyvas[eilė->galinis];> }> // Driver program to test above functions./> int> main()> {> >struct> Queue* queue = createQueue(1000);> >enqueue(queue, 10);> >enqueue(queue, 20);> >enqueue(queue, 30);> >enqueue(queue, 40);> >printf>(>'%d dequeued from queue
'>,> >dequeue(queue));> >printf>(>'Front item is %d
'>, front(queue));> >printf>(>'Rear item is %d
'>, rear(queue));> >return> 0;> }> |
>
>
Java
// Java program for array> // implementation of queue> // A class to represent a queue> class> Queue {> >int> front, rear, size;> >int> capacity;> >int> array[];> >public> Queue(>int> capacity)> >{> >this>.capacity = capacity;> >front =>this>.size =>0>;> >rear = capacity ->1>;> >array =>new> int>[>this>.capacity];> >}> >// Queue is full when size becomes> >// equal to the capacity> >boolean> isFull(Queue queue)> >{> >return> (queue.size == queue.capacity);> >}> >// Queue is empty when size is 0> >boolean> isEmpty(Queue queue)> >{> >return> (queue.size ==>0>);> >}> >// Method to add an item to the queue.> >// It changes rear and size> >void> enqueue(>int> item)> >{> >if> (isFull(>this>))> >return>;> >this>.rear = (>this>.rear +>1>)> >%>this>.capacity;> >this>.array[>this>.rear] = item;> >this>.size =>this>.size +>1>;> >System.out.println(item> >+>' enqueued to queue'>);> >}> >// Method to remove an item from queue.> >// It changes front and size> >int> dequeue()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >int> item =>this>.array[>this>.front];> >this>.front = (>this>.front +>1>)> >%>this>.capacity;> >this>.size =>this>.size ->1>;> >return> item;> >}> >// Method to get front of queue> >int> front()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >return> this>.array[>this>.front];> >}> >// Method to get rear of queue> >int> rear()> >{> >if> (isEmpty(>this>))> >return> Integer.MIN_VALUE;> >return> this>.array[>this>.rear];> >}> }> // Driver class> public> class> Test {> >public> static> void> main(String[] args)> >{> >Queue queue =>new> Queue(>1000>);> >queue.enqueue(>10>);> >queue.enqueue(>20>);> >queue.enqueue(>30>);> >queue.enqueue(>40>);> >System.out.println(queue.dequeue()> >+>' dequeued from queue
'>);> >System.out.println(>'Front item is '> >+ queue.front());> >System.out.println(>'Rear item is '> >+ queue.rear());> >}> }> // This code is contributed by Gaurav Miglani> |
>
>
Python3
# Python3 program for array implementation of queue> # Class Queue to represent a queue> class> Queue:> ># __init__ function> >def> __init__(>self>, capacity):> >self>.front>=> self>.size>=> 0> >self>.rear>=> capacity>->1> >self>.Q>=> [>None>]>*>capacity> >self>.capacity>=> capacity> > ># Queue is full when size becomes> ># equal to the capacity> >def> isFull(>self>):> >return> self>.size>=>=> self>.capacity> > ># Queue is empty when size is 0> >def> isEmpty(>self>):> >return> self>.size>=>=> 0> ># Function to add an item to the queue.> ># It changes rear and size> >def> EnQueue(>self>, item):> >if> self>.isFull():> >print>(>'Full'>)> >return> >self>.rear>=> (>self>.rear>+> 1>)>%> (>self>.capacity)> >self>.Q[>self>.rear]>=> item> >self>.size>=> self>.size>+> 1> >print>(>'% s enqueued to queue'> %> str>(item))> ># Function to remove an item from queue.> ># It changes front and size> >def> DeQueue(>self>):> >if> self>.isEmpty():> >print>(>'Empty'>)> >return> > >print>(>'% s dequeued from queue'> %> str>(>self>.Q[>self>.front]))> >self>.front>=> (>self>.front>+> 1>)>%> (>self>.capacity)> >self>.size>=> self>.size>->1> > ># Function to get front of queue> >def> que_front(>self>):> >if> self>.isEmpty():> >print>(>'Queue is empty'>)> >print>(>'Front item is'>,>self>.Q[>self>.front])> > ># Function to get rear of queue> >def> que_rear(>self>):> >if> self>.isEmpty():> >print>(>'Queue is empty'>)> >print>(>'Rear item is'>,>self>.Q[>self>.rear])> # Driver Code> if> __name__>=>=> '__main__'>:> >queue>=> Queue(>30>)> >queue.EnQueue(>10>)> >queue.EnQueue(>20>)> >queue.EnQueue(>30>)> >queue.EnQueue(>40>)> >queue.DeQueue()> >queue.que_front()> >queue.que_rear()> |
>
>
C#
// C# program for array implementation of queue> using> System;> namespace> GeeksForGeeks {> // A class to represent a linearqueue> class> Queue {> >private> int>[] ele;> >private> int> front;> >private> int> rear;> >private> int> max;> >public> Queue(>int> size)> >{> >ele =>new> int>[size];> >front = 0;> >rear = -1;> >max = size;> >}> >// Function to add an item to the queue.> >// It changes rear and size> >public> void> enqueue(>int> item)> >{> >if> (rear == max - 1) {> >Console.WriteLine(>'Queue Overflow'>);> >return>;> >}> >else> {> >ele[++rear] = item;> >}> >}> >// Function to remove an item from queue.> >// It changes front and size> >public> int> dequeue()> >{> >if> (front == rear + 1) {> >Console.WriteLine(>'Queue is Empty'>);> >return> -1;> >}> >else> {> >Console.WriteLine(ele[front] +>' dequeued from queue'>);> >int> p = ele[front++];> >Console.WriteLine();> >Console.WriteLine(>'Front item is {0}'>, ele[front]);> >Console.WriteLine(>'Rear item is {0} '>, ele[rear]);> >return> p;> >}> >}> >// Function to print queue.> >public> void> printQueue()> >{> >if> (front == rear + 1) {> >Console.WriteLine(>'Queue is Empty'>);> >return>;> >}> >else> {> >for> (>int> i = front; i <= rear; i++) {> >Console.WriteLine(ele[i] +>' enqueued to queue'>);> >}> >}> >}> }> // Driver code> class> Program {> >static> void> Main()> >{> >Queue Q =>new> Queue(5);> >Q.enqueue(10);> >Q.enqueue(20);> >Q.enqueue(30);> >Q.enqueue(40);> >Q.printQueue();> >Q.dequeue();> >}> }> }> |
>
>
Javascript
> // Queue class> class Queue> {> >// Array is used to implement a Queue> >constructor()> >{> >this>.items = [];> >}> >isEmpty()> >{> >// return true if the queue is empty.> >return> this>.items.length == 0;> >}> >enqueue(element)> >{> >// adding element to the queue> >this>.items.push(element);> >document.write(element +>' enqueued to queue '>);> >}> >dequeue()> >{> >// removing element from the queue> >// returns underflow when called> >// on empty queue> >if>(>this>.isEmpty())> >return> 'Underflow '>;> >return> this>.items.shift();> >}> >front()> >{> >// returns the Front element of> >// the queue without removing it.> >if>(>this>.isEmpty())> >return> 'No elements in Queue '>;> >return> this>.items[0];> >}> >rear()> >{> >// returns the Rear element of> >// the queue without removing it.> >if>(>this>.isEmpty())> >return> 'No elements in Queue '>;> >return> this>.items[>this>.items.length-1];> >}> }> // creating object for queue class> var> queue =>new> Queue();> // Adding elements to the queue> queue.enqueue(10);> queue.enqueue(20);> queue.enqueue(30);> queue.enqueue(40);> // queue contains [10, 20, 30, 40]> // removes 10> document.write(queue.dequeue() +>' dequeued from queue '>);> // queue contains [20, 30, 40]> // Front is now 20> document.write(>'Front item is '> + queue.front() +>' '>);> // printing the rear element> // Rear is 40> document.write(>'Rear item is '> + queue.rear() +>' '>);> // This code is contributed by Susobhan Akhuli> > |
>
>Išvestis
10 enqueued to queue 20 enqueued to queue 30 enqueued to queue 40 enqueued to queue 10 dequeued from queue Front item is 20 Rear item is 40>
Sudėtingumo analizė:
- Laiko sudėtingumas
| Operacijos | Sudėtingumas |
|---|---|
| Eilė (įterpimas) | O(1) |
| Deque (ištrynimas) | O(1) |
| Priekyje (Eikite į priekį) | O(1) |
| Užpakalinė dalis (Atsidėkite atgal) | O(1) |
| IsFull (Patikrinti, ar eilė pilna, ar ne) | O(1) |
| IsEmpty (tikrinimo eilė tuščia ar ne) | O(1) |
- Pagalbinė erdvė:
O(N), kur N yra elementų saugojimo masyvo dydis.
Masyvo diegimo privalumai:
- Lengva įgyvendinti.
- Didelis duomenų kiekis gali būti lengvai valdomas efektyviai.
- Tokios operacijos kaip įterpimas ir ištrynimas gali būti atliekamos nesunkiai, nes tai daroma pagal taisyklę „pirmas pirmas“.
Masyvo diegimo trūkumai:
- Statinė duomenų struktūra, fiksuotas dydis.
- Jei eilėje yra daug eilės ir ištraukimo eilės operacijų, tam tikru momentu (esant tiesiniam priekinių ir galinių indeksų prieaugiui) gali nepavykti įterpti elementų į eilę, net jei eilė tuščia (šios problemos išvengiama naudojant žiedinę eilę).
- Didžiausias eilės dydis turi būti nustatytas iš anksto.