Push Pop FILO

[freedimension]

Mal was einfaches zur Abwechslung, aber vielleicht kann's ja jemand brauchen.

Code: Alles auswählen

Structure Stack
  memPtr.l
  *curPtr.LONG
EndStructure
Global stack.Stack
Procedure StackInit(size.l)
  If stack\memPtr
    FreeMemory(stack\memPtr)
  EndIf
  stack\memPtr = AllocateMemory(size * 4)
  stack\curPtr = stack\memPtr
EndProcedure
Procedure StackPop()
  stack\curPtr - 4
  ProcedureReturn stack\curPtr\l
EndProcedure
Procedure StackGet()
  ProcedureReturn stack\curPtr\l
EndProcedure
Procedure StackPush(val.l)
  stack\curPtr\l = val
  stack\curPtr + 4
EndProcedure
Procedure StackFree()
  If stack\memPtr
    FreeMemory(stack\memPtr)
  EndIf
EndProcedure

Sollte eigentlich selbsterklärend sein

[freedimension]

Habe das ganze mal etwas verfeinert

Code: Alles auswählen

Structure Stack
  memPtr.l
  *curPtr.LONG
EndStructure

;Damit wird ein Stack angelegt. size.l gibt die Anzahl der ablegbaren Integerwerte an
Procedure StackInit(size.l)
  *x.Stack = AllocateMemory(SizeOf(Stack))
  *x\memPtr = AllocateMemory(size * 4)
  *x\curPtr = *x\memPtr
  ProcedureReturn *x
EndProcedure

;holt den letzten Wert des Stacks und löscht ihn
Procedure StackPop(*stack.Stack)
  *stack\curPtr - 4
  ProcedureReturn *stack\curPtr\l
EndProcedure

;ermittelt den letzten Wert des Stacks ohne ihn jedoch zu löschen
Procedure StackGet(*stack.Stack)
  ProcedureReturn *stack\curPtr\l
EndProcedure

;Legt einen Wert auf dem Stack ab
Procedure StackPush(*stack.Stack, val.l)
  *stack\curPtr\l = val
  *stack\curPtr + 4
EndProcedure

;gibt die Resourcen eines Stacks wieder frei
Procedure StackFree(*stack.Stack)
  If *stack\memPtr
    FreeMemory(*stack\memPtr)
    FreeMemory(*stack)
  EndIf
EndProcedure

 ;überprüft ob noch Werte im Stack vorhanden sind
Procedure StackIsEmpty(*stack.Stack)
  If *stack\memPtr = *stack\curPtr
    ProcedureReturn #True
  EndIf
  ProcedureReturn #False
EndProcedure

; Beispiel
*a.Stack = StackInit(50)
*b.Stack = StackInit(50)
StackPush(*a, 12)
StackPush(*a, 23)
StackPush(*b, 67)
Debug StackPop(*a)
Debug StackPop(*b)
StackPush(*a, 42)
Debug StackPop(*a)
Debug StackPop(*a)

Ihr dürft das ruhig noch etwas optimieren und hier dann posten

[Robert Wünsche]

So, und noch eine Etwas andere Art, die auf direkterem Aufruf bassiert:

Code: Alles auswählen

;warscheinlich schnelleres stack:

;der stack wird automatisch erweitert !

#stack_erweiter = 40 ; schrittgröße zum erweitern (in Byte)
#stack_anfang   = 40 ; die anfängliche Stackgröße (in Byte)

;Linkedlist für den Stackmanager:
Structure Stack
  adresse.l
  grosse.l           ;in Variablen !
  inhalt.l           ;ist der tatsächliche inhalt des stackes (in variablen)
EndStructure
NewList Stack.Stack()

;stack muss nur initialisiert werden !
;der stackpointer wird zurückgegeben !
;wenn 0 --> fehlgeschlagen !
Procedure Stack_init()
  speicher = AllocateMemory(#stack_anfang) 
  If speicher = 0
    ProcedureReturn 0
  EndIf
  
  LastElement(Stack())
  AddElement(Stack())
  Stack()\adresse = speicher
  Stack()\grosse  = #stack_anfang / 4
  ProcedureReturn ListIndex(Stack())  
EndProcedure

;"Pushen"
;wenns fehlschlägt --> 0 !
;anderenfalls 1
Procedure Stack_Push(p_wert.l,p_stack)
  SelectElement(Stack(),p_stack)
  ;überprüfe, ob der inhalt beinahe überläuft:
  If Stack()\inhalt >= Stack()\grosse - 1
    ;erweitern:
    adresse = ReAllocateMemory(Stack()\adresse, (Stack()\grosse * 4)+#stack_erweiter)

    If adresse = 0
      ProcedureReturn 0
    EndIf
    
    Stack()\adresse = adresse
    Stack()\grosse = Stack()\grosse + (#stack_erweiter / 4)
  EndIf
  
  Stack()\inhalt = Stack()\inhalt + 1
  
  ;daten schreiben:
  PokeL(Stack()\adresse + (((Stack()\inhalt+1) * 4) - 4),p_wert)
EndProcedure

;"Popen"
Procedure Stack_Pop(p_stack)
  SelectElement(Stack(),p_stack)
  
  wert = PeekL(Stack()\adresse + ((Stack()\inhalt+1) * 4 - 4))
  Stack()\inhalt = Stack()\inhalt - 1
  If Stack()\inhalt = -1
    Stack()\inhalt = 0
    ProcedureReturn 0
  EndIf
  ProcedureReturn wert
EndProcedure

End

Ganz wichtig, das END nicht vergessen !

Der stack wird zur not automatisch erweitert !

[freedimension]

Zwei Anmerkungen:
1. Wo genau siehst du Geschwindigkeitsvorteile deiner Variante?
2. Ich habe bewusst auf LinkedLists verzichtet

[Robert Wünsche]

Ach shit , deine variante ist 4 Mal schneller !
Aber ich denke, dass meine Flexibler ist (man achte besonders darauf, das man stacks in stacks bauen kann), wozu das gut sein soll, weiß ich auch nicht.
Und ja, meins erweitert den Speicher automatisch !
Man kann auch belibig viele stacks anlegen
Gut, dein's ist schneller, aber meins ein Krümelchen Praktischer ?

[freedimension]

Meine Version ist halt für Fälle ausgelegt, in denen bekannt ist wieviele Werte maximal abgelegt werden, also z.B. beim Parsen eines Stringes wofür ich das dann auch benötige.
Ich könnte jetzt hingehen und meine Variante genauso flexibel machen wie deine (aber ohne LL), würde dadurch dann aber halt auch Geschwindigkeit verlieren. Deswegen fehlen ja auch Sicherheitsabfragen und alles. Es funktioniert wenn man weiß was man tut.

[Robert Wünsche]

So, jetzt ist sie "etwas" schneller !

Code: Alles auswählen

;stack:
; größe | inhalt |  1 | 2 | ...

#stack_startgrosse = 200
#stack_erweiterung = 100

Procedure Init_stack()
  adresse = AllocateMemory(#stack_startgrosse)
  ;anfangsgröße schreiben:
  If adresse <> 0
    PokeL(adresse,#stack_startgrosse + 8)
  EndIf
  ProcedureReturn adresse
EndProcedure

Procedure push_stack(p_adresse,p_wert)
  grosse = PeekL(p_adresse)
  inhalt = PeekL(p_adresse + 4)
  If inhalt + 8 >= grosse/4
    adresse = ReAllocateMemory(p_adresse,grosse + #stack_erweiterung)
    PokeL(adresse,grosse + #stack_erweiterung)
    p_adresse = adresse
  EndIf
  inhalt + 1
  PokeL(p_adresse + 4,inhalt)
  PokeL(p_adresse + 8 + inhalt<<2,p_wert)
  ProcedureReturn p_adresse
EndProcedure

Procedure pop_stack(p_adresse)
  ;anzahl auslesen:
  inhalt = PeekL(p_adresse + 4)
  If inhalt < 1
    ProcedureReturn 0
  EndIf
  wert = PeekL(p_adresse + 8 + inhalt<<2)
  inhalt - 1
  PokeL(p_adresse + 4,inhalt)
  ProcedureReturn wert
EndProcedure

Procedure read_stack(p_adresse,p_position)
  grosse = PeekL(p_adresse)
  If p_position > grosse
    ProcedureReturn 0
  EndIf
  
  ProcedureReturn PeekL(p_adresse + 8 + p_position<<2)
EndProcedure

Procedure free_stack(p_adresse)
  FreeMemory(p_adresse)  
EndProcedure

End

[Kiffi]

> also z.B. beim Parsen eines Stringes wofür ich das dann auch benötige.

kannst Du bitte ein kurzes praktisches Anwendungsbeispiel posten?
Ich würde mal gerne sehen, wie Dein Code verwendet wird.

Vielen Dank im voraus & Grüße ... Kiffi