// Übung zu Listen: Stack von Strings mit einfach verketteter Liste
//
// Aufruf: list-stack
//
// Klaus Kusche, 2018

#include <iostream>
#include <string>

using namespace std;

// Klasse für ein einzelnes Element der Liste
// an sich würde eine Struktur statt einer Klasse genügen,
// aber eine Klasse hat einen schönen Konstruktor
class Elem
{
  // "Elem" soll nur innerhalb von "StrStack" verwendbar sein
  // wir machen daher alles in Elem privat (==> keiner kann darauf zugreifen)
  // und erklären StrStack zum Freund (==> aber StrStack darf alles)
  friend class StrStack;

  private:
    // Konstruktor:
    // Wir legen gleich beim Anlegen eines Elementes
    // seinen Wert und seinen Nachfolger fest
    Elem(const string &s, Elem *n) : str(s), next(n) {}

    string str;  // die Nutzdaten: Ein String
    Elem *next;  // die Listen-Verkettung (Zeiger auf das nächste Element)
};

// Klasse für den Stack als Ganzes
class StrStack
{
  public:
    // Konstruktor:
    // Ein neuer Stack wird auf "leer" initialisiert
    // (keine Elemente ==> head ist der Nullpointer)
    StrStack() : head(nullptr) {}

    // push:
    // Lege den Wert str oben auf den Stack
    // (d.h. hänge ihn vorne an die Liste)
    void push(const string &str) {
      // neues Element mit Wert str erzeugen
      // Nachfolger des neuen Elementes ist das bisherige erste Element
      // das neue Element wird neues erstes Element
      head = new Elem(str, head);
    }

    // pop:
    // Entnimm das oberste Element aus dem Stack
    // (d.h. entferne das vorderste Element aus der Liste)
    // und speichere seinen Wert in "str"
    // Returnwert: true wenn erfolgreich, false wenn Stack leer
    bool pop(string &str) {
      // Liste bzw. Stack leer? (kein erstes Element?)
      if (head == nullptr) {
        return false;
      }
      
      Elem *tmp = head;  // das vorderste Element der Liste wird entnommen
      head = tmp->next;  // dessen Nachfolger wird neues vorderstes Element
      str = tmp->str;    // dessen Wert wird im Aufrufer gespeichert
      delete tmp;        // Nicht vergessen: Dann wird das Element gelöscht
                         // (sein Speicher freigegeben)
      
      return true;
    }

  private:
    Elem *head;  // Zeiger auf das erste (oberste) Element
                 // einen Zeiger auf das letzte Element brauchen wir nicht
};

int main()
{
  string wort;
  StrStack st;

  while (cin >> wort) {
    st.push(wort);
  }

  while (st.pop(wort)) {
    cout << wort << ' ';
  }
  cout << endl;

  return 0;
}