Data Structure - Stack - OOP

Share your advanced PureBasic knowledge/code with the community.
User avatar
StarBootics
Addict
Addict
Posts: 984
Joined: Sun Jul 07, 2013 11:35 am
Location: Canada

Data Structure - Stack - OOP

Post by StarBootics »

Hello everyone,

Before I start, I want to clarify something : YES A STACK DATA STRUCTURE CAN BE DONE WITH STANDARD PB LINKED LIST.

There a prototype of a Stack data structure implementation. See the source code for the YouTube link about where the inspiration came from.

Best regards
StarBootics

Code: Select all

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; Project name : Data Structure - Stack
; File Name : Stack - OOP.pb
; File version: 1.0.0
; Programming : Prototype
; Programmed by : StarBootics
; Date : June 9th, 2021
; Last Update : June 9th, 2021
; PureBasic code : V5.73 LTS
; Platform : Windows, Linux, MacOS X
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; Based on the code presented by the YouTube channel
;
; https://www.youtube.com/channel/UC8butISFwT-Wl7EV0hUK0BQ
; Video link : https://www.youtube.com/watch?v=B31LgI4Y4DQ
; Video name : Data Structures - Full Course Using C And C++
;
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

DeclareModule Stack
  
  Interface Stack
    
    Push(Value.l)
    Pop()
    Top.l()
    IsEmpty.b()
    Free()
    
  EndInterface
  
  Declare.i New()
  
EndDeclareModule

Module Stack
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< Structures declaration <<<<<
  
  Structure Node
    
    Value.l
    *Link.Node
    
  EndStructure
  
  Structure Private_Members
    
    VirtualTable.i
    *Top.Node
    
  EndStructure
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< The Push operator <<<<<
  
  Procedure Push(*This.Private_Members, Value.l)
    
    *Temp.Node = AllocateStructure(Node)
    *Temp\Value = Value
    *Temp\Link = *This\Top
    *This\Top = *Temp
    
  EndProcedure
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< The Pop operator <<<<<
  
  Procedure Pop(*This.Private_Members)
    
    If *This\Top = #Null
      ; MessageRequester("Stack Error", "The Stack is already Empty !")
      ProcedureReturn 0
    EndIf
    
    *Temp.Node = *This\Top
    *This\Top = *This\Top\Link
    FreeStructure(*Temp)

  EndProcedure
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< The Top operator <<<<<
  
  Procedure.l Top(*This.Private_Members)
    
    If *This\Top <> #Null
      ProcedureReturn *This\Top\Value
    Else
      MessageRequester("Stack Error", "The Stack is Empty !")
    EndIf
    
  EndProcedure
 
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< The IsEmpty operator <<<<<
  
  Procedure.b IsEmpty(*This.Private_Members)
    
    If *This\Top = #Null
      ProcedureReturn #True
    Else
      ProcedureReturn #False
    EndIf
    
  EndProcedure
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< The Destructor <<<<<

  Procedure Free(*This.Private_Members)
    
    While IsEmpty(*This) <> #True
      Pop(*This)
    Wend
    
    FreeStructure(*This)
    
  EndProcedure
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< The Constructor <<<<<

  Procedure.i New()
    
    *This.Private_Members = AllocateStructure(Private_Members)
    *This\VirtualTable = ?START_METHODS
    
    *This\Top = #Null
    
    ProcedureReturn *This
  EndProcedure
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< The VirtualTable entries <<<<<

  DataSection
    START_METHODS:
    Data.i @Push()
    Data.i @Pop()
    Data.i @Top()
    Data.i @IsEmpty()
    Data.i @Free()
    END_METHODS:
  EndDataSection
  
EndModule

CompilerIf #PB_Compiler_IsMainFile
  
  MyStack.Stack::Stack = Stack::New()
  
  MyStack\Push(25)
  MyStack\Push(20)
  MyStack\Push(15)
  
  While MyStack\IsEmpty() <> #True
    
    Debug MyStack\Top()
    MyStack\Pop()
    
  Wend  
  
  MyStack\Free()
  
CompilerEndIf

; <<<<<<<<<<<<<<<<<<<<<<<
; <<<<< END OF FILE <<<<<
; <<<<<<<<<<<<<<<<<<<<<<<
The Stone Age did not end due to a shortage of stones !
GPI
PureBasic Expert
PureBasic Expert
Posts: 1394
Joined: Fri Apr 25, 2003 6:41 pm

Re: Data Structure - Stack - OOP

Post by GPI »

Small tip: When you use Integers instead of longs, you can Store a Pointer in your struckture and with a pointer you could store everything.
User avatar
StarBootics
Addict
Addict
Posts: 984
Joined: Sun Jul 07, 2013 11:35 am
Location: Canada

Re: Data Structure - Stack - OOP

Post by StarBootics »

Hello everyone,

This is the version 2.0.0 of a Stack data structure specifically design to hold element of different type in this case Allocated Structures but it can be object created with Dev-Object.

If the stack contain identical objects created with Dev-Object for example you have to specify the address of the destructor in the stack constructor. If the stack contain different objects you have to specify the address of the destructor when you push element on the stack. If the destructor are not specified the Pop method will consider a simple FreeStructure is safe to do.

Best regards
StarBootics

Code: Select all

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; Project name : Data Structure - Stack
; File Name : Stack - OOP.pb
; File version: 2.0.0
; Programming : OK
; Programmed by : StarBootics
; Date : June 9th, 2021
; Last Update : June 9th, 2021
; PureBasic code : V5.73 LTS
; Platform : Windows, Linux, MacOS X
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

DeclareModule Stack
  
  Interface Stack
    
    Push(Tag.l, *ObjectPtr, *ObjectDestructor = #Null)
    Pop()
    TopTag.l()
    TopObjectPtr.i()
    IsEmpty.b()
    Free()
    
  EndInterface
  
  Declare.i New(*ObjectDestructor = #Null)
  
EndDeclareModule

Module Stack
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< Structures declaration <<<<<
  
  Structure Node
    
    Tag.l
    ObjectPtr.i
    ObjectDestructor.i
    *Link.Node
    
  EndStructure
  
  Structure Private_Members
    
    VirtualTable.i
    ObjectDestructor.i
    *Top.Node
    
  EndStructure
  
  Prototype DestructorFunction(*ObjectPtr)
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< The Push Operator <<<<<
  
  Procedure Push(*This.Private_Members, Tag.l, *ObjectPtr, *ObjectDestructor = #Null)
    
    *Temp.Node = AllocateStructure(Node)
    *Temp\Tag = Tag
    *Temp\ObjectPtr = *ObjectPtr
    *Temp\ObjectDestructor = *ObjectDestructor
    *Temp\Link = *This\Top
    *This\Top = *Temp
    
  EndProcedure
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< The Pop operator <<<<<
  
  Procedure Pop(*This.Private_Members)
    
    If *This\Top = #Null
      ; MessageRequester("Stack Error", "The Stack is already Empty !")
      ProcedureReturn 0
    EndIf
    
    *Temp.Node = *This\Top
    
    If *Temp\ObjectDestructor <> #Null
      Destructor.DestructorFunction = *Temp\ObjectDestructor
      Destructor(*Temp\ObjectPtr)
    ElseIf *This\ObjectDestructor <> #Null
      Destructor.DestructorFunction = *This\ObjectDestructor
      Destructor(*Temp\ObjectPtr)
    Else
      FreeStructure(*Temp\ObjectPtr)
    EndIf
    
    *This\Top = *This\Top\Link
    FreeStructure(*Temp)

  EndProcedure
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< The TopTag operator <<<<<
  
  Procedure.l TopTag(*This.Private_Members)
    
    If *This\Top <> #Null
      ProcedureReturn *This\Top\Tag
    Else
      MessageRequester("Stack Error", "The Stack is Empty !")
    EndIf
    
  EndProcedure
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< The TopObjectPtr <<<<<
  
  Procedure.i TopObjectPtr(*This.Private_Members)
    
    If *This\Top <> #Null
      ProcedureReturn *This\Top\ObjectPtr
    Else
      MessageRequester("Stack Error", "The Stack is Empty !")
    EndIf
    
  EndProcedure
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< The IsEmpty operator <<<<<
  
  Procedure.b IsEmpty(*This.Private_Members)
    
    If *This\Top = #Null
      ProcedureReturn #True
    Else
      ProcedureReturn #False
    EndIf
    
  EndProcedure
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< The Destructor <<<<<

  Procedure Free(*This.Private_Members)
    
    While IsEmpty(*This) <> #True
      Pop(*This)
    Wend
    
    FreeStructure(*This)
    
  EndProcedure
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< The Constructor <<<<<

  Procedure.i New(*ObjectDestructor = #Null)
    
    *This.Private_Members = AllocateStructure(Private_Members)
    *This\VirtualTable = ?START_METHODS
    
    *This\Top = #Null
    *This\ObjectDestructor = *ObjectDestructor
    
    ProcedureReturn *This
  EndProcedure
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< Virtual table entries <<<<<

  DataSection
    START_METHODS:
    Data.i @Push()
    Data.i @Pop()
    Data.i @TopTag()
    Data.i @TopObjectPtr()
    Data.i @IsEmpty()
    Data.i @Free()
    END_METHODS:
  EndDataSection
  
EndModule

CompilerIf #PB_Compiler_IsMainFile
  
  Enumeration 
    #TAG_DODECAHEDRON
    #TAG_SPHERE
    #TAG_CUBE
    #TAG_PYRAMID
  EndEnumeration
  
  Structure Dodecahedron
    
    Volume.d
    Size.d
    Whatever.s
    
  EndStructure
  
  Structure Sphere
    
    Volume.d
    Radius.d
    Whatever.s
    
  EndStructure
  
  Structure Cube
    
    Volume.d
    Size.d
    Whatever.s
    
  EndStructure
  
  Structure Pyramid
    
    Volume.d
    Size.d
    Whatever.s
    
  EndStructure
  
  MyStack.Stack::Stack = Stack::New(#Null)
  
  MyStack\Push(#TAG_PYRAMID, AllocateStructure(Pyramid), #Null)
  MyStack\Push(#TAG_SPHERE, AllocateStructure(Sphere), #Null)
  MyStack\Push(#TAG_CUBE, AllocateStructure(Cube), #Null)
  MyStack\Push(#TAG_SPHERE, AllocateStructure(Sphere), #Null)
  MyStack\Push(#TAG_DODECAHEDRON, AllocateStructure(Dodecahedron), #Null)
  MyStack\Push(#TAG_PYRAMID, AllocateStructure(Pyramid), #Null)
  
  While MyStack\IsEmpty() <> #True
    
    Select MyStack\TopTag()
        
      Case #TAG_DODECAHEDRON
        *Dodecahedron.Dodecahedron = MyStack\TopObjectPtr()
        Debug "In the stack there is a Dodecahedron"
        
      Case #TAG_SPHERE
        *Sphere.Sphere = MyStack\TopObjectPtr()
        Debug "In the stack there is a Sphere"  
        
      Case #TAG_CUBE
        *Cube.Cube = MyStack\TopObjectPtr()
        Debug "In the stack there is a Cube" 
        
      Case #TAG_PYRAMID 
        *Pyramid.Pyramid = MyStack\TopObjectPtr()
        Debug "In the stack there is a Pyramid" 
        
    EndSelect

    MyStack\Pop()
    
  Wend  
  
  MyStack\Free()
  
CompilerEndIf

; <<<<<<<<<<<<<<<<<<<<<<<
; <<<<< END OF FILE <<<<<
; <<<<<<<<<<<<<<<<<<<<<<<
The Stone Age did not end due to a shortage of stones !
GPI
PureBasic Expert
PureBasic Expert
Posts: 1394
Joined: Fri Apr 25, 2003 6:41 pm

Re: Data Structure - Stack - OOP

Post by GPI »

my implantation:

Code: Select all

DeclareModule Stack
  EnableExplicit
  Interface object
    free()
    pushb(value.b)
    pushw(value.w)
    pushl(value.l)
    pushq(value.q)
    pushf(value.f)
    pushd(value.d)
    pushi(value.i)
    popb.b()
    popw.w()
    popl.l()
    popq.q()
    popf.f()
    popd.d()
    popi.i()
  EndInterface
  Declare.i new(size.q=1000)
EndDeclareModule

Module stack
  Structure combi
    StructureUnion
      b.b
      w.w
      l.l
      q.q
      f.f
      d.d
      i.i
    EndStructureUnion
  EndStructure
  
  Structure sobject
    *vt
    *start.combi
    *end.combi
    *current.combi
  EndStructure  
  
  Procedure.i new(size.q=1000)
    Protected.sobject *ret= AllocateStructure(sobject)
    *ret\vt = ?vt
    *ret\start = AllocateMemory(size)
    *ret\end = *ret\start + size
    *ret\current = *ret\end
    ProcedureReturn *ret
  EndProcedure
  Procedure free(*obj.sobject)
    FreeMemory(*obj\start)
    *obj\start = #Null
    *obj\end = #Null
    *obj\current = #Null
    *obj\vt = #Null
    FreeStructure (*obj)
  EndProcedure
  
  Procedure pushb(*obj.sobject, value.b)
    *obj\current - SizeOf(byte)
    If *obj\current < *obj\start
      Debug "STACK OVERFLOW!"
      End
    EndIf
    *obj\current\b = value
  EndProcedure
  Procedure.b popb(*obj.sobject)
    Protected.b ret = *obj\current\b
    *obj\current + SizeOf(byte)
    If *obj\current > *obj\end
      Debug "STACK UNDERFLOW!"
      End
    EndIf
    ProcedureReturn ret
  EndProcedure
  
  Procedure pushw(*obj.sobject, value.w)
    *obj\current - SizeOf(word)
    If *obj\current < *obj\start
      Debug "STACK OVERFLOW!"
      End
    EndIf
    *obj\current\w = value
  EndProcedure
  Procedure.w popw(*obj.sobject)
    Protected.w ret = *obj\current\w
    *obj\current + SizeOf(word)
    If *obj\current > *obj\end
      Debug "STACK UNDERFLOW!"
      End
    EndIf
    ProcedureReturn ret
  EndProcedure
  
  Procedure pushl(*obj.sobject, value.l)
    *obj\current - SizeOf(long)
    If *obj\current < *obj\start
      Debug "STACK OVERFLOW!"
      End
    EndIf
    *obj\current\l = value
  EndProcedure
  Procedure.l popl(*obj.sobject)
    Protected.l ret = *obj\current\l
    *obj\current + SizeOf(long)
    If *obj\current > *obj\end
      Debug "STACK UNDERFLOW!"
      End
    EndIf
    ProcedureReturn ret
  EndProcedure
  
  Procedure pushq(*obj.sobject, value.q)
    *obj\current - SizeOf(quad)
    If *obj\current < *obj\start
      Debug "STACK OVERFLOW!"
      End
    EndIf
    *obj\current\q = value
  EndProcedure
  Procedure.q popq(*obj.sobject)
    Protected.q ret = *obj\current\q
    *obj\current + SizeOf(quad)
    If *obj\current > *obj\end
      Debug "STACK UNDERFLOW!"
      End
    EndIf
    ProcedureReturn ret
  EndProcedure
  
  Procedure pushf(*obj.sobject, value.f)
    *obj\current - SizeOf(float)
    If *obj\current < *obj\start
      Debug "STACK OVERFLOW!"
      End
    EndIf
    *obj\current\f = value
  EndProcedure
  Procedure.f popf(*obj.sobject)
    Protected.f ret = *obj\current\f
    *obj\current + SizeOf(float)
    If *obj\current > *obj\end
      Debug "STACK UNDERFLOW!"
      End
    EndIf
    ProcedureReturn ret
  EndProcedure
  
  Procedure pushd(*obj.sobject, value.d)
    *obj\current - SizeOf(double)
    If *obj\current < *obj\start
      Debug "STACK OVERFLOW!"
      End
    EndIf
    *obj\current\d = value
  EndProcedure
  Procedure.d popd(*obj.sobject)
    Protected.d ret = *obj\current\d
    *obj\current + SizeOf(double)
    If *obj\current > *obj\end
      Debug "STACK UNDERFLOW!"
      End
    EndIf
    ProcedureReturn ret
  EndProcedure
  
  Procedure pushi(*obj.sobject, value.i)
    *obj\current - SizeOf(integer)
    If *obj\current < *obj\start
      Debug "STACK OVERFLOW!"
      End
    EndIf
    *obj\current\i = value
  EndProcedure
  Procedure.i popi(*obj.sobject)
    Protected.i ret = *obj\current\i
    *obj\current + SizeOf(integer)
    If *obj\current > *obj\end
      Debug "STACK UNDERFLOW!"
      End
    EndIf
    ProcedureReturn ret
  EndProcedure
  
  
  DataSection
    vt:
    Data.i @free()
    Data.i @pushb(), @pushw(), @pushl(), @pushq(), @pushf(), @pushd(), @pushi()
    Data.i @popb(), @popw(), @popl(), @popq(), @popf(), @popd(), @popi()
  EndDataSection
EndModule


*demo.stack::object = stack::new(1000) ; 1000 byte stack

*demo\pushb(10)
*demo\pushw(20)
*demo\pushl(30)
*demo\pushi(40)

Debug *demo\popi()
Debug *demo\popl()
Debug *demo\popw()
Debug *demo\popb()

; absolut legal: 
*demo\pushl($12345678)
Debug Hex(*demo\popw()); 5678
Debug Hex(*demo\popw()); 1234
it should be more like a stack the CPU use. It is a big memory you fill "backward". It doesn't care about what your data push it to the stack. It can underrun (read more object than pushed) and overflow (push to many objects).
A Stack is a "first in, last out" memory, like a staple plates, you must take of the top plates before you can get a lower plate.
You must take care about the order or you get a currupted stack.

A CPU uses this for example to store the return adress when you jump to a subroutine.
User avatar
StarBootics
Addict
Addict
Posts: 984
Joined: Sun Jul 07, 2013 11:35 am
Location: Canada

Re: Data Structure - Stack - OOP

Post by StarBootics »

Hello GPI,

Your approach as it's uses but let's say you want to check if the opening brackets of an expression match the closing ones. You can do it with a "Stack" of string for example.

Another uses for "Stack" is when you want to implement an Undo functionality in your program, Depending on what your program is doing a Stack like the version 2.0.0 I have shown will be probably needed.

Best regards
StarBootics
The Stone Age did not end due to a shortage of stones !
Post Reply