Similar cu Queue este o structură de date liniară care urmează o anumită ordine în care sunt efectuate operațiunile pentru stocarea datelor. Comanda este First In First Out (FIFO) . Ne putem imagina o coadă ca un rând de oameni care așteaptă să primească ceva în ordine secvențială care începe de la începutul rândului. Este o listă ordonată în care inserările se fac la un capăt, care este cunoscut sub numele de spate, iar ștergerile se fac de la celălalt capăt cunoscut sub numele de față. Un bun exemplu de coadă este orice coadă de consumatori pentru o resursă în care consumatorul care a venit primul este servit primul.
Diferența dintre stive și cozi este în eliminare. Într-o stivă eliminăm articolul cel mai recent adăugat; într-o coadă, eliminăm articolul cel mai puțin recent adăugat.
Structura datelor din coadă
Operații de bază în coadă:
- enqueue(): Inserează un element la sfârșitul cozii, adică la capătul din spate. dequeue(): Această operație elimină și returnează un element care se află la capătul cozii. front(): Această operație returnează elementul din partea din față fără a-l elimina. rear(): Această operație returnează elementul din partea din spate fără a-l îndepărta. isEmpty(): Această operație indică dacă coada este goală sau nu. isFull(): Această operație indică dacă coada este plină sau nu. size(): Această operație returnează dimensiunea cozii, adică numărul total de elemente pe care le conține.
Tipuri de cozi:
- Coadă simplă: coada simplă, cunoscută și sub numele de coadă liniară, este cea mai simplă versiune a unei cozi. Aici, inserarea unui element, adică operațiunea de adăpostire are loc în partea din spate, iar îndepărtarea unui element, adică operațiunea de scoatere din coadă are loc în partea din față. Aici problema este că, dacă punem un articol din față și apoi din spate ajunge la capacitatea cozii și, deși există spații goale înainte de față înseamnă că coada nu este plină, dar conform condițiilor din funcția isFull(), va arăta că coada este plină atunci. Pentru a rezolva această problemă folosim coada circulară.
- Coada circulară : Într-o coadă circulară, elementul cozii acționează ca un inel circular. Funcționarea unei cozi circulare este similară cu cea liniară, cu excepția faptului că ultimul element este conectat la primul element. Avantajul său este că memoria este utilizată într-un mod mai bun. Acest lucru se datorează faptului că, dacă există un spațiu gol, adică dacă niciun element nu este prezent într-o anumită poziție în coadă, atunci un element poate fi adăugat cu ușurință în acea poziție folosind capacitatea modulo ( %n ).
- Coada prioritară : Această coadă este un tip special de coadă. Specialitatea sa este că aranjează elementele într-o coadă în funcție de o anumită prioritate. Prioritatea poate fi ceva în care elementul cu cea mai mare valoare are prioritate, astfel încât creează o coadă cu ordine descrescătoare a valorilor. Prioritatea poate fi, de asemenea, astfel încât elementul cu cea mai mică valoare să primească cea mai mare prioritate, astfel încât, la rândul său, creează o coadă cu ordine crescătoare a valorilor. În coada de priorități predefinite, C++ dă prioritate valorii celei mai mari, în timp ce Java acordă prioritate valorii celei mai mici.
- În consecinţă : Scoaterea la coadă este cunoscută și sub numele de coadă dublă. După cum sugerează și numele dublu, înseamnă că un element poate fi introdus sau scos de la ambele capete ale cozii, spre deosebire de celelalte cozi în care se poate face doar de la un capăt. Din cauza acestei proprietăți, este posibil să nu se supună proprietății First In First Out.
Aplicații de coadă:
Coada este folosită atunci când lucrurile nu trebuie procesate imediat, ci trebuie procesate în F în primul rând eu n F în primul rând O ut comanda like Latimea prima cautare . Această proprietate a Queue îl face util și în următoarele tipuri de scenarii.
inkscape vs gimp
- Când o resursă este partajată între mai mulți consumatori. Exemplele includ programarea CPU, programarea discului. Când datele sunt transferate asincron (datele nu sunt neapărat primite la aceeași rată ca cele trimise) între două procese. Exemplele includ IO Buffer-uri, conducte, fișier IO, etc. Coada poate fi folosită ca o componentă esențială în diferite alte structuri de date.
Implementarea matricei de coadă:
Pentru implementarea cozii, trebuie să urmărim doi indici, față și spate. Punem în coadă un articol în spate și scoatem un articol din față. Dacă pur și simplu creștem indici față și spate, atunci pot apărea probleme, partea din față poate ajunge la sfârșitul matricei. Soluția la această problemă este creșterea față și spate într-o manieră circulară.
Pași pentru coadă:
- Verificați dacă coada este plină sau nu
- Dacă este plin, imprimați depășire și ieșiți
- Dacă coada nu este plină, creșteți coada și adăugați elementul
Pași pentru scoaterea din coadă:
- Coada de verificare este goală sau nu
- dacă este gol, tipăriți underflow și ieșiți
- dacă nu este gol, imprimați elementul la cap și incrementați capul
Mai jos este un program pentru implementarea operațiunii de mai sus la coadă
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->capacitate = capacitate;> >queue->front = coada->dimensiune = 0;> >// This is important, see the enqueue> >queue->spate = capacitate - 1;> >queue->matrice =>new> int>[queue->capacitate];> >return> queue;> }> // Queue is full when size> // becomes equal to the capacity> int> isFull(Queue* queue)> {> >return> (queue->dimensiune == coada->capacitate);> }> // Queue is empty when size is 0> int> isEmpty(Queue* queue)> {> >return> (queue->dimensiune == 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->spate = (coadă->spate + 1)> >% queue->capacitate;> >queue->array[queue->rear] = item;> >queue->dimensiune = coada->dimensiune + 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->matrice[coadă->față];> >queue->front = (coadă->front + 1)> >% queue->capacitate;> >queue->dimensiune = coada->dimensiune - 1;> >return> item;> }> // Function to get front of queue> int> front(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->matrice[coadă->față];> }> // Function to get rear of queue> int> rear(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->matrice[coadă->spate];> }> // 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
// 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->capacitate = capacitate;> >queue->front = coada->dimensiune = 0;> >// This is important, see the enqueue> >queue->spate = capacitate - 1;> >queue->matrice = (>int>*)>malloc>(> >queue->capacitate *>>>int>));> >return> queue;> }> // Queue is full when size becomes> // equal to the capacity> int> isFull(>struct> Queue* queue)> {> >return> (queue->dimensiune == coada->capacitate);> }> // Queue is empty when size is 0> int> isEmpty(>struct> Queue* queue)> {> >return> (queue->dimensiune == 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->spate = (coadă->spate + 1)> >% queue->capacitate;> >queue->array[queue->rear] = item;> >queue->dimensiune = coada->dimensiune + 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->matrice[coadă->față];> >queue->front = (coadă->front + 1)> >% queue->capacitate;> >queue->dimensiune = coada->dimensiune - 1;> >return> item;> }> // Function to get front of queue> int> front(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->matrice[coadă->față];> }> // Function to get rear of queue> int> rear(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->matrice[coadă->spate];> }> // 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;> }> |
cum se rulează un script în linux
>
>
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
hopa concepte
# 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#
diferența dintre array și arraylist
// 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();> >}> }> }> |
>
>
tutorial ssis
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> > |
>
>Ieșire
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>
Analiza complexității:
- Complexitatea timpului
| Operațiuni | Complexitate |
|---|---|
| Pune în coadă (inserție) | O(1) |
| Deque (ștergere) | O(1) |
| În față (Ia în față) | O(1) |
| Spate (Ia din spate) | O(1) |
| IsFull (Coada de verificare este plină sau nu) | O(1) |
| IsEmpty (Coada de verificare este goală sau nu) | O(1) |
- Spațiu auxiliar:
O(N) unde N este dimensiunea matricei pentru stocarea elementelor.
Avantajele implementării matricei:
- Ușor de implementat.
- O cantitate mare de date poate fi gestionată eficient cu ușurință.
- Operațiuni precum inserarea și ștergerea pot fi efectuate cu ușurință, deoarece respectă regula primul intrat, primul ieșit.
Dezavantajele implementării matricei:
- Structură de date statice, dimensiune fixă.
- Dacă coada are un număr mare de operații de așezare și scoatere din coadă, la un moment dat (în cazul creșterii liniare a indicilor din față și din spate) este posibil să nu putem introduce elemente în coadă chiar dacă coada este goală (această problemă este evitată prin utilizarea cozii circulare).
- Mărimea maximă a unei cozi trebuie definită anterior.