Eine Warteschlange ist eine nützliche Datenstruktur beim Programmieren. Stellen Sie sich eine Warteschlange mit Eintrittskarten außerhalb eines Kinos vor, in der die erste Person, die sich in die Warteschlange begibt, auch die erste Person ist, die eine Eintrittskarte erhält.
Die Warteschlange folgt der First In First Out (FIFO)-Regel – das Element, das zuerst kommt, ist das Element, das zuerst herauskommt.
Betrachten Sie die Zeichnung. Da 1 vor 2 in die Warteschlange gestellt wird, verlässt er auch als erster die Warteschlange. Es folgt der FIFO-Regel.
Aus Sicht der Programmierung wird das Platzieren eines Elements in der Warteschlange (leere Warteschlange - eine leere Warteschlange) als "enqueue" bezeichnet, und das Entfernen eines Elements aus der Warteschlange wird als "dequeue" bezeichnet.
Wir können eine Warteschlange in jeder Programmiersprache wie C, C++, Java, Python oder C# mit fast derselben Spezifikation implementieren.
Technische Eigenschaften der Warteschlange
Eine Warteschlange ist ein Objekt oder genauer gesagt eine abstrakte Datenstruktur (ADT), mit der Sie die folgenden Operationen ausführen können:
- Enqueue: füge ein Element am Ende der Warteschlange hinzu;
- Dequeue: Entfernen Sie ein Element von der Vorderseite der Warteschlange;
- IsEmpty: prüfen, ob die Warteschlange leer ist;
- IsFull: Prüfen Sie, ob die Warteschlange voll ist;
- Peek: Holen Sie sich den Wert des Starts der Warteschlange, ohne ihn zu löschen.
Wie die Warteschlange funktioniert
Warteschlangenoperationen funktionieren wie folgt:
- Zwei Zeiger namens FRONT und REAR werden verwendet, um das erste und letzte Element in der Warteschlange zu verfolgen.
- Beim Initialisieren der Warteschlange setzen wir den Wert von FRONT und REAR auf -1.
- Beim Hinzufügen eines Elements erhöhen wir den Wert des REAR-Index und platzieren das neue Element an der Position, auf die REAR zeigt.
- Beim Entfernen eines Elements aus der Warteschlange geben wir den Wert zurück, auf den FRONT zeigt, und inkrementieren den FRONT-Index.
- Vor dem Anstehen prüfen wir, ob die Warteschlange voll ist.
- Bevor wir die Warteschlange entfernen, prüfen wir, ob die Warteschlange leer ist.
- Beim Initialisieren des ersten Elements setzen wir den Wert von FRONT auf 0.
- Beim Entfernen des letzten Elements setzen wir die Werte FRONT und REAR auf -1 zurück.
Implementierung einer Warteschlange in einer Programmiersprache
Die häufigste Implementierung einer Warteschlange verwendet Arrays, aber eine Warteschlange kann auch mithilfe von Listen implementiert werden.
Implementierung mit C-Programmierung
#include<stdio.h>
#define SIZE 5
void enQueue(int);
void deQueue();
void display();
int items[SIZE], front = -1, rear = -1;
int main()
{
//deQueue невозможно в пустой очереди
deQueue();
//enQueue 5 elements
enQueue(1);
enQueue(2);
enQueue(3);
enQueue(4);
enQueue(5);
//6-й элемент не может быть добавлен в очередь, потому что очередь заполнена
enQueue(6);
display();
//deQueue удаляет элемент, введенный первым, т.е. 1
deQueue();
//Теперь у нас всего 4 элемента
display();
return 0;
}
void enQueue(int value){
if(rear == SIZE-1)
printf("\nQueue is Full!!");
else {
if(front == -1)
front = 0;
rear++;
items[rear] = value;
printf("\nInserted -> %d", value);
}
}
void deQueue(){
if(front == -1)
printf("\nQueue is Empty!!");
else{
printf("\nDeleted : %d", items[front]);
front++;
if(front > rear)
front = rear = -1;
}
}
void display(){
if(rear == -1)
printf("\nQueue is Empty!!!");
else{
int i;
printf("\nQueue elements are:\n");
for(i=front; i<=rear; i++)
printf("%d\t",items[i]);
}
}
Wenn Sie dieses Programm ausführen, erhalten Sie Folgendes:
Queue is Empty!! Inserted -> 1 Inserted -> 2 Inserted -> 3 Inserted -> 4 Inserted -> 5 Queue is Full!! Queue elements are: 1 2 3 4 5 Deleted : 1 Queue elements are: 2 3 4 5
Implementierung mittels C-Programmierung ++
#include <iostream>
#define SIZE 5
using namespace std;
class Queue {
private:
int items[SIZE], front, rear;
public:
Queue(){
front = -1;
rear = -1;
}
bool isFull(){
if(front == 0 && rear == SIZE - 1){
return true;
}
return false;
}
bool isEmpty(){
if(front == -1) return true;
else return false;
}
void enQueue(int element){
if(isFull()){
cout << "Queue is full";
} else {
if(front == -1) front = 0;
rear++;
items[rear] = element;
cout << endl << "Inserted " << element << endl;
}
}
int deQueue(){
int element;
if(isEmpty()){
cout << "Queue is empty" << endl;
return(-1);
} else {
element = items[front];
if(front >= rear){
front = -1;
rear = -1;
} /* В Q есть только один элемент, поэтому мы удаляем очередь после удаления. */
else {
front++;
}
cout << endl << "Deleted -> " << element << endl;
return(element);
}
}
void display()
{
/* Функция для отображения элементов очереди */
int i;
if(isEmpty()) {
cout << endl << "Empty Queue" << endl;
}
else
{
cout << endl << "Front -> " << front;
cout << endl << "Items -> ";
for(i=front; i<=rear; i++)
cout << items[i] << ""\t";
cout << endl << "Rear -> " << rear << endl;
}
}
};
int main()
{
Queue q;
//deQueue невозможно в пустой очереди
q.deQueue();
//enQueue 5 элементов
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
q.enQueue(4);
q.enQueue(5);
//6-й элемент не может быть добавлен в очередь, потому что очередь заполнена
q.enQueue(6);
q.display();
//deQueue удаляет элемент, введенный первым, т.е. 1
q.deQueue();
//Теперь у нас всего 4 элемента
q.display();
return 0;
}
Nach dem Ausführen erhalten wir:
Queue is empty Inserted 1 Inserted 2 Inserted 3 Inserted 4 Inserted 5 Queue is full Front -> 0 Items -> 1 2 3 4 5 Rear -> 4 Deleted -> 1 Front -> 1 Items -> 2 3 4 5 Rear -> 4
Einschränkung dieser Implementierung
Wie Sie im Bild unten sehen können, wurde die Größe der Warteschlange einige Zeit nach dem Hinzufügen zur Warteschlange und dem Entfernen aus der Warteschlange reduziert.
Die Indizes 0 und 1 können erst verwendet werden, nachdem die Warteschlange geleert wurde, wenn alle Elemente entfernt wurden.
Durch Ändern des Codes für die Warteschlange können wir den Speicherplatz nutzen, indem wir eine modifizierte Warteschlange implementieren, die als kreisförmige Warteschlange bezeichnet wird.
