Die kreisförmige Warteschlange vermeidet Platzverschwendung bei der üblichen Implementierung einer Warteschlange mit Arrays.
DeQueue – Entfernen eines Elements aus der Warteschlange;
FRONT und REAR sind zwei Zeiger, die verwendet werden, um das erste und letzte Element in der Warteschlange zu verfolgen.
Wie Sie im obigen Bild sehen können, wurde seine Größe nach einigem Einreihen und Entfernen aus der Warteschlange reduziert.
Die Indizes 0 und 1 können nur verwendet werden, nachdem die Warteschlange geleert wurde, wenn alle Elemente entfernt wurden.
So funktioniert die kreisförmige Warteschlange
Eine kreisförmige Warteschlange arbeitet mit einem kreisförmigen Inkrementierungsprozess, dh wenn wir versuchen, eine Variable zu inkrementieren und das Ende der Warteschlange erreichen, beginnen wir am Anfang der Warteschlangen-Modulo-Division mit der Warteschlangengröße.
Also:
if REAR + 1 == 5 (overflow!), REAR = (REAR + 1)%5 = 0 (start of queue)
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.
- Wenn wir ein Element aus der Warteschlange entfernen, geben wir den Wert zurück, auf den FRONT zeigt, und erhöhen allmählich den FRONT-Index.
- Vor dem Anstehen prüfen wir, ob die Warteschlange voll ist.
- Vor dem Entfernen der Warteschlange 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.
Die Überprüfung auf eine volle Warteschlange hat jedoch eine neue zusätzliche Klausel:
- Fall 1: VORNE = 0 && HINTEN == GRÖSSE - 1
- Fall 2: VORNE = HINTEN + 1
Der zweite Fall tritt auf, wenn REAR aufgrund des kreisförmigen Inkrements bei 0 beginnt und wenn sein Wert nur um 1 kleiner als FRONT ist, die Warteschlange voll ist.
Implementierung einer zyklischen Warteschlange in einer Programmiersprache
Die gebräuchlichste Implementierung einer Warteschlange verwendet Arrays, aber eine Implementierung unter Verwendung von Listen kann ebenfalls möglich sein.
Implementierung mit C-Programmierung
#include <stdio.h>
#define SIZE 5
int items[SIZE];
int front = -1, rear =-1;
int isFull()
{
if( (front == rear + 1) || (front == 0 && rear == SIZE-1)) return 1;
return 0;
}
int isEmpty()
{
if(front == -1) return 1;
return 0;
}
void enQueue(int element)
{
if(isFull()) printf("\n Queue is full!! \n");
else
{
if(front == -1) front = 0;
rear = (rear + 1) % SIZE;
items[rear] = element;
printf("\n Inserted -> %d", element);
}
}
int deQueue()
{
int element;
if(isEmpty()) {
printf("\n Queue is empty !! \n");
return(-1);
} else {
element = items[front];
if (front == rear){
front = -1;
rear = -1;
} /* В Q есть только один элемент, поэтому мы сбрасываем очередь после ее удаления. */
else {
front = (front + 1) % SIZE;
}
printf("\n Deleted element -> %d \n", element);
return(element);
}
}
void display()
{
int i;
if(isEmpty()) printf(" \n Empty Queue\n");
else
{
printf("\n Front -> %d ",front);
printf("\n Items -> ");
for( i = front; i!=rear; i=(i+1)%SIZE) {
printf("%d ",items[i]);
}
printf("%d ",items[i]);
printf("\n Rear -> %d \n",rear);
}
}
int main()
{
// Ложь, потому что front = -1
deQueue();
enQueue(1);
enQueue(2);
enQueue(3);
enQueue(4);
enQueue(5);
// Невозможно поставить в очередь, потому что front == 0 && rear == SIZE - 1
enQueue(6);
display();
deQueue();
display();
enQueue(7);
display();
// Невозможно поставить в очередь, потому что front == rear + 1
enQueue(8);
return 0;
}
Wenn Sie dieses Programm ausführen, erhalten Sie Folgendes:
Inserted -> 1 Inserted -> 2 Inserted -> 3 Inserted -> 4 Inserted -> 5 Queue is full!! Front -> 0 Items -> 1 2 3 4 5 Rear -> 4 Deleted element -> 1 Front -> 1 Items -> 2 3 4 5 Rear -> 4 Inserted -> 7 Front -> 1 Items -> 2 3 4 5 7 Rear -> 0 Queue is full!!
Implementierung mit 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;
}
if(front == rear + 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 = (rear + 1) % SIZE;
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=(front+1) % SIZE;
}
return(element);
}
}
void display()
{
/* Функция для отображения статуса круговой очереди */
int i;
if(isEmpty()) {
cout << endl << "Empty Queue" << endl;
}
else
{
cout << "Front -> " << front;
cout << endl << "Items -> ";
for(i=front; i!=rear;i=(i+1)%SIZE)
cout << items[i];
cout << items[i];
cout << endl << "Rear -> " << rear;
}
}
};
int main()
{
Queue q;
// Ложь, потому что front = -1
q.deQueue();
q.enQueue(1);
q.enQueue(2);
q.enQueue(3);
q.enQueue(4);
q.enQueue(5);
// Невозможно поставить в очередь, потому что 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();
// Невозможно поставить в очередь, потому что front == rear + 1
q.enQueue(8);
return 0;
}
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 Front -> 0 Items -> 12345 Rear -> 4 Deleted Element is 1 Front -> 1 Items -> 2345 Rear -> 4 Inserted 7 Front -> 1 Items -> 23457 Rear -> 0 Queue is full
