Das deutsche Python-Forum

Hallo,

ich benötige Hilfe bei folgender Aufgabe:

Implementiere einen Stack unter Verwendung einer einfach verketteten Liste durch folgende Funktionen:
StackInit, IsEmpty, IsFull, Push, Pop, Top, und PopTop.
und
Implementiere eine Queue unter Verwendung einer einfach verketteten Liste durch folgende Funktionen:
QueueInit, IsEmpty, IsFull, Put, Get, und Front.

Wie kann ich hier vorgehen?
Danke

@jj12: In dem Du Dir als erstes überlegst wie Du die einfach verkettete Liste als Datenstruktur implementieren möchtest. Was ist denn dafür erlaubt oder bekannt? Darfst/kannst Du Klassen schreiben? Oder sind wir hier auf ”LISP Niveau” und müssen Tupel als ”cons”-Paare verwenden?

Oder gibt es bereits eine einfach verkettete Liste und Funktionen die dafür definiert sind, auf die man zurückgreifen kann?

Wie ist die Semantik von `is_full()` definiert? Verkettete Listen haben ja die nette Eigenschaft, das sie praktisch unendlich gross werden können, also nicht ”voll” werden. Dementsprechend bräuchte man so eine Beschränkung auch bei Queues und Stapeln nicht.

Findet sich in der Einführung von Michael Weigend (4. Aufl., 2010) auf den Seiten 721 (Stack) und S. 724 (Queue). In beiden Fällen wird im Hintergrund eine Liste genutzt.

@pixewakb: laut Aufgabenstellung soll aber eine verkettete Liste verwendet werden und keine, wie sie in Python standard ist. Zumal es unsinnig ist einen Stack mit einer Liste programmieren zu wollen. In Python hat der Datentyp list schon alle Methoden, die typischerweise von einem Stack erwartet werden, nur dass push append heißt.

Was genau ist eine verkettete Liste? Welchen Datentyp würdest Du anstelle verwenden?

@pixewakb: eine verkettete Liste ist eine Kette von Strukturen, bestehend aus den eigentlichen Daten und einem Verweis auf das nächste Element der Liste, naja, bei einem Stack eher das vorangehende Element.

@pixewakb: Wikipedia hat da was zu: Liste (Datenstruktur)