Datenstruktur und Algorithmen - Warteschlange

Queue ist eine abstrakte Datenstruktur, die Stacks ähnelt. Im Gegensatz zu Stapeln ist eine Warteschlange an beiden Enden offen. Ein Ende wird immer zum Einfügen von Daten (Enqueue) und das andere zum Entfernen von Daten (Dequeue) verwendet. Die Warteschlange folgt der First-In-First-Out-Methode, dh auf das zuerst gespeicherte Datenelement wird zuerst zugegriffen.

Ein reales Beispiel für eine Warteschlange kann eine einspurige Einbahnstraße sein, bei der das Fahrzeug zuerst ein- und zuerst ausfährt. Weitere Beispiele aus der Praxis können als Warteschlangen an den Fahrkartenschaltern und Bushaltestellen angesehen werden.

Warteschlangendarstellung

Da wir jetzt verstehen, dass wir in der Warteschlange aus unterschiedlichen Gründen auf beide Enden zugreifen. Das folgende Diagramm versucht, die Darstellung der Warteschlange als Datenstruktur zu erklären.

Wie in Stapeln kann eine Warteschlange auch mithilfe von Arrays, verknüpften Listen, Zeigern und Strukturen implementiert werden. Der Einfachheit halber werden wir Warteschlangen unter Verwendung eines eindimensionalen Arrays implementieren.

Grundoperationen

Bei Warteschlangenoperationen kann die Warteschlange initialisiert oder definiert, verwendet und dann vollständig aus dem Speicher gelöscht werden. Hier werden wir versuchen, die grundlegenden Operationen zu verstehen, die mit Warteschlangen verbunden sind -

enqueue() - Hinzufügen (Speichern) eines Elements zur Warteschlange.
dequeue() - Entfernen (Zugreifen) eines Elements aus der Warteschlange.

Es sind nur wenige weitere Funktionen erforderlich, um den oben genannten Warteschlangenbetrieb effizient zu gestalten. Dies sind -

peek() - Ruft das Element an der Vorderseite der Warteschlange ab, ohne es zu entfernen.
isfull() - Überprüft, ob die Warteschlange voll ist.
isempty() - Überprüft, ob die Warteschlange leer ist.

In der Warteschlange werden Daten, auf die verwiesen wird, immer aus der Warteschlange entfernt (oder auf Daten zugegriffen) front Zeiger und beim Einreihen (oder Speichern) von Daten in die Warteschlange helfen wir rear Zeiger.

Lassen Sie uns zunächst die unterstützenden Funktionen einer Warteschlange kennenlernen -

spähen()

Diese Funktion hilft, die Daten am zu sehen frontder Warteschlange. Der Algorithmus der Funktion peek () lautet wie folgt:

Algorithm

begin procedure peek
   return queue[front]
end procedure

Implementierung der Funktion peek () in der Programmiersprache C -

Example

int peek() {
   return queue[front];
}

ist voll()

Da wir zum Implementieren der Warteschlange ein Array mit einer Dimension verwenden, prüfen wir nur, ob der hintere Zeiger bei MAXSIZE erreicht ist, um festzustellen, ob die Warteschlange voll ist. Wenn wir die Warteschlange in einer zirkulären verknüpften Liste verwalten, unterscheidet sich der Algorithmus. Algorithmus der isfull () Funktion -

Algorithm

begin procedure isfull

   if rear equals to MAXSIZE
      return true
   else
      return false
   endif
   
end procedure

Implementierung der Funktion isfull () in der Programmiersprache C -

Example

bool isfull() {
   if(rear == MAXSIZE - 1)
      return true;
   else
      return false;
}

ist leer()

Algorithmus der Funktion isempty () -

Algorithm

begin procedure isempty

   if front is less than MIN  OR front is greater than rear
      return true
   else
      return false
   endif
   
end procedure

Wenn der Wert von front kleiner als MIN oder 0 ist, bedeutet dies, dass die Warteschlange noch nicht initialisiert und daher leer ist.

Hier ist der C-Programmcode -

Example

bool isempty() {
   if(front < 0 || front > rear) 
      return true;
   else
      return false;
}

Warteschlangenbetrieb

Warteschlangen verwalten zwei Datenzeiger. front und rear. Daher sind seine Operationen vergleichsweise schwierig zu implementieren als die von Stapeln.

Die folgenden Schritte sollten ausgeführt werden, um Daten in eine Warteschlange zu stellen (einzufügen):

Step 1 - Überprüfen Sie, ob die Warteschlange voll ist.
Step 2 - Wenn die Warteschlange voll ist, erzeugen Sie einen Überlauffehler und beenden Sie den Vorgang.
Step 3 - Wenn die Warteschlange nicht voll ist, erhöhen Sie sie rear Zeiger auf den nächsten leeren Raum.
Step 4 - Fügen Sie ein Datenelement zur Warteschlangenposition hinzu, auf die die Rückseite zeigt.
Step 5 - Erfolg zurückgeben.

Manchmal prüfen wir auch, ob eine Warteschlange initialisiert ist oder nicht, um unvorhergesehene Situationen zu bewältigen.

Algorithmus für den Enqueue-Betrieb

procedure enqueue(data)      
   
   if queue is full
      return overflow
   endif
   
   rear ← rear + 1
   queue[rear] ← data
   return true
   
end procedure

Implementierung von enqueue () in der Programmiersprache C -

Example

int enqueue(int data)      
   if(isfull())
      return 0;
   
   rear = rear + 1;
   queue[rear] = data;
   
   return 1;
end procedure

Warteschlangenbetrieb

Der Zugriff auf Daten aus der Warteschlange besteht aus zwei Aufgaben: Zugriff auf die Daten wo frontzeigt und entfernt die Daten nach dem Zugriff. Die folgenden Schritte werden ausgeführtdequeue Betrieb -

Step 1 - Überprüfen Sie, ob die Warteschlange leer ist.
Step 2 - Wenn die Warteschlange leer ist, erzeugen Sie einen Unterlauffehler und beenden Sie den Vorgang.
Step 3 - Wenn die Warteschlange nicht leer ist, greifen Sie auf die Daten zu, bei denen front zeigt.
Step 4 - Inkrementieren front Zeiger auf das nächste verfügbare Datenelement.
Step 5 - Erfolg zurückgeben.

Algorithmus für den Dequeue-Betrieb

procedure dequeue
   
   if queue is empty
      return underflow
   end if

   data = queue[front]
   front ← front + 1
   return true

end procedure

Implementierung von dequeue () in der Programmiersprache C -

Example

int dequeue() {
   if(isempty())
      return 0;

   int data = queue[front];
   front = front + 1;

   return data;
}

Für ein vollständiges Warteschlangenprogramm in der Programmiersprache C klicken Sie bitte hier .