class Waggon
{  int inhalt;
   Waggon naechste;
} // class Waggon


class WaggonStack
{ Waggon anker = null;

  boolean isEmpty()
  { return (anker == null); }

  void push(int nummer)
  { Waggon neu = new Waggon();
    neu.inhalt = nummer;
    neu.naechste = anker; // wenn leer, dann auch richtig.
    anker = neu;
  } // push

  int pop()
  { int ablage = 0; // Rueckgabe bei leerem WaggonStack
    if (!isEmpty())
         { ablage = anker.inhalt;
           anker = anker.naechste;
         }
    return ablage;
  } // pop

  int readTop()
  { return anker.inhalt;
  } // readTop
} // class WaggonStack


class Gleise1
{
  static WaggonStack gleisA = new WaggonStack();
  static WaggonStack gleisB = new WaggonStack();
  static WaggonStack gleisC = new WaggonStack();

  static void startgleisAnlegen()
  { gleisA.push(16);
    gleisA.push(11);
    gleisA.push(15);
    gleisA.push(13);
    gleisA.push(20);
    gleisA.push(10);
    gleisA.push(19);
    gleisA.push(7);
    gleisA.push(6);
    gleisA.push(3);
  }

  static void sortiereWaggons()
  { int wagennr;
    wagennr = gleisA.pop(); // Ersten Wagen auf alle Faelle
    gleisC.push(wagennr);   // von A nach C
    
    while ((!gleisA.isEmpty()) || (!gleisB.isEmpty()))
    { verschiebe (gleisA, gleisB, gleisC); // Gleis A wird geleert
      if (!gleisB.isEmpty())               // Gleis B (Ablage) nicht leer.
           verschiebe (gleisB, gleisA, gleisC);
                                           // Gleis A ist nun Ablage.
    } // while
  } // sortiere Waggons


  static void verschiebe (WaggonStack start, WaggonStack ablage, WaggonStack ziel)
  { // leert start und fuellt u.U. ablage auf
    int startwagennr;
    int zielwagennr;
    while (!start.isEmpty())
    {    do
         { startwagennr = start.readTop();
           zielwagennr  = ziel.readTop();
           if (startwagennr < zielwagennr)
                { zielwagennr = ziel.pop(); // Waggon vom Ziel
                  ablage.push(zielwagennr); // in Ablage schieben
                }
         } while ((zielwagennr > startwagennr) && (!ziel.isEmpty()));
         startwagennr = start.pop();
         ziel.push(startwagennr);
    } // while
  } // verschiebe


  static void kontrolle(WaggonStack gleis)
  { int nr;
    while (!gleis.isEmpty())
    { nr = gleis.pop();
      Out.println("Auf dem Gleis steht Nr. " + nr);
    } // while
  } // kontrolle

  public static void main(String[] arg)
  {
    startgleisAnlegen();
    sortiereWaggons();
    kontrolle(gleisC);
    kontrolle(gleisB);
    kontrolle(gleisA);
  } // main
} // class Gleise1