Stapelspeicher

fanaticox64 · Hält's aus hier Beiträge: 5

Hi,
Ich soll für die Schule eine
kurze Andeutung der Implementierung des Stapelspeichers
hervorbringen. Nur weiss ich dummerweise
nicht wie ich diese schreibe.
Über eine kleine Hilfestellung, würde Ich mich riesig freuen

danke im vorraus
fanatico

oldmax · Beiträge: 380 D3 Prof, D4 Prof

Hi
Stell dir vor, du bist furchtbar vergesslich. Wenn du nun eine Arbeit unterbrichst, mußt du dir irgendwo einen Merkzettel hinpappen, was du zuletzt erledigt hast. Früher gab's auf den Schreibtischen ein Brettchen mit einem Nagel drin und jedesmal, wenn ein solcher Merkzettel geschrieben wurde, wurde er einfach auf den Stapel aufgespießt. Damit war der Stapelspeicher des 18.Jahrhunderts erfunden. Nun brauchte man nur immer den obersten Zettel vom Stapel nehmen und konnte mit seiner Arbeit fortfahren (Heute heißt sowas Stack, also auch nix anderes) Nun könntest du ja sagen, das ist unfair, Da wird ja der zuerst abgelegte Zettel zuletzt abgearbeitet. So isses. Eine CPU schreibt z.B. so ihre nächste Adresse für den Befehlscode auf den Stack, bevor sie eine Unterbrechung bearbeitet, um anschließend die ursprüngliche Bearbeitung fortzusetzen. Wenn ich mich richtig eerinnere ist dies ein FiLo ein First in Last Out Stapel. Die ander Variante ist das durchreichen über einen Zwischenspeicher (Druckerspooler) da wird auch die Information auf einen Stapel gepackt, weil die dahinter geschalteten Mechanismen eben langsamer sind, trotzdem muß die Reihenfolge eingehalten werden. Also, ein Rohr, in das man Kugeln schiebt. Die Kugel die zuerst hinein getan wird, fällt auch als erste wieder hinaus und das ist dann FiFi, First in First out.
Ich hoffe, ich habe die beiden jetzt nicht wieder verwechselt...
Gruß oldmax

_________________
Zier dich nich so, ich krieg dich schon....

Gausi · Verfasst: Mo 30.10.06 14:41

oldmax hat folgendes geschrieben:

Die Kugel die zuerst hinein getan wird, fällt auch als erste wieder hinaus und das ist dann FiFi, First in First out.
Ich hoffe, ich habe die beiden jetzt nicht wieder verwechselt...

Bis auf die Tatsache, dass das letztere nicht FiFi, sondern FiFo heißt, ist das wohl so richtig ;-)

Wobei man afaik bei FiFo in der Regel von Queue spricht ("Warteschlange"), und nicht von Stack ("Stapel").

_________________
We are, we were and will not be.

fanaticox64 · Hält's aus hier Beiträge: 5

hi,
erstmal vielen dank für die schnellen Antworten,
aber könnt ihr mir vieleicht auch verraten wie
so ein Delphi Programmieransatz eines Stappelspeichers wäre.
Wenn ihr das hinkriegt wäre alles perfekt

fanatico

Gausi · Verfasst: Mo 30.10.06 16:25

Du willst also den Datenstruktur eines Stacks selber programmieren?

Das ist nicht wirklich schwierig. Hast du schonmal eine (doppelt) verkettete Liste geschrieben? Ein Stack geht fast noch einfacher. Mal aus dem Kopf umgangssprachlich, ohne Garantie auf Richtigkeit und/oder Vollständigkeit:

Ein Stack kann beliebig viele Elemente eines Datentyps aufnehmen. Was das für Daten sind, ist prinzipiell egal. Wichtig ist nur, dass der Datentyp ein Feld "Next" hat, der ein Zeiger auf eben diesen Datentyp ist. In diesem Zeiger wird das nächste Element auf dem Stack gespeichert.
Der Stack besteht dann im Wesentlichen aus einem Zeiger "Top", sowie den Methoden "Push" und "Pop". Push fügt ein Element ein, in dem der Zeiger des Elements (NewElement.Next) auf Stack.Top gesetzt wird (d.h. der Nachfolger des neuen Elements ist die alte Spitze des Stacks), und anschließend Stack.Top auf das neue Element gesetzt wird (da dies die neue Spitze bildet).
Pop entfernt das oberste Element, indem Stack.Top auf Stack.Top.Next gesetzt wird.

Ich bin mir ziemlich sicher, dass es irgendwo hier im Forum ein Tutorial zu Pointern gibt, wo das Beispiel einer verketteten Liste behandelt wird. Da musst du eigentlich nur ein paar Sachen draus löschen, und du hast deinen Stack ;-)

_________________
We are, we were and will not be.

oldmax · Beiträge: 380 D3 Prof, D4 Prof

Hi
FiFi... ?! Logisch FiFo. :oops:

Ach hab ich heut wieder ungehorsame Fingers.

Ok, das wär geklärt und das mit der queue auch. Nun aber zu deiner Hausaufgabe... meinst du nicht, es wär nun ein ganz klein bischen Eigenleistung fällig ? :wink:

Das mit der verketteten Liste hab ich auch schon gelesen, also, wenn du schon nix selber machen willst, dann benutz wenigstens die Suchmaschine... :!:

Ich mein, wir kriegen so'n Ding programmiert, keine Frage, aber du hast dich schließlich irgendwie dazu durchgerungen, die Sprache zu lernen und vom Abkupfern, hmmm, da lernst du nix. :mahn:

Gruß oldmax

_________________
Zier dich nich so, ich krieg dich schon....

Ehemaliges Mitglied Erhaltene Danke: 1

nur mal zur info, 'n stack ist 'n lifo ;-)

hat ja auch schon oldmax so skizziert, mit seinem notizzettelbeispiel... da bitte nachlesen :-)

delfiphan · Beiträge: 2684 Erhaltene Danke: 32

Ein Stack wird üblicherweise so implementiert, dass man einfach mal Speicher alloziert und einen Pointer auf den Anfang des Speicherblocks setzt. Um zu Pushen schreibt man den Wert und erhöht anschliessend den Zeiger. Für Pop genau umgekehrt: Der Pointer wird zuerst runtergesetzt, dann der Wert gelesen.

Manchmal ist die Adressierung auch umgekehrt (z.B. push/pop in asm): Bei einem leeren Stapel zeigt hier der SP (Stack Pointer) aufs Ende des Speicherblocks und beim Push wird dieser dekrementiert und beim Pop inkrementiert. Der Vorteil dieser verkehrten Adressierung besteht hier darin, dass man beim Pushen zuerst die Adresse verändert und dann den Wert schreibt. Daraus folgt, dass der Stackpointer immer auf das zuletzt gepushte "Objekt" zeigt. Bei der ersten Möglichkeit ist dies nicht der Fall: Der Stackpointer zeigt dort immer auf die nächste freie Speicheradresse (mit eventuellem Datenmüll).

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:

var
 P: ^Integer;
begin
  GetMem(P, 1000); // Speicher allozieren
  // push(1)
  P^ := 1;
  inc(P);
  // push(2)
  P^ := 2;
  inc(P);
  // push(3)
  P^ := 3;
  inc(P);
  // pop
  dec(P);
  ShowMessage(inttostr(P^)); // 3
  // pop
  dec(P);
  ShowMessage(inttostr(P^)); // 2
  // pop
  dec(P);
  ShowMessage(inttostr(P^)); // 1
  FreeMem(P);
end;

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme