Stacks und Ques

Sqwan

Hey

Hab mal eine Frage.
In der FH machen wir so tolle Ques und Stacks.
In etwas so:

class Daten<T>
{
    public T wert;
    public Daten<T> next;
}

Also verkettete Listen. Bis dahin kein problem.
Ich frage mich nur grade, gibt es eine sinnvolle Anwendung für sowas?
Mir fällt nichts ein. Es kommt mir fast sinnlos vor das da so viel wert drauf gelegt wird.

Kann mir einer die wichtigkeit erklären oder ists vllt wirklich blödsinn?

Danke schon mal
Sqwan

Athar

gibt es eine sinnvolle Anwendung für sowas?

Meinst du etwa verkettete Listen? Das will ich meinen!
Verkette Listen erlauben Einfüge- und Löschoperationen an jeder Stelle der Liste in konstanter Zeit und man kann sie trotzdem in linearer Zeit durchqueren.
Zeiger/Iteratoren auf Knoten werden nicht ungültig, wenn andere Teile der Liste umgebaut werden. Damit sind verkettete Listen eine der grundlegendsten Datenstrukturen der Informatik.

Stacks und Queues können mithilfe einer verketteten Liste implementiert werden, müssen aber nicht.

DerBaer

ein Konkretes Anwendungsbeispiel für einen Stack ist zum Beispiel ein Taschenrechner(einer der nicht nur jede Operation einzeln auswertet, sondern auch
2+4*(3^5-6+(4 / 8)) erlaubt.

RHBaum

anderes Beispiel aus der Praxis:

Ich hab eine hardware, die schickt mir nachrichten (Struktur mit einer ID und einem X Byte langem Datenfeld)

auf der anderen seite hab ich nen Thread der die daten verarbeit ... durch den thread muessen die "zwischengepuffert" werden, da ich nen threadwechsel mach, und es nicht garantiert ist, das ich gleich nach jedem incomming sofort in meinem Thread die nachricht entgegennehmen kann.
Die reihenfolge soll gewahrt bleiben.

Was werd ich also nehmen ? nen Fifo in kombination mit nem Threadmutex sicherlich. Wie implementiert man nen fifo wohl am besten ?
Willkommen in der welt der Container.

Wobei du schon differenzieren solltest, zwischen VerhaltensMuster (Stack, Queue/FIFO) und der technischen Realisierung der Ablage, also dem eigentlichen Container (Verkettete Liste, Array, Baeume, HashMaps ... )

in der STL ist ein Stack z.b. eine std::list, mit Aufgesetzten Adapter std::stack (DesignPattern - proxy / Adapter) der die funktionalitaet der Liste einschraenkt, und die Schnittstellen anpasst.
Man kannst dem std::stack aber auch nen anderen Container als unterbau verpassen, wenn man will ...

Ciao ...

volkard

DerBaer schrieb:

ein Konkretes Anwendungsbeispiel für einen Stack ist zum Beispiel ein Taschenrechner(einer der nicht nur jede Operation einzeln auswertet, sondern auch
2+4*(3^5-6+(4 / 8)) erlaubt.

Naja. Ob da eine verkette Liste drin ist? Ich sage mal, das ist nicht der Fall.

volkard

RHBaum schrieb:

auf der anderen seite hab ich nen Thread der die daten verarbeit ... durch den thread muessen die "zwischengepuffert" werden, da ich nen threadwechsel mach, und es nicht garantiert ist, das ich gleich nach jedem incomming sofort in meinem Thread die nachricht entgegennehmen kann.
Die reihenfolge soll gewahrt bleiben.

Was werd ich also nehmen ? nen Fifo in kombination mit nem Threadmutex sicherlich. Wie implementiert man nen fifo wohl am besten ?
Willkommen in der welt der Container.

Hat der Herr uns nicht genau für diesen Zweck die Pipe geschenkt? Meinetwegen nichtmal die Daten pipen, sondern Zeiger auf die Strukturen.

volkard

Athar schrieb:

gibt es eine sinnvolle Anwendung für sowas?

Meinst du etwa verkettete Listen? Das will ich meinen!
Verkette Listen erlauben Einfüge- und Löschoperationen an jeder Stelle der Liste in konstanter Zeit und man kann sie trotzdem in linearer Zeit durchqueren.

Und wo ist die sinnvolle Anwendung? Obige rekursiv definierte Liste ist leider ein typisches Hochschulprodukt, wo anscheinend der Listenschmerz durch Rekursionsschmerz neutralisiert werden soll. Mit linearem Hintenanfügen, was einem aber auch gar nicht mehr weh tut, nachdem man in der main ein li=VorneAnfuegen(li,15); geschrieben hat.

Athar schrieb:

Zeiger/Iteratoren auf Knoten werden nicht ungültig, wenn andere Teile der Liste umgebaut werden.

Brauche ich nie. Dafür gebe ich keinen Pluspunkt.

Athar schrieb:

Damit sind verkettete Listen eine der grundlegendsten Datenstrukturen der Informatik.

Ja, sind sie. Aber nicht deswegen.

volkard

Sqwan schrieb:

Ich frage mich nur grade, gibt es eine sinnvolle Anwendung für sowas?

Selten. Ein Beispiel, wo ich Listen benutze, weil sie was anbieten, das Arrays nicht schnell können, sind MoveToFront-Listen.

Jester

volkard schrieb:

Athar schrieb:

Zeiger/Iteratoren auf Knoten werden nicht ungültig, wenn andere Teile der Liste umgebaut werden.

Brauche ich nie. Dafür gebe ich keinen Pluspunkt.

brauche ich ständig. Zum Beispiel wenn ich ne Kante in meinem Graphen hab und will sie effizient löschen ohne dass meine ganzen anderen Kanten, die ich mir grad in anderen Variablen merke ungültig werden. Insofern ist das aus meiner Sicht der größte Pluspunkt überhaupt. Außerdem kann ich zwei Listen ganz effizient zusammenhängen... auch prima!