Der berühmte Stack, bei dem ich den Wald vor lauter Bäumen nicht sehe.

Hallo zusammen,

ich habe die Aufgabe in C einen Stack zu implementieren. Nun habe ich mich mal generell erst mal mit dem Thema Stack auseinander gesetzt, leider fange ich da schon an mächtig zu schleudern und bräuchte da mal ein bisschen Hilfe was die eigentliche Funktion angeht.

Nun ich habe verstanden das ein Stack erst mal nichts anderes ist als ein Stapelpapier z.b bei dem ich ein Blatt aufs andere lege und dann alles nachher rückwärts wieder runter nehme. Also sprich das Last In – First Out Prinzip (LiFo).

So aber jetzt gehts los. Bitte nicht lachen aber ich raff nicht was ich genau davon habe. Warum nimmt man nicht einfach ein Array was man füllt und nachher wieder anderes rum ausgibt.

Ich verstehe einfach nicht den Sinn und den genauen Ablauf eines solchen Stacks.

Vielleicht könnte mir mal da jemand unter die Arme greifen. Ich will keine Lösung oder quellcode ich will einfach verstehen wie das alles sich zusammen verhält.

Ich hoffe mein Problem ist klar geworden.

Gruß

Sector

Also Stack funktioniert folgendermassen: Es gibt genau zwei Operationen drauf.

push(wert): Füge oben einen Wert hinzu
wert = pop(): Entferne den obersten Wert vom Stack und speichere ihn in einer Variable.

Wie du das ganze intern organisierst bleibt dir überlassen. Am zuverlässigsten dürfte wohl eine verkettete Liste sein - es sei denn, du hast Direktzugriff auf einen Speicherbereich (wie beispielsweise bei einem Microcontroller - da schreibst du einfach nen Wert hin, setzt den Stackpointer um ein Wort tiefer/höher und schreibst dort das nächste hin. Daher kommt auch die "Stapelarchitektur" - wobei Stack eigentlich Keller heisst :) )

Alle Klarheiten beseitigt?

MfG Bischi

Hallo bischi,

also leider hat mich deine Erklärung genausoweit gebracht wie ich schon war :D. Also ich soll das mit einem Array lösen aber warum macht man das ???? Ich meine warum speicher ich nicht einfach die Zahlen direkt in das array ab??? Also wo liegt der vorteil eines solchen Stacks ?????

Und wie soll dann sowas ablaufen ????? Da liegen meine Probleme


Gruß und danke erst mal für deine Antwort

Nun, ein Array ist vielleicht nicht so schlau weil du dich damit in der Grösse einschränkst ;)

Den Sinn und Ablauf siehst du am besten an einer konkreten Anwendung. Wenn du in C Programmierst sind das für dich direkt nicht so viele - ich wüsst jetzt wirklich nicht wozu ich in C "einfach so" einen Stack implementieren sollte. (Ausser ich will einen HP Taschenrechner nachbauen ;))
Wenn man die passende Funktionalität braucht dann wird das halt ein Stack. Ob man jetzt einen LIFO gerade benutzen kann - das springt einen eigenltich meist an - du kennst ja einigermassen die Anforderungen die du gerade hast :)

Aber im Hintergrund läuft einiges darüber - insbesondere auch das Aufrufen von Funktionen und Übergeben von Parametern an die Funktionen läuft oft über einen Stack (oft - kommt auf die Architektur/Programmiersprache/ABI drauf an, man kann das auch anders lösen...) - d.h. wenn eine Funktion aufgerufen wird legt der Aufrufer Rücksprungadresse und Argumente auf den Stack; die Aufgerufene Funktion weiss wo (relativ zur aktuellen Position des Stackpointers) sie ihre Argumente findet und kann selber auch weitere Funktionen aufrufen (für welche sie dann wiederum Argumente auf den Stack legt, etc...)
Vorteile in dem Zusammenhang - ich wüsste gerade nicht wie man sowas anders schlau implementiert :D

MfG Peschmä

Öhm :D also ich danke dir für deine nette Antwort aber leider sagt mir das immer noch sehr wenig. Ich raffe nicht was die genaue Funktion davon sein soll.

Also ich habe die Zahlen 1,2,3,4 und die will ich auf dem Stack ablegen und dann wieder runterholen. Aber warum ??? Ich meine wenn ich ein Array anlege und die darin ablege und dann das rückwerts auslese habe ich daselbe in Grün :D. was mach einen Stack so besonders das man sich die Mühe macht in einen Funktions wirrwar sowas zu implementieren.

Ich weiß einfach nicht wie ich mein Problem anders beschreiben sollte. :(

Sonst vielleicht schildert mir mal jemand den Ablauf eines solchen Stacks und ich sage dann wo es bei mir hakt.

Vielleicht sollte man explizit dazu sagen, push und pop sind, zumindest bei den allermeissten Systemen, Funktionen die der Prozessor direkt ausführen kann. D. h. ich kann dem Prozessor direkt einen Befehl geben etwas aus einem Register auf den Stack zu pushen bzw. von diesem in eines zu popen.

Wo der Vorteil daran liegt wird dir vielleicht klar, wenn du mal folgende zwei Aufgaben miteinander vergleichst:

1. Schreibe ein Programm, das beliebig viele skalare Werte abspeichern und wieder ausgeben kann. Ein Wert der dem Programm übergeben wird soll dabei als letztes an eine Liste angehängt werden. Wird ein Wert wieder angefordert, so reicht es aus den letzten Wert der Liste zurückzugeben und diesen von der Liste zu entfernen.

2. Schreibe ein Programm, das beliebig viele skalare Werte abspeichern und wieder ausgeben kann. Ein Wert der dem Programm übergeben wird soll dabei wahlfrei an eine beliebige Stelle einer Liste eingefügt werden. Es kann ein Wert an einer wahlfreien Stelle der Liste angefordert werden, welcher zurück zu geben und zu entfernen ist.

(1. enspricht dem Stack)

Wenn du beides mal versuchst zu programmieren, beides kannst du mit Arrays simulieren, wirst du festellen, dass 1. sehr viel einfacher zu machen ist 2..
Schleisslich musst du bei 1. den Array immer nur um eins vergrössern (vgl. Stackpointer inkrementieren) und den Wert hinzufügen, bzw. den letzten Wert lesen, zurückgeben und den Array um eins verkleinern (vgl. Stackpointer dekrementieren) und musst auch keine Adressen auswerten die von aussen rein kommen. Bei 2. Jedoch, müsstest du den Array vergrössern, den entsprechend hinteren Teil nach rechts verschieben und dann deinen Wert an entsprechender Stelle einfügen und vice versa, einen Wert irgendwo aus dem Array heraus auslesen, die entsprechenden Wert recht davon nach links um kopieren und den Array um eins verkürzen. Ausserdem müsstest du die Adresse die du rein bekommst auch immer auf Gültikeit überprüfen, also nicht zu gross, bei 1. hingegen genügt es abzufangen ob der Array ggf. leer ist.

Natürlich gibt es in einigen "höheren" Hochsprachen Funktionen, die auch 2. nicht allzu schwer machen umzusetzten, weil sich der Compiler/ Interpreter selber um das vergrössern/ verkleinern des Arrays und ums Verschieben der Elemente kümmert. Aber wenn dus mal in C ohne irgendwelchen zusätzlichen Bibliotheken ausser den Standard-Libs probierst, wirst du's sehen, da musst dich dann nämlich selber drum kümmern.
Und wenn dir dann noch überlegst, dass du das ganze jetzt ohne Arrays und ohne jegliche Hochsprach, ja noch nicht mal Assembler machen musst, sondern direkt den Prozessor programmieren müsstest, also dir das ganze im Endeffekt als digitale Schaltung überlegen müsstest, wirds vielleicht noch klarer, son Stack ist wesentlich einfacher...

Moin,

ich weiß jetzt nicht, ob die Antworten, die hier bislang schon gegeben wurden, Deine Frage beantwortet haben...

Die bisherigen Antworten bezogen sich auf Implementierungen.
Ich selbst bin Informatikstudent und da gibt es noch eine etwas andere Sichtweise auf solche Konzepte und ich kann ja mal erklären, welche elementaren Probleme ein Stack ursprünglich mal gelöst hat.

Die grundlegende Theorie der Informatik hat mit Turingmaschinen oder DFAs (Deterministic Finite Automata) begonnen, also Maschinen mit einer begrenzten Anzahl von Zuständen und einem ebenso begrenzten Symbolvorrat.
Mit diesen Maschinen ließen sich schon diverse "Probleme" lösen, bzw. - sollte ich vielleicht etwas genauer sagen - "Entscheidungen treffen".

Ich geb mal ein Beispiel:

Wir gehen aus von einem Symbolvorrat von zwei Symbolen, nennen wir sie "a" und "b"
mit einem DFA lässt sich jetzt leicht entscheiden, ob eine eingegebene Zeichenkette zum Beispiel die Bedingung erfüllt "Immer abwechselnd a und b"
Es lassen sich auch kompliziertere Muster mit größerem Zeichenvorrat erkennen und bearbeiten.

Nun gibt es aber auch Probleme, die sich nicht mit einfachen DFAs entscheiden lassen, z.B. lässt sich mit keinem DFA entscheiden "Eine beliebige Anzahl von a's gefolgt von der gleichen Anzahl b's".

In diesem Fall müsste der Automat unendlich viele Zustände haben, dies ist aber durch die Charakteristik "Endlich" (engl. Finite) bereits ausgeschlossen.

Solche Probleme lassen sich mit Hilfe eines Stack lösen, denn mit einem Stack muss nur für jedes eingelesene a ein Symbol auf den Stack gelegt werden und beim Auftauchen des ersten b's wird für jedes b wieder ein a vom Stack genommen. Ergänzt durch eine Fehlerbedingung, dass keine a's mehr auftauchen dürfen, ist das Problem gelöst, bzw. entschieden, denn nur wenn mit dem letzten b auch das letzte a vom Stack entfernt wird, ist die Bedingung erfüllt.

Das dürfte jetzt extrem verkürzt die Entstehungsgeschichte des Stack-Konzepts gewesen sein...

Das klingt jetzt vielleicht ziemlich antiquiert, aber glaub' mir, auch die höchsten Probleme der Informatik werden meistens intern auf derartig simple Probleme heruntergebrochen und mir selbst hat es echt geholfen, sich auch mal mit diesen Grundlagen auseinanderzusetzen und nicht immer nur auf Seite der Hochsprachen zu arbeiten.

Ich hoffe, Du hast davon überhaupt irgendetwas verstanden, eigentlich müsste man das mit Zeichnungen machen, aber das geht hier ja leider nicht ohne größeren Aufwand.

So long,

Liberty

Zusätzliche Ergänzung: Wenn du eine rekursive Funktion schreibst, so wird deren Speichergebrauch intern meist durch einen Stack gelöst, was extrem einfach und effizient ist.

MfG Bischi

Wow das war mal gut :cool:.......... also die Sache wird damit schon um einiges klarer.

@sticky bit
Ja das kling ja mal sehr einleuchtend. Also bedeutet das für meine Problem stellung in der ich einen Stack mit einem Dynamischen Array implementirenn soll, doch folgendes.

Das Stack programm kümmert sich doch eigentlich dann um das dynamische Array.

Also mal im Klartext das sind meine Prototypen:
# Prototypen

int stackInit(stack_size); <- Diese funktion soll doch im bezug auf das Array. Das array erzeugen. Was aber vom ablauf her dann Stack heißt.

int push(Stack_element); <- Diese funktion soll doch dann immer einen Wert in das Array einfügen.

int pop(Stack_element); <- Damit wird immer ein Element wieder aus dem Array genommen.

int empty(); <- prüft ob das Array leer ist.

int full(); <- prüft ob das Array voll ist.

int clear(); <- leert das Array

void stackDelete(); <- löscht das Array

So habe ich das jetzt alles erst mal richtig verstanden?????

@Liberty
Also vielen dank für deine Erklärung mal zum hintergrund der Geschichte ich bin froh das mir das jemand mal so relativ simpel erklären konnte. Es ist ja immer wieder überraschend wie viel man sich doch selber aneigenen muss und wieviel man erklärt bekommt. Ich selber studiere nämlich auch Technische Informatik mit Schwerpunkt Software Entwicklung. Leider hat es bisher noch niemand mal ordentlich geschafft einfach mal den Nutzen eines solchen Stack sauber zu erklären. Was mich daran am meisten aufregt ist das ich ab Januar für solch gloreiche Vorlesungen 648 € bezahlen darf wo ich mich immer noch frage wie ich das machen soll. :rolleyes:

Also erst mal vielen dank an euch Leute

Gruß

Sector

Zitat:

---

Zitat von Sector1379

int pop(Stack_element); <- Damit wird immer ein Element wieder aus dem Array genommen.

---

Ne - eben nicht!

Stack_element pop();

MfG Bischi

PS: Wenn ihr da wirklich so wenig lernt, würd ich mir vielleicht mal überlegen, die Uni zu wechseln...

Zitat:

---

Zitat von bischi

Ne - eben nicht!

Stack_element pop();

MfG Bischi

PS: Wenn ihr da wirklich so wenig lernt, würd ich mir vielleicht mal überlegen, die Uni zu wechseln...

---

Öhm Moment mal. Das habe ich mir nicht ausgedacht das ist die vorgabe von meinem Prof. Da kann ich nichts dran machen das ist das Header file den er vorgibt.

Zitat:

---

Zitat von Sector1379

Öhm Moment mal. Das habe ich mir nicht ausgedacht das ist die vorgabe von meinem Prof. Da kann ich nichts dran machen das ist das Header file den er vorgibt.

---

Ah - stimmt: C...

also etwa so: int pop(Pointer_auf_Stack_element);

wobei du auf das gepoppte Stackelement danach mittels Pointer (oder auch call by reference) zugreifen kannst (ich bin es mir eben gewohnt, dass Rückgabewerte eben auch als solche gekennzeichnet werden :) ).

MfG :D Bischi

Zitat:

---

Zitat von bischi

Ah - stimmt: C...

also etwa so: int pop(Pointer_auf_Stack_element);

wobei du auf das gepoppte Stackelement danach mittels Pointer (oder auch call by reference) zugreifen kannst (ich bin es mir eben gewohnt, dass Rückgabewerte eben auch als solche gekennzeichnet werden :) ).

MfG :D Bischi

---

Exat so sollte es laufen. Kannst du mir sagen ob ich dann alles so erst mal richtig verstanden habe ????? Oder habe ich wieder einen dank Fehler.

Zwei drei Punkte:

- du sprichst immer von Array - wenn du das Ding in einer Funktion erzeugst wird das kein Array sein sondern einfach ein Speicherblock aufm Heap, Arrays in C haben immer eine fixe (d.h. nicht zur Laufzeit bestimmte) Grösse (eventuell hat sich da mit C99 was geändert - aber ich glaube da sind halt auch noch Konstanten als Grössenangaben erlaubt oder so, etc)

- wozu genau haben push() und pop() int-Rückgabewerte? Sind das Fehlermeldemöglichkeiten?

Sonst passt das schon glaub ich. Genau siehst du dann wenn dus implementierst ;)

MfG Peschmä

Zitat:

---

Zitat von peschmae

Zwei drei Punkte:

- du sprichst immer von Array - wenn du das Ding in einer Funktion erzeugst wird das kein Array sein sondern einfach ein Speicherblock aufm Heap, Arrays in C haben immer eine fixe (d.h. nicht zur Laufzeit bestimmte) Grösse (eventuell hat sich da mit C99 was geändert - aber ich glaube da sind halt auch noch Konstanten als Grössenangaben erlaubt oder so, etc)

- wozu genau haben push() und pop() int-Rückgabewerte? Sind das Fehlermeldemöglichkeiten?

Sonst passt das schon glaub ich. Genau siehst du dann wenn dus implementierst ;)

MfG Peschmä

---

Also das mit den Fixen werten verstehe ich jetzt nicht so ganz. Warum gibt es dann denn Dynamische Arrays und ich spreche immer von Array weil ich das mit einem Dynamischen Array lösen soll.