Ähnlich wie bei Queue handelt es sich um eine lineare Datenstruktur, die einer bestimmten Reihenfolge folgt, in der die Vorgänge zum Speichern von Daten ausgeführt werden. Die Reihenfolge lautet First In First Out (FIFO) . Man kann sich eine Warteschlange als eine Reihe von Menschen vorstellen, die darauf warten, etwas zu erhalten, und zwar in der Reihenfolge, die am Anfang der Warteschlange beginnt. Es handelt sich um eine geordnete Liste, in der Einfügungen an einem Ende erfolgen, das als Rückseite bezeichnet wird, und Löschungen am anderen Ende, das als Vorderseite bezeichnet wird. Ein gutes Beispiel für eine Warteschlange ist eine beliebige Warteschlange von Verbrauchern für eine Ressource, bei der der Verbraucher, der zuerst kam, zuerst bedient wird.
Der Unterschied zwischen Stapeln und Warteschlangen besteht im Entfernen. In einem Stapel entfernen wir das zuletzt hinzugefügte Element. In einer Warteschlange entfernen wir das Element, das am längsten hinzugefügt wurde.
Warteschlangendatenstruktur
Grundlegende Vorgänge in der Warteschlange:
- enqueue(): Fügt ein Element am Ende der Warteschlange ein, also am hinteren Ende. dequeue(): Diese Operation entfernt ein Element, das sich am vorderen Ende der Warteschlange befindet, und gibt es zurück. front(): Diese Operation gibt das Element am vorderen Ende zurück, ohne es zu entfernen. hinten(): Diese Operation gibt das Element am hinteren Ende zurück, ohne es zu entfernen. isEmpty(): Diese Operation gibt an, ob die Warteschlange leer ist oder nicht. isFull(): Diese Operation gibt an, ob die Warteschlange voll ist oder nicht. size(): Diese Operation gibt die Größe der Warteschlange zurück, d. h. die Gesamtzahl der darin enthaltenen Elemente.
Arten von Warteschlangen:
- Einfache Warteschlange: Die einfache Warteschlange, auch lineare Warteschlange genannt, ist die einfachste Version einer Warteschlange. Hier erfolgt das Einfügen eines Elements, d. h. die Enqueue-Operation, am hinteren Ende und das Entfernen eines Elements, d. h. die Dequeue-Operation, am vorderen Ende. Hier besteht das Problem darin, dass wir, wenn wir ein Element von vorne und dann von hinten platzieren, die Kapazität der Warteschlange erreichen und obwohl vorn Leerzeichen vorhanden sind, bedeutet dies, dass die Warteschlange nicht voll ist, aber gemäß der Bedingung in der Funktion isFull() wird angezeigt, dass die Dann ist die Warteschlange voll. Um dieses Problem zu lösen, verwenden wir eine kreisförmige Warteschlange.
- Runde Warteschlange : In einer kreisförmigen Warteschlange fungieren die Elemente der Warteschlange als kreisförmiger Ring. Die Funktionsweise einer zirkulären Warteschlange ähnelt der der linearen Warteschlange, mit der Ausnahme, dass das letzte Element mit dem ersten Element verbunden ist. Der Vorteil besteht darin, dass der Speicher besser genutzt wird. Dies liegt daran, dass, wenn ein Leerraum vorhanden ist, d. h. wenn an einer bestimmten Position in der Warteschlange kein Element vorhanden ist, mithilfe der Modulo-Kapazität einfach ein Element an dieser Position hinzugefügt werden kann( %N ).
- Prioritätswarteschlange : Bei dieser Warteschlange handelt es sich um einen besonderen Warteschlangentyp. Seine Besonderheit besteht darin, dass es die Elemente in einer Warteschlange nach einer bestimmten Priorität anordnet. Die Priorität kann etwas sein, bei dem das Element mit dem höchsten Wert die Priorität hat, sodass eine Warteschlange mit absteigender Reihenfolge der Werte erstellt wird. Die Priorität kann auch so sein, dass das Element mit dem niedrigsten Wert die höchste Priorität erhält, sodass wiederum eine Warteschlange mit aufsteigender Reihenfolge der Werte erstellt wird. In der vordefinierten Prioritätswarteschlange gibt C++ dem höchsten Wert Priorität, während Java dem niedrigsten Wert Priorität einräumt.
- Entsprechend : Dequeue wird auch als Double Ended Queue bezeichnet. Wie der Name bereits vermuten lässt, bedeutet dies, dass ein Element an beiden Enden der Warteschlange eingefügt oder entfernt werden kann, im Gegensatz zu den anderen Warteschlangen, bei denen dies nur an einem Ende möglich ist. Aufgrund dieser Eigenschaft gehorcht es möglicherweise nicht der First-In-First-Out-Eigenschaft.
Anwendungen der Warteschlange:
Die Warteschlange wird verwendet, wenn Dinge nicht sofort verarbeitet werden müssen, sondern verarbeitet werden müssen F zuerst ICH N F zuerst Ö ut bestellen wie Breitensuche . Diese Eigenschaft von Queue macht es auch in folgenden Szenarios nützlich.
- Wenn eine Ressource von mehreren Verbrauchern gemeinsam genutzt wird. Beispiele hierfür sind CPU-Planung und Festplattenplanung. Wenn Daten asynchron zwischen zwei Prozessen übertragen werden (Daten werden nicht unbedingt mit der gleichen Geschwindigkeit empfangen wie gesendet). Beispiele hierfür sind E/A-Puffer, Pipes, Datei-E/A usw. Die Warteschlange kann als wesentliche Komponente in verschiedenen anderen Datenstrukturen verwendet werden.
Array-Implementierung der Warteschlange:
Um die Warteschlange zu implementieren, müssen wir zwei Indizes im Auge behalten, den vorderen und den hinteren. Wir stellen einen Artikel hinten in die Warteschlange und einen Artikel vorne aus der Warteschlange. Wenn wir einfach die vorderen und hinteren Indizes erhöhen, kann es zu Problemen kommen, da die Vorderseite möglicherweise das Ende des Arrays erreicht. Die Lösung dieses Problems besteht darin, vorne und hinten kreisförmig zu vergrößern.
Schritte zum Einreihen:
- Überprüfen Sie, ob die Warteschlange voll ist oder nicht
- Wenn voll, Überlauf drucken und beenden
- Wenn die Warteschlange nicht voll ist, erhöhen Sie tail und fügen Sie das Element hinzu
Schritte zum Entfernen aus der Warteschlange:
- Überprüfen Sie, ob die Warteschlange leer ist oder nicht
- Wenn leer, Unterlauf drucken und beenden
- Wenn nicht leer, Element am Kopf drucken und Kopf erhöhen
Nachfolgend finden Sie ein Programm zur Implementierung der oben genannten Operation in der Warteschlange
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->Kapazität = Kapazität;> >queue->front = queue->size = 0;> >// This is important, see the enqueue> >queue->hinten = Kapazität - 1;> >queue->array =>new> int>[queue->Kapazität];> >return> queue;> }> // Queue is full when size> // becomes equal to the capacity> int> isFull(Queue* queue)> {> >return> (queue->size == queue->capacity);> }> // Queue is empty when size is 0> int> isEmpty(Queue* queue)> {> >return> (queue->Größe == 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->hinten = (Warteschlange->hinten + 1)> >% queue->Kapazität;> >queue->array[queue->rear] = item;> >queue->size = queue->size + 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[queue->front];> >queue->front = (queue->front + 1)> >% queue->Kapazität;> >queue->size = queue->size - 1;> >return> item;> }> // Function to get front of queue> int> front(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[queue->front];> }> // Function to get rear of queue> int> rear(Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[queue->rear];> }> // 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
stdin c-Programmierung
// 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->Kapazität = Kapazität;> >queue->front = queue->size = 0;> >// This is important, see the enqueue> >queue->hinten = Kapazität - 1;> >queue->array = (>int>*)>malloc>(> >queue->Kapazität *>sizeof>(>int>));> >return> queue;> }> // Queue is full when size becomes> // equal to the capacity> int> isFull(>struct> Queue* queue)> {> >return> (queue->size == queue->capacity);> }> // Queue is empty when size is 0> int> isEmpty(>struct> Queue* queue)> {> >return> (queue->Größe == 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->hinten = (Warteschlange->hinten + 1)> >% queue->Kapazität;> >queue->array[queue->rear] = item;> >queue->size = queue->size + 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[queue->front];> >queue->front = (queue->front + 1)> >% queue->Kapazität;> >queue->size = queue->size - 1;> >return> item;> }> // Function to get front of queue> int> front(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[queue->front];> }> // Function to get rear of queue> int> rear(>struct> Queue* queue)> {> >if> (isEmpty(queue))> >return> INT_MIN;> >return> queue->array[queue->rear];> }> // 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 stapeln
// 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
Rekursion in Java
# 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();> >}> }> }> |
VLC Media Player auf YouTube herunterladen
>
>
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> > |
>
>Ausgabe
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>
Komplexitätsanalyse:
- Zeitkomplexität
| Operationen | Komplexität |
|---|---|
| In die Warteschlange stellen (Einfügung) | O(1) |
| Deque(Löschung) | O(1) |
| Vorne (Vorne gehen) | O(1) |
| Hinten (Nach hinten kommen) | O(1) |
| IsFull (Überprüfen Sie, ob die Warteschlange voll ist oder nicht) | O(1) |
| IsEmpty(Überprüfen Sie, ob die Warteschlange leer ist oder nicht) | O(1) |
- Hilfsraum:
O(N) wobei N die Größe des Arrays zum Speichern von Elementen ist.
Vorteile der Array-Implementierung:
- Einfach umzusetzen.
- Große Datenmengen können problemlos und effizient verwaltet werden.
- Vorgänge wie Einfügen und Löschen können problemlos durchgeführt werden, da die First-In-First-Out-Regel befolgt wird.
Nachteile der Array-Implementierung:
- Statische Datenstruktur, feste Größe.
- Wenn die Warteschlange eine große Anzahl von Enqueue- und Dequeue-Vorgängen aufweist, können wir irgendwann (im Falle einer linearen Erhöhung der vorderen und hinteren Indizes) möglicherweise keine Elemente mehr in die Warteschlange einfügen, selbst wenn die Warteschlange leer ist (dieses Problem wird vermieden). durch Verwendung einer zirkulären Warteschlange).
- Die maximale Größe einer Warteschlange muss zuvor definiert werden.