PureBasic Forums - English

Posted: **Wed Jun 09, 2021 9:08 pm**

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

There a prototype of a Queue 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 - Queue
; File Name : Queue - 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 Queue
  
  Interface Queue
    
    Enqueue(Value.l)
    Dequeue()
    Front.l()
    IsEmpty.b()
    Free()
    
  EndInterface
  
  Declare.i New()
  
EndDeclareModule

Module Queue
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< Structures declaration <<<<<
  
  Structure Node
    
    Value.l
    *Link.Node
    
  EndStructure
  
  Structure Private_Members
    
    VirtualTable.i
    *Front.Node
    *Rear.Node
    
  EndStructure
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< The Enqueue operator <<<<<
  
  Procedure Enqueue(*This.Private_Members, Value.l)
    
    *Temp.Node = AllocateStructure(Node)
    *Temp\Value = Value
    *Temp\Link = #Null
    
    If *This\Front = #Null And *This\Rear = #Null
      *This\Front = *Temp
      *This\Rear = *Temp
      ProcedureReturn 0
    EndIf
    
    *This\Rear\Link = *Temp
    *This\Rear = *Temp
    
  EndProcedure
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< The Dequeue operator <<<<<
  
  Procedure Dequeue(*This.Private_Members)
    
    *Temp.Node = *This\Front
    
    If *This\Front = #Null
      ; MessageRequester("Queue Error", "The Queue is already Empty !")
      ProcedureReturn 0
    EndIf
    
    If *This\Front = *This\Rear
      *This\Front = #Null
      *This\Rear = #Null
    Else
      *This\Front = *This\Front\Link
    EndIf
    
    FreeStructure(*Temp)
    
  EndProcedure
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< The Front operator <<<<<
  
  Procedure.l Front(*This.Private_Members)
    
    If *This\Front <> #Null
      ProcedureReturn *This\Front\Value
    Else
      MessageRequester("Queue Error", "The Queue is Empty !")
    EndIf
    
  EndProcedure
 
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< The IsEmpty operator <<<<<
  
  Procedure.b IsEmpty(*This.Private_Members)
    
    If *This\Front = #Null
      ProcedureReturn #True
    Else
      ProcedureReturn #False
    EndIf
    
  EndProcedure
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< The Destructor <<<<<

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

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

  DataSection
    START_METHODS:
    Data.i @Enqueue()
    Data.i @Dequeue()
    Data.i @Front()
    Data.i @IsEmpty()
    Data.i @Free()
    END_METHODS:
  EndDataSection
  
EndModule

CompilerIf #PB_Compiler_IsMainFile
  
  MyQueue.Queue::Queue = Queue::New()
  
  MyQueue\Enqueue(25)
  MyQueue\Enqueue(35)
  MyQueue\Enqueue(15)
  MyQueue\Enqueue(45)
  
  While MyQueue\IsEmpty() <> #True
    
    Debug MyQueue\Front()
    MyQueue\Dequeue()
    
  Wend
  
  MyQueue\Free()
  
CompilerEndIf

; <<<<<<<<<<<<<<<<<<<<<<<
; <<<<< END OF FILE <<<<<
; <<<<<<<<<<<<<<<<<<<<<<<

Posted: **Thu Jun 10, 2021 4:43 am**

Hello everyone,

This is the version 2.0.0 of a Queue 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 Queue contain identical objects created with Dev-Object for example you have to specify the address of the destructor in the Queue constructor. If the Queue contain different objects you have to specify the address of the destructor when you Enqueue element in the Queue. If the destructor are not specified the Dequeue method will consider a simple FreeStructure is safe to do.

Best regards
StarBootics

Code: Select all

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; Project name : Data Structure - Queue
; File Name : Queue - 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 Queue
  
  Interface Queue
    
    Enqueue(Tag.l, *ObjectPtr, *ObjectDestructor = #Null)
    Dequeue()
    FrontTag.l()
    FrontObjectPtr.i()
    IsEmpty.b()
    Free()
    
  EndInterface
  
  Declare.i New(*ObjectDestructor = #Null)
  
EndDeclareModule

Module Queue
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< Structures declaration <<<<<
  
  Structure Node
    
    Tag.l
    ObjectPtr.i
    ObjectDestructor.i
    *Link.Node
    
  EndStructure
  
  Structure Private_Members
    
    VirtualTable.i
    ObjectDestructor.i
    *Front.Node
    *Rear.Node
    
  EndStructure
  
  Prototype DestructorFunction(*ObjectPtr)
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< The Enqueue operator <<<<<
  
  Procedure Enqueue(*This.Private_Members, Tag.l, *ObjectPtr, *ObjectDestructor = #Null)
    
    *Temp.Node = AllocateStructure(Node)
    *Temp\Tag = Tag
    *Temp\ObjectPtr = *ObjectPtr
    *Temp\ObjectDestructor = *ObjectDestructor
    *Temp\Link = #Null
    
    If *This\Front = #Null And *This\Rear = #Null
      *This\Front = *Temp
      *This\Rear = *Temp
      ProcedureReturn 0
    EndIf
    
    *This\Rear\Link = *Temp
    *This\Rear = *Temp
    
  EndProcedure
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< The Dequeue operator <<<<<
  
  Procedure Dequeue(*This.Private_Members)
    
    *Temp.Node = *This\Front
    
    If *This\Front = #Null
      ; MessageRequester("Queue Error", "The Queue is already Empty !")
      ProcedureReturn 0
    EndIf
    
    If *This\Front = *This\Rear
      *This\Front = #Null
      *This\Rear = #Null
    Else
      *This\Front = *This\Front\Link
    EndIf
    
    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
    
    FreeStructure(*Temp)
    
  EndProcedure
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< The FrontTag operator <<<<<
  
  Procedure.l FrontTag(*This.Private_Members)
    
    If *This\Front <> #Null
      ProcedureReturn *This\Front\Tag
    Else
      MessageRequester("Queue Error", "The Queue is Empty !")
    EndIf
    
  EndProcedure
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< The FrontObjectPtr operator <<<<<
  
  Procedure.i FrontObjectPtr(*This.Private_Members)
    
    If *This\Front <> #Null
      ProcedureReturn *This\Front\ObjectPtr
    Else
      MessageRequester("Queue Error", "The Queue is Empty !")
    EndIf
    
  EndProcedure
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< The IsEmpty operator <<<<<
  
  Procedure.b IsEmpty(*This.Private_Members)
    
    If *This\Front = #Null
      ProcedureReturn #True
    Else
      ProcedureReturn #False
    EndIf
    
  EndProcedure
  
  ; <<<<<<<<<<<<<<<<<<<<<<<<<<
  ; <<<<< The Destructor <<<<<

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

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

  DataSection
    START_METHODS:
    Data.i @Enqueue()
    Data.i @Dequeue()
    Data.i @FrontTag()
    Data.i @FrontObjectPtr()
    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
  
  MyQueue.Queue::Queue = Queue::New(#Null)
  
  MyQueue\Enqueue(#TAG_PYRAMID, AllocateStructure(Pyramid), #Null)
  MyQueue\Enqueue(#TAG_SPHERE, AllocateStructure(Sphere), #Null)
  MyQueue\Enqueue(#TAG_CUBE, AllocateStructure(Cube), #Null)
  MyQueue\Enqueue(#TAG_SPHERE, AllocateStructure(Sphere), #Null)
  MyQueue\Enqueue(#TAG_DODECAHEDRON, AllocateStructure(Dodecahedron), #Null)
  MyQueue\Enqueue(#TAG_PYRAMID, AllocateStructure(Pyramid), #Null)
  
  While MyQueue\IsEmpty() <> #True
    
    Select MyQueue\FrontTag()
        
      Case #TAG_DODECAHEDRON
        *Dodecahedron.Dodecahedron = MyQueue\FrontObjectPtr()
        Debug "In the queue there is a Dodecahedron"
        
      Case #TAG_SPHERE
        *Sphere.Sphere = MyQueue\FrontObjectPtr()
        Debug "In the queue there is a Sphere"  
        
      Case #TAG_CUBE
        *Cube.Cube = MyQueue\FrontObjectPtr()
        Debug "In the queue there is a Cube" 
        
      Case #TAG_PYRAMID 
        *Pyramid.Pyramid = MyQueue\FrontObjectPtr()
        Debug "In the queue there is a Pyramid" 
        
    EndSelect

    MyQueue\Dequeue()
    
  Wend  
  
  MyQueue\Free()
  
CompilerEndIf

; <<<<<<<<<<<<<<<<<<<<<<<
; <<<<< END OF FILE <<<<<
; <<<<<<<<<<<<<<<<<<<<<<<

PureBasic Forums - English

Data Structure - Queue - OOP

Data Structure - Queue - OOP

Re: Data Structure - Queue - OOP