In diesem Tutorial erfahren Sie, was eine Warteschlange ist. Außerdem finden Sie die Implementierung der Warteschlange in C, C ++, Java und Python.
Eine Warteschlange ist eine nützliche Datenstruktur bei der Programmierung. Es ähnelt der Ticketwarteschlange vor einem Kinosaal, bei der die erste Person, die die Warteschlange betritt, die erste Person ist, die das Ticket erhält.
Die Warteschlange folgt der FIFO- Regel (First In First Out). Das Element, das zuerst eingeht, ist das Element, das zuerst ausgegeben wird.
FIFO-Darstellung der Warteschlange
Da im obigen Bild 1 vor 2 in der Warteschlange gehalten wurde, wird es auch als erstes aus der Warteschlange entfernt. Es folgt der FIFO- Regel.
In Bezug auf die Programmierung wird das Einfügen von Elementen in die Warteschlange als Enqueue und das Entfernen von Elementen aus der Warteschlange als Dequeue bezeichnet .
Wir können die Warteschlange in jeder Programmiersprache wie C, C ++, Java, Python oder C # implementieren, aber die Spezifikation ist ziemlich gleich.
Grundlegende Operationen der Warteschlange
Eine Warteschlange ist ein Objekt (eine abstrakte Datenstruktur - ADT), das die folgenden Operationen ermöglicht:
- Enqueue : Fügen Sie am Ende der Warteschlange ein Element hinzu
- Dequeue : Entfernen Sie ein Element von der Vorderseite der Warteschlange
- IsEmpty : Überprüfen Sie, ob die Warteschlange leer ist
- IsFull : Überprüfen Sie, ob die Warteschlange voll ist
- Peek : Ermittelt den Wert der Vorderseite der Warteschlange, ohne ihn zu entfernen
Arbeiten der Warteschlange
Warteschlangenoperationen funktionieren wie folgt:
- zwei Zeiger VORNE und HINTEN
- FRONT verfolgt das erste Element der Warteschlange
- REAR verfolgt das letzte Element der Warteschlange
- Setzen Sie zunächst den Wert von FRONT und REAR auf -1
Warteschlangenbetrieb
- Überprüfen Sie, ob die Warteschlange voll ist
- Setzen Sie für das erste Element den Wert von FRONT auf 0
- Erhöhen Sie den REAR-Index um 1
- Fügen Sie das neue Element an der Position hinzu, auf die REAR zeigt
Warteschlangenbetrieb
- Überprüfen Sie, ob die Warteschlange leer ist
- Geben Sie den Wert zurück, auf den FRONT zeigt
- Erhöhen Sie den FRONT-Index um 1
- Setzen Sie für das letzte Element die Werte von FRONT und REAR auf -1 zurück
Enqueue- und Dequeue-Operationen
Warteschlangenimplementierungen in Python, Java, C und C ++
Wir verwenden normalerweise Arrays, um Warteschlangen in Java und C / ++ zu implementieren. Im Fall von Python verwenden wir Listen.
Python Java C C ++ # Queue implementation in Python class Queue: def __init__(self): self.queue = () # Add an element def enqueue(self, item): self.queue.append(item) # Remove an element def dequeue(self): if len(self.queue) < 1: return None return self.queue.pop(0) # Display the queue def display(self): print(self.queue) def size(self): return len(self.queue) q = Queue() q.enqueue(1) q.enqueue(2) q.enqueue(3) q.enqueue(4) q.enqueue(5) q.display() q.dequeue() print("After removing an element") q.display()
// Queue implementation in Java public class Queue ( int SIZE = 5; int items() = new int(SIZE); int front, rear; Queue() ( front = -1; rear = -1; ) boolean isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) return false; ) boolean isEmpty() ( if (front == -1) return true; else return false; ) void enQueue(int element) ( if (isFull()) ( System.out.println("Queue is full"); ) else ( if (front == -1) front = 0; rear++; items(rear) = element; System.out.println("Inserted " + element); ) ) int deQueue() ( int element; if (isEmpty()) ( System.out.println("Queue is empty"); return (-1); ) else ( element = items(front); if (front>= rear) ( front = -1; rear = -1; ) /* Q has only one element, so we reset the queue after deleting it. */ else ( front++; ) System.out.println("Deleted -> " + element); return (element); ) ) void display() ( /* Function to display elements of Queue */ int i; if (isEmpty()) ( System.out.println("Empty Queue"); ) else ( System.out.println("Front index-> " + front); System.out.println("Items -> "); for (i = front; i " + rear); ) ) public static void main(String() args) ( Queue q = new Queue(); // deQueue is not possible on empty queue q.deQueue(); // enQueue 5 elements q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // 6th element can't be added to because the queue is full q.enQueue(6); q.display(); // deQueue removes element entered first i.e. 1 q.deQueue(); // Now we have just 4 elements q.display(); ) )
// Queue implementation in C #include #define SIZE 5 void enQueue(int); void deQueue(); void display(); int items(SIZE), front = -1, rear = -1; int main() ( //deQueue is not possible on empty queue deQueue(); //enQueue 5 elements enQueue(1); enQueue(2); enQueue(3); enQueue(4); enQueue(5); // 6th element can't be added to because the queue is full enQueue(6); display(); //deQueue removes element entered first i.e. 1 deQueue(); //Now we have just 4 elements display(); return 0; ) void enQueue(int value) ( if (rear == SIZE - 1) printf("Queue is Full!!"); else ( if (front == -1) front = 0; rear++; items(rear) = value; printf("Inserted -> %d", value); ) ) void deQueue() ( if (front == -1) printf("Queue is Empty!!"); else ( printf("Deleted : %d", items(front)); front++; if (front> rear) front = rear = -1; ) ) // Function to print the queue void display() ( if (rear == -1) printf("Queue is Empty!!!"); else ( int i; printf("Queue elements are:"); for (i = front; i <= rear; i++) printf("%d ", items(i)); ) printf(""); )
// Queue implementation in C++ #include #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" <= rear) ( front = -1; rear = -1; ) /* Q has only one element, so we reset the queue after deleting it. */ else ( front++; ) cout << endl < " << element << endl; return (element); ) ) void display() ( /* Function to display elements of Queue */ int i; if (isEmpty()) ( cout << endl << "Empty Queue" << endl; ) else ( cout << endl < " << front; cout << endl < "; for (i = front; i <= rear; i++) cout << items(i) << " "; cout << endl < " << rear << endl; ) ) ); int main() ( Queue q; //deQueue is not possible on empty queue q.deQueue(); //enQueue 5 elements q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // 6th element can't be added to because the queue is full q.enQueue(6); q.display(); //deQueue removes element entered first i.e. 1 q.deQueue(); //Now we have just 4 elements q.display(); return 0; )
Einschränkungen der Warteschlange
Wie Sie im Bild unten sehen können, wurde die Größe der Warteschlange nach einigem Ein- und Ausreihen verringert.
Einschränkung einer Warteschlange
Und wir können die Indizes 0 und 1 nur hinzufügen, wenn die Warteschlange zurückgesetzt wird (wenn alle Elemente aus der Warteschlange entfernt wurden).
Wenn REAR den letzten Index erreicht hat und zusätzliche Elemente in den Leerzeichen (0 und 1) gespeichert werden können, können wir die Leerzeichen verwenden. Dies wird durch eine modifizierte Warteschlange implementiert, die als zirkuläre Warteschlange bezeichnet wird.
Komplexitätsanalyse
Die Komplexität von Enqueue- und Dequeue-Operationen in einer Warteschlange unter Verwendung eines Arrays ist O(1).
Anwendungen der Warteschlange
- CPU-Planung, Festplattenplanung
- Wenn Daten asynchron zwischen zwei Prozessen übertragen werden. Die Warteschlange wird für die Synchronisation verwendet. Zum Beispiel: E / A-Puffer, Pipes, Datei-E / A usw.
- Behandlung von Interrupts in Echtzeitsystemen.
- Call Center-Telefonsysteme verwenden Warteschlangen, um Personen, die sie anrufen, in der richtigen Reihenfolge zu halten.
Empfohlene Lektüre
- Arten von Warteschlangen
- Kreisförmige Warteschlange
- Deque-Datenstruktur
- Prioritätswarteschlange
