Datenstruktur der zirkulären Warteschlange

In diesem Tutorial erfahren Sie, was eine kreisförmige Warteschlange ist. Außerdem finden Sie die Implementierung einer zirkulären Warteschlange in C, C ++, Java und Python.

Die kreisförmige Warteschlange vermeidet die Verschwendung von Speicherplatz in einer regulären Warteschlangenimplementierung mithilfe von Arrays.

Einschränkung der regulären Warteschlange

Wie Sie im obigen Bild sehen können, wurde die Größe der Warteschlange nach einigem Ein- und Ausreihen verringert.

Die Indizes 0 und 1 können nur verwendet werden, nachdem die Warteschlange zurückgesetzt wurde, wenn alle Elemente aus der Warteschlange entfernt wurden.

Wie Circular Queue funktioniert

Die kreisförmige Warteschlange arbeitet nach dem Verfahren der zirkulären Inkrementierung. Wenn wir also versuchen, den Zeiger zu inkrementieren und das Ende der Warteschlange erreichen, beginnen wir am Anfang der Warteschlange.

Hier wird das kreisförmige Inkrement durch Modulodivision mit der Warteschlangengröße durchgeführt. Das ist,

 wenn REAR + 1 == 5 (Überlauf!), REAR = (REAR + 1)% 5 = 0 (Beginn der Warteschlange)
Kreisförmige Warteschlangendarstellung

Circular Queue Operations

Die kreisförmige Warteschlange funktioniert wie folgt:

  • zwei Zeiger VORNE und HINTEN
  • FRONT verfolgt das erste Element der Warteschlange
  • REAR verfolgt die letzten Elemente der Warteschlange
  • Setzen Sie zunächst den Wert von FRONT und REAR auf -1

1. Betrieb in die Warteschlange stellen

  • Ü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 kreisförmig um 1 (dh wenn das Heck das Ende erreicht, befindet es sich als nächstes am Anfang der Warteschlange).
  • Fügen Sie das neue Element an der Position hinzu, auf die REAR zeigt

2. Betrieb aus der Warteschlange entfernen

  • Überprüfen Sie, ob die Warteschlange leer ist
  • Geben Sie den Wert zurück, auf den FRONT zeigt
  • Erhöhen Sie den FRONT-Index kreisförmig um 1
  • Setzen Sie für das letzte Element die Werte von FRONT und REAR auf -1 zurück

Die Prüfung auf volle Warteschlange hat jedoch einen neuen zusätzlichen Fall:

  • Fall 1: FRONT = 0 && REAR == SIZE - 1
  • Fall 2: FRONT = REAR + 1

Der zweite Fall tritt auf, wenn REAR aufgrund eines zirkulären Inkrements von 0 beginnt und wenn sein Wert nur 1 kleiner als FRONT ist, ist die Warteschlange voll.

Enque- und Deque-Operationen

Circular Queue-Implementierungen in Python, Java, C und C ++

Die häufigste Warteschlangenimplementierung verwendet Arrays, kann jedoch auch mithilfe von Listen implementiert werden.

Python Java C C + 
 # Circular Queue implementation in Python class MyCircularQueue(): def __init__(self, k): self.k = k self.queue = (None) * k self.head = self.tail = -1 # Insert an element into the circular queue def enqueue(self, data): if ((self.tail + 1) % self.k == self.head): print("The circular queue is full") elif (self.head == -1): self.head = 0 self.tail = 0 self.queue(self.tail) = data else: self.tail = (self.tail + 1) % self.k self.queue(self.tail) = data # Delete an element from the circular queue def dequeue(self): if (self.head == -1): print("The circular queue is empty") elif (self.head == self.tail): temp = self.queue(self.head) self.head = -1 self.tail = -1 return temp else: temp = self.queue(self.head) self.head = (self.head + 1) % self.k return temp def printCQueue(self): if(self.head == -1): print("No element in the circular queue") elif (self.tail>= self.head): for i in range(self.head, self.tail + 1): print(self.queue(i), end=" ") print() else: for i in range(self.head, self.k): print(self.queue(i), end=" ") for i in range(0, self.tail + 1): print(self.queue(i), end=" ") print() # Your MyCircularQueue object will be instantiated and called as such: obj = MyCircularQueue(5) obj.enqueue(1) obj.enqueue(2) obj.enqueue(3) obj.enqueue(4) obj.enqueue(5) print("Initial queue") obj.printCQueue() obj.dequeue() print("After removing an element from the queue") obj.printCQueue() 
 // Circular Queue implementation in Java public class CQueue ( int SIZE = 5; // Size of Circular Queue int front, rear; int items() = new int(SIZE); CQueue() ( front = -1; rear = -1; ) // Check if the queue is full boolean isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) if (front == rear + 1) ( return true; ) return false; ) // Check if the queue is empty boolean isEmpty() ( if (front == -1) return true; else return false; ) // Adding an element void enQueue(int element) ( if (isFull()) ( System.out.println("Queue is full"); ) else ( if (front == -1) front = 0; rear = (rear + 1) % SIZE; items(rear) = element; System.out.println("Inserted " + element); ) ) // Removing an 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 = (front + 1) % SIZE; ) return (element); ) ) void display() ( /* Function to display status of Circular Queue */ int i; if (isEmpty()) ( System.out.println("Empty Queue"); ) else ( System.out.println("Front -> " + front); System.out.println("Items -> "); for (i = front; i != rear; i = (i + 1) % SIZE) System.out.print(items(i) + " "); System.out.println(items(i)); System.out.println("Rear -> " + rear); ) ) public static void main(String() args) ( CQueue q = new CQueue(); // Fails because front = -1 q.deQueue(); q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // Fails to enqueue because front == 0 && rear == SIZE - 1 q.enQueue(6); q.display(); int elem = q.deQueue(); if (elem != -1) ( System.out.println("Deleted Element is " + elem); ) q.display(); q.enQueue(7); q.display(); // Fails to enqueue because front == rear + 1 q.enQueue(8); ) )
 // Circular Queue implementation in C #include #define SIZE 5 int items(SIZE); int front = -1, rear = -1; // Check if the queue is full int isFull() ( if ((front == rear + 1) || (front == 0 && rear == SIZE - 1)) return 1; return 0; ) // Check if the queue is empty int isEmpty() ( if (front == -1) return 1; return 0; ) // Adding an element void enQueue(int element) ( if (isFull()) printf(" Queue is full!! "); else ( if (front == -1) front = 0; rear = (rear + 1) % SIZE; items(rear) = element; printf(" Inserted -> %d", element); ) ) // Removing an element int deQueue() ( int element; if (isEmpty()) ( printf(" 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 dequeing it. ? else ( front = (front + 1) % SIZE; ) printf(" Deleted element -> %d ", element); return (element); ) ) // Display the queue void display() ( int i; if (isEmpty()) printf(" Empty Queue"); else ( printf(" Front -> %d ", front); printf(" Items -> "); for (i = front; i != rear; i = (i + 1) % SIZE) ( printf("%d ", items(i)); ) printf("%d ", items(i)); printf(" Rear -> %d ", rear); ) ) int main() ( // Fails because front = -1 deQueue(); enQueue(1); enQueue(2); enQueue(3); enQueue(4); enQueue(5); // Fails to enqueue because front == 0 && rear == SIZE - 1 enQueue(6); display(); deQueue(); display(); enQueue(7); display(); // Fails to enqueue because front == rear + 1 enQueue(8); return 0; )
 // Circular Queue implementation in C++ #include #define SIZE 5 /* Size of Circular Queue */ using namespace std; class Queue ( private: int items(SIZE), front, rear; public: Queue() ( front = -1; rear = -1; ) // Check if the queue is full bool isFull() ( if (front == 0 && rear == SIZE - 1) ( return true; ) if (front == rear + 1) ( return true; ) return false; ) // Check if the queue is empty bool isEmpty() ( if (front == -1) return true; else return false; ) // Adding an element void enQueue(int element) ( if (isFull()) ( cout << "Queue is full"; ) else ( if (front == -1) front = 0; rear = (rear + 1) % SIZE; items(rear) = element; cout << endl << "Inserted " << element << endl; ) ) // Removing an element 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 has only one element, // so we reset the queue after deleting it. else ( front = (front + 1) % SIZE; ) return (element); ) ) void display() ( // Function to display status of Circular Queue int i; if (isEmpty()) ( cout << endl << "Empty Queue" << endl; ) else ( cout < " << front; cout << endl < "; for (i = front; i != rear; i = (i + 1) % SIZE) cout << items(i); cout << items(i); cout << endl < " << rear; ) ) ); int main() ( Queue q; // Fails because front = -1 q.deQueue(); q.enQueue(1); q.enQueue(2); q.enQueue(3); q.enQueue(4); q.enQueue(5); // Fails to enqueue because front == 0 && rear == SIZE - 1 q.enQueue(6); q.display(); int elem = q.deQueue(); if (elem != -1) cout << endl << "Deleted Element is " << elem; q.display(); q.enQueue(7); q.display(); // Fails to enqueue because front == rear + 1 q.enQueue(8); return 0; )

Komplexe Analyse der zirkulären Warteschlange

Die Komplexität der Enqueue- und Dequeue-Operationen einer kreisförmigen Warteschlange beträgt O (1) für (Array-Implementierungen).

Anwendungen der zirkulären Warteschlange

  • CPU-Planung
  • Speicherverwaltung
  • Verkehrsregelung

Interessante Beiträge...