Vergelijkbaar met Queue is een lineaire datastructuur die een bepaalde volgorde volgt waarin de bewerkingen worden uitgevoerd voor het opslaan van gegevens. De volgorde is: eerst in, eerst uit (FIFO) . Je kunt je een wachtrij voorstellen als een rij mensen die wachten op iets, in opeenvolgende volgorde, beginnend vanaf het begin van de rij. Het is een geordende lijst waarin invoegingen worden gedaan aan het ene uiteinde, dat bekend staat als de achterkant, en verwijderingen worden gedaan vanaf het andere uiteinde, bekend als de voorkant. Een goed voorbeeld van een wachtrij is elke wachtrij van consumenten voor een hulpbron waarbij de consument die het eerst kwam, als eerste wordt bediend.
Het verschil tussen stapels en wachtrijen zit in het verwijderen. In een stapel verwijderen we het meest recent toegevoegde item; in een wachtrij verwijderen we het item dat het minst recent is toegevoegd.
Wachtrij Gegevensstructuur
Basisbewerkingen in de wachtrij:
- enqueue(): Voegt een element in aan het einde van de wachtrij, d.w.z. aan de achterkant. dequeue(): Deze bewerking verwijdert en retourneert een element dat zich aan de voorkant van de wachtrij bevindt. front(): Deze bewerking retourneert het element aan de voorkant zonder het te verwijderen. achter(): Deze bewerking retourneert het element aan de achterkant zonder het te verwijderen. isEmpty(): Deze bewerking geeft aan of de wachtrij leeg is of niet. isFull(): Deze bewerking geeft aan of de wachtrij vol is of niet. size(): Deze bewerking retourneert de grootte van de wachtrij, d.w.z. het totale aantal elementen dat deze bevat.
Soorten wachtrijen:
- Eenvoudige wachtrij: Eenvoudige wachtrij, ook wel lineaire wachtrij genoemd, is de meest eenvoudige versie van een wachtrij. Hier vindt het inbrengen van een element, d.w.z. de Enqueue-bewerking, plaats aan de achterkant en het verwijderen van een element, d.w.z. de Dequeue-bewerking, vindt plaats aan de voorkant. Het probleem hier is dat als we een item van voren en vervolgens van achteren naar voren halen, de capaciteit van de wachtrij bereiken en hoewel er lege ruimtes vóór de voorkant zijn, betekent dit dat de wachtrij niet vol is, maar volgens de voorwaarde in de functie isFull() zal dit aantonen dat de wachtrij is dan vol. Om dit probleem op te lossen gebruiken we een circulaire wachtrij.
- Circulaire wachtrij : In een cirkelvormige wachtrij fungeert het element van de wachtrij als een cirkelvormige ring. De werking van een circulaire wachtrij is vergelijkbaar met de lineaire wachtrij, behalve dat het laatste element verbonden is met het eerste element. Het voordeel is dat het geheugen op een betere manier wordt gebruikt. Dit komt omdat als er een lege ruimte is, d.w.z. als er geen element aanwezig is op een bepaalde positie in de wachtrij, een element eenvoudig op die positie kan worden toegevoegd met behulp van modulo-capaciteit( %N ).
- Prioriteits-rij : Deze wachtrij is een speciaal type wachtrij. Zijn specialiteit is dat het de elementen in een wachtrij rangschikt op basis van een bepaalde prioriteit. De prioriteit kan iets zijn waarbij het element met de hoogste waarde de prioriteit heeft, zodat er een wachtrij ontstaat met afnemende volgorde van waarden. De prioriteit kan ook zodanig zijn dat het element met de laagste waarde de hoogste prioriteit krijgt, zodat er op zijn beurt een wachtrij ontstaat met oplopende volgorde van waarden. In een vooraf gedefinieerde prioriteitswachtrij geeft C++ prioriteit aan de hoogste waarde, terwijl Java prioriteit geeft aan de laagste waarde.
- Overeenkomstig : Dequeue wordt ook wel Double Ended Queue genoemd. Zoals de naam double-ended suggereert, betekent dit dat een element aan beide uiteinden van de wachtrij kan worden ingevoegd of verwijderd, in tegenstelling tot de andere wachtrijen waarin dit alleen vanaf één uiteinde kan worden gedaan. Vanwege deze eigenschap kan het zijn dat de First In First Out-eigenschap niet wordt nageleefd.
Toepassingen van wachtrij:
Wachtrij wordt gebruikt wanneer zaken niet direct verwerkt hoeven te worden, maar wel in verwerkt moeten worden F eerst I N F eerst O ut bestelling zoals Breedte eerste zoekopdracht . Deze eigenschap van Queue maakt het ook nuttig bij de volgende soorten scenario's.
- Wanneer een hulpbron wordt gedeeld door meerdere consumenten. Voorbeelden hiervan zijn CPU-planning en schijfplanning. Wanneer gegevens asynchroon worden overgedragen (gegevens worden niet noodzakelijkerwijs met dezelfde snelheid ontvangen als verzonden) tussen twee processen. Voorbeelden zijn onder meer IO-buffers, pipelines, bestands-IO, etc. Queue kan worden gebruikt als een essentieel onderdeel in verschillende andere datastructuren.
Array-implementatie van wachtrij:
Voor het implementeren van de wachtrij moeten we twee indices bijhouden, voor en achter. We zetten een item aan de achterkant in de wachtrij en halen een item aan de voorkant uit de wachtrij. Als we eenvoudigweg de voor- en achterindices verhogen, kunnen er problemen optreden: de voorkant kan het einde van de array bereiken. De oplossing voor dit probleem is om de voor- en achterkant cirkelvormig te vergroten.
Stappen voor de wachtrij:
- Controleer of de wachtrij vol is of niet
- Indien vol, print overflow en sluit af
- Als de wachtrij niet vol is, verhoog dan de staart en voeg het element toe
Stappen voor het uit de wachtrij halen:
- Controleer wachtrij is leeg of niet
- indien leeg, print underflow en exit
- indien niet leeg, druk het element af bij de kop en verhoog de kop
Hieronder vindt u een programma om bovenstaande bewerking in de wachtrij te implementeren
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->capaciteit = capaciteit;> >queue->voorkant = wachtrij->grootte = 0;> >// This is important, see the enqueue> >queue->achter = capaciteit - 1;> >queue->array =>new> int>[queue->capaciteit];> >return> queue;> }> // Queue is full when size> // becomes equal to the capacity> int> isFull(Queue* queue)> {> >return> (queue->size == wachtrij->capaciteit);> }> // Queue is empty when size is 0> int> isEmpty(Queue* queue)> {> >return> (queue->maat == 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->achter = (wachtrij->achter + 1)> >% queue->capaciteit;> >queue->array[wachtrij->achter] = item;> >queue->grootte = wachtrij->grootte + 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[wachtrij->voor];> >queue->voorkant = (wachtrij->voor + 1)> >% queue->capaciteit;> >queue->grootte = wachtrij->grootte - 1;> >return> item;> }> // Function to get front of queue> int> front(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[wachtrij->voor];> }> // Function to get rear of queue> int> rear(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[wachtrij->achter];> }> // 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->capaciteit = capaciteit;> >queue->voorkant = wachtrij->grootte = 0;> >// This is important, see the enqueue> >queue->achter = capaciteit - 1;> >queue->array = (>int>*)>malloc>(> >queue->capaciteit *>sizeof>(>int>));> >return> queue;> }> // Queue is full when size becomes> // equal to the capacity> int> isFull(>struct> Queue* queue)> {> >return> (queue->size == wachtrij->capaciteit);> }> // Queue is empty when size is 0> int> isEmpty(>struct> Queue* queue)> {> >return> (queue->maat == 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->achter = (wachtrij->achter + 1)> >% queue->capaciteit;> >queue->array[wachtrij->achter] = item;> >queue->grootte = wachtrij->grootte + 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[wachtrij->voor];> >queue->voorkant = (wachtrij->voor + 1)> >% queue->capaciteit;> >queue->grootte = wachtrij->grootte - 1;> >return> item;> }> // Function to get front of queue> int> front(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[wachtrij->voor];> }> // Function to get rear of queue> int> rear(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[wachtrij->achter];> }> // 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
als het anders bashen is
> // 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> > |
>
>Uitvoer
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>
Complexiteitsanalyse:
- Tijdcomplexiteit
| Activiteiten | Complexiteit |
|---|---|
| In wachtrij plaatsen (invoeging) | O(1) |
| Deque(verwijdering) | O(1) |
| Voorkant (voorkant krijgen) | O(1) |
| Achterkant (achterkant krijgen) | O(1) |
| IsFull(controleer of de wachtrij vol is of niet) | O(1) |
| IsEmpty(controleer of de wachtrij leeg is of niet) | O(1) |
- Hulpruimte:
O(N) waarbij N de grootte is van de array voor het opslaan van elementen.
Voordelen van array-implementatie:
- Eenvoudig te implementeren.
- Een grote hoeveelheid gegevens kan eenvoudig en efficiënt worden beheerd.
- Bewerkingen zoals invoegen en verwijderen kunnen gemakkelijk worden uitgevoerd omdat de regel 'first in, first out' wordt gevolgd.
Nadelen van array-implementatie:
- Statische gegevensstructuur, vaste grootte.
- Als de wachtrij een groot aantal in- en uitqueue-bewerkingen heeft, kunnen we op een gegeven moment (in het geval van lineaire toename van de voor- en achterindexen) mogelijk geen elementen in de wachtrij invoegen, zelfs als de wachtrij leeg is (dit probleem wordt vermeden door gebruik te maken van een circulaire wachtrij).
- De maximale grootte van een wachtrij moet vooraf worden gedefinieerd.