Samanlainen kuin Queue on lineaarinen tietorakenne, joka noudattaa tiettyä järjestystä, jossa toiminnot suoritetaan tietojen tallentamiseksi. Tilaus on First In First Out (FIFO) . Jonon voi kuvitella jonona ihmisiä, jotka odottavat saavansa jotain peräkkäisessä järjestyksessä, joka alkaa jonon alusta. Se on järjestetty luettelo, jossa lisäykset tehdään toiseen päähän, joka tunnetaan nimellä takaosa, ja poistot tehdään toisesta päästä, jota kutsutaan etupääksi. Hyvä esimerkki jonosta on mikä tahansa kuluttajien jono resurssille, jossa ensin palvellaan ensin tullutta kuluttajaa.
Pinojen ja jonojen välinen ero on poistamisessa. Poistamme pinosta viimeksi lisätyn kohteen; jonossa poistamme viimeksi lisätyn kohteen.
Jono Tietorakenne
Perustoiminnot jonossa:
- enqueue(): Lisää elementin jonon loppuun eli takapäähän. dequeue(): Tämä toiminto poistaa ja palauttaa elementin, joka on jonon etupäässä. front(): Tämä toiminto palauttaa etupään elementin poistamatta sitä. rear(): Tämä toiminto palauttaa elementin takapäässä poistamatta sitä. isEmpty(): Tämä toiminto ilmaisee, onko jono tyhjä vai ei. isFull(): Tämä toiminto ilmaisee, onko jono täynnä vai ei. size(): Tämä toiminto palauttaa jonon koon eli sen sisältämien elementtien kokonaismäärän.
Jonotyypit:
- Yksinkertainen jono: Yksinkertainen jono, joka tunnetaan myös nimellä lineaarinen jono, on jonon perusversio. Tässä elementin lisääminen eli Enqueue-toiminto tapahtuu takapäässä ja elementin poistaminen eli Dequeue-toiminto tapahtuu etupäässä. Tässä ongelmana on se, että jos siirrämme jonkin kohteen edestä ja sitten takaa jonon kapasiteettiin ja vaikka edessä on tyhjiä tiloja, se tarkoittaa, että jono ei ole täynnä, mutta isFull()-funktion ehdon mukaisesti, se näyttää, että jono on silloin täynnä. Tämän ongelman ratkaisemiseksi käytämme pyöreää jonoa.
- Pyöreä jono : Pyöreässä jonossa jonon elementti toimii pyöreänä renkaana. Pyöreän jonon toiminta on samanlaista kuin lineaarisen jonon, paitsi että viimeinen elementti on yhdistetty ensimmäiseen elementtiin. Sen etuna on, että muistia hyödynnetään paremmin. Tämä johtuu siitä, että jos on tyhjä tila, eli jos jonon tietyssä kohdassa ei ole elementtiä, elementti voidaan helposti lisätä kyseiseen kohtaan käyttämällä modulo-kapasiteettia ( %n ).
- Prioriteettijono : Tämä jono on erityinen jonotyyppi. Sen erikoisuus on, että se järjestää elementit jonoon jonkin prioriteetin perusteella. Prioriteetti voi olla jotain, jossa korkeimman arvon elementillä on prioriteetti, joten se luo jonon, jonka arvojärjestys on laskeva. Prioriteetti voi olla myös sellainen, että pienimmän arvon omaava elementti saa korkeimman prioriteetin, jolloin se puolestaan luo jonon, jossa arvot kasvavat. Ennalta määritetyssä prioriteettijonossa C++ antaa etusijalle suurimman arvon, kun taas Java antaa prioriteetin pienimmälle arvolle.
- Asianmukaisesti : Dequeue tunnetaan myös nimellä Double Ended Queue. Kuten nimestä voi päätellä, kaksipäätinen, se tarkoittaa, että elementti voidaan lisätä tai poistaa jonon molemmista päistä, toisin kuin muut jonot, joissa se voidaan tehdä vain toisesta päästä. Tämän ominaisuuden vuoksi se ei välttämättä noudata First In First Out -ominaisuutta.
Jonon sovellukset:
Jonoa käytetään, kun asioita ei tarvitse käsitellä heti, vaan ne on käsiteltävä sisään F ensin minä n F ensin O tilaa kuten Leveys ensimmäinen haku . Tämä jonon ominaisuus tekee siitä hyödyllisen myös seuraavissa tilanteissa.
- Kun resurssi jaetaan useiden kuluttajien kesken. Esimerkkejä ovat suorittimen ajoitus, levyjen ajoitus. Kun dataa siirretään asynkronisesti (dataa ei välttämättä vastaanoteta samalla nopeudella kuin lähetetty) kahden prosessin välillä. Esimerkkejä ovat IO-puskurit, putket, tiedosto-IO jne. Jonoa voidaan käyttää olennaisena komponenttina useissa muissa tietorakenteissa.
Jonon taulukkototeutus:
Jonon toteuttamiseksi meidän on seurattava kahta indeksiä, edessä ja takana. Asetamme tuotteen jonoon taakse ja poistamme tuotteen edestä. Jos yksinkertaisesti lisäämme etu- ja takaindeksejä, voi esiintyä ongelmia, etuosa voi saavuttaa taulukon loppuun. Ratkaisu tähän ongelmaan on lisätä etu- ja takaosaa ympyrämäisesti.
Jonon vaiheet:
- Tarkista, onko jono täynnä vai ei
- Jos täynnä, tulosta ylivuoto ja poistu
- Jos jono ei ole täynnä, lisää häntää ja lisää elementti
Vaiheet jonosta poistamiseen:
- Tarkista, onko jono tyhjä vai ei
- jos tyhjä, tulosta alivuoto ja poistu
- jos se ei ole tyhjä, tulosta elementti päähän ja lisäyspää
Alla on ohjelma yllä olevan toiminnan toteuttamiseksi jonossa
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->kapasiteetti = kapasiteetti;> >queue->edessä = jono->koko = 0;> >// This is important, see the enqueue> >queue->takana = kapasiteetti - 1;> >queue->array =>new> int>[queue->kapasiteetti];> >return> queue;> }> // Queue is full when size> // becomes equal to the capacity> int> isFull(Queue* queue)> {> >return> (queue->koko == jono->kapasiteetti);> }> // Queue is empty when size is 0> int> isEmpty(Queue* queue)> {> >return> (queue->koko == 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->taka = (jono->taka + 1)> >% queue->kapasiteetti;> >queue->array[jono->taka] = kohde;> >queue->koko = jono->koko + 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->array[jono->etu];> >queue->edessä = (jono->etu + 1)> >% queue->kapasiteetti;> >queue->koko = jono->koko - 1;> >return> item;> }> // Function to get front of queue> int> front(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[jono->etu];> }> // Function to get rear of queue> int> rear(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[jono->taka];> }> // 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 ydin java
// 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->kapasiteetti = kapasiteetti;> >queue->edessä = jono->koko = 0;> >// This is important, see the enqueue> >queue->takana = kapasiteetti - 1;> >queue->array = (>int>*)>malloc>(> >queue->kapasiteetti *>>sizeof>(>int>));> >return> queue;> }> // Queue is full when size becomes> // equal to the capacity> int> isFull(>struct> Queue* queue)> {> >return> (queue->koko == jono->kapasiteetti);> }> // Queue is empty when size is 0> int> isEmpty(>struct> Queue* queue)> {> >return> (queue->koko == 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->taka = (jono->taka + 1)> >% queue->kapasiteetti;> >queue->array[jono->taka] = kohde;> >queue->koko = jono->koko + 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->array[jono->etu];> >queue->edessä = (jono->etu + 1)> >% queue->kapasiteetti;> >queue->koko = jono->koko - 1;> >return> item;> }> // Function to get front of queue> int> front(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[jono->etu];> }> // Function to get rear of queue> int> rear(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[jono->taka];> }> // 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> |
>
>
Python 3
Linuxin tehtävänhallinta
# 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> > |
>
>Lähtö
kartta javassa
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>
Monimutkaisuusanalyysi:
- Aika monimutkaisuus
| Toiminnot | Monimutkaisuus |
|---|---|
| Jono (lisäys) | O(1) |
| Deque (poisto) | O(1) |
| Edessä (nouse eteen) | O(1) |
| Taka (Hae taakse) | O(1) |
| IsFull (tarkista, onko jono täynnä vai ei) | O(1) |
| IsEmpty (tarkistusjono on tyhjä vai ei) | O(1) |
- Aputila:
O(N) missä N on elementtien tallentamiseen tarkoitetun taulukon koko.
Array-toteutuksen edut:
- Helppo toteuttaa.
- Suuria tietomääriä voidaan hallita tehokkaasti ja vaivattomasti.
- Toiminnot, kuten lisääminen ja poistaminen, voidaan suorittaa helposti, koska se noudattaa ensin ensimmäinen ulos -sääntöä.
Array-toteutuksen haitat:
- Staattinen tietorakenne, kiinteä koko.
- Jos jonossa on suuri määrä jono- ja purkutoimintoja, jossain vaiheessa (etu- ja takaindeksien lineaarisen kasvun tapauksessa) emme ehkä pysty lisäämään elementtejä jonoon, vaikka jono olisi tyhjä (tämä ongelma vältetään käyttämällä pyöreää jonoa).
- Jonon enimmäiskoko on määritettävä etukäteen.