// sl-4-BA : Der ADT Queue
// schönes Beispiel für Ringlisten

#include "queue.h"

struct Queue { // einfach verkettete Ringliste: Anker zeigt auf das Queue-Ende
  DataType value; // front zeigt allgemein auf das nachfolgende Element
  QueuePtr front;  // "Anker"->front zeigt als Ringschluss auf das vorderste
};

void empty(QueuePtr & q) {
  while (!is_empty(q)) { dequeue(q); }
  // q = 0; würde auch funktionieren, Speicher würde aber nicht freigegeben
}

bool is_empty(const QueuePtr q) {
  return q==0; // Kurzform von if (q==0) { return true; } else { return false; }
}

void enqueue(QueuePtr & q, const DataType value) {
  if (q==0) {
    q = new Queue; // erstes Element in der Queue
    q->value=value;
    q->front=q; // erstes und letztes Element sind identisch
  } else {
    QueuePtr node = new Queue;
    node->value = value;
    node->front = q->front;
    q->front = node;
    q = node;
  }
}

void dequeue(QueuePtr & q) { // q darf nicht 0 sein!
  // die aufrufende Funktion muss ggf. mit is_empty(q) prüfen, ob q leer ist
  if (q->front==q) { // ist es das einzige Element in der Queue?
    delete q;
    q=0;
  } else {
    QueuePtr tbd = q->front; // Zeiger für zu löschendes Element merken
    q->front = q->front->front;
    delete tbd;
  }
}

DataType front(const QueuePtr q) { // q darf nicht 0 sein!
  // die aufrufende Funktion muss ggf. mit is_empty(q) prüfen, ob q leer ist
  return q->front->value;
}