
Data Structure

This illustrates a data structure, a means of storing data within a program.

You may see other such structures in the Data Structures category.
 Illustration of FIFO behavior
Task

Implement a FIFO queue.

Elements are added at one side and popped from the other in the order of insertion.



Operations:

   push   (aka enqueue)    - add element
   pop     (aka dequeue)    - pop first element
   empty                             - return truth value when empty


Errors:

   handle the error of trying to pop from an empty queue (behavior depends on the language and platform)


See

   Queue/Usage   for the built-in FIFO or queue of your language or standard library.


See also

 Array
 Associative array: Creation, Iteration
 Collections
 Compound data type
 Doubly-linked list: Definition, Element definition, Element insertion, List Traversal, Element Removal
 Linked list
 Queue: Definition, Usage
 Set
 Singly-linked list: Element definition, Element insertion, List Traversal, Element Removal
 Stack


' FB 1.05.0 Win64
 
' queue_rosetta.bi
' simple generic Queue type
 
#Define Queue(T) Queue_##T
 
#Macro Declare_Queue(T)
Type Queue(T)
 Public:
    Declare Constructor()
    Declare Destructor()
    Declare Property capacity As Integer
    Declare Property count As Integer 
    Declare Property empty As Boolean
    Declare Property front As T 
    Declare Function pop() As T   
    Declare Sub push(item As T)
  Private:
    a(any) As T 
    count_ As Integer = 0  
    Declare Function resize(size As Integer) As Integer    
End Type
 
Constructor Queue(T)()
  Redim a(0 To 0) '' create a default T instance for various purposes 
End Constructor
 
Destructor Queue(T)()
  Erase a
End Destructor
 
Property Queue(T).capacity As Integer
  Return UBound(a)
End Property
 
Property Queue(T).count As Integer
  Return count_
End Property
 
Property Queue(T).empty As Boolean
  Return count_ = 0
End Property
 
Property Queue(T).front As T
  If count_ > 0 Then
    Return a(1)
  End If
  Print "Error: Attempted to access 'front' element of an empty queue"
  Return a(0)  '' return default element 
End Property
 
Function Queue(T).pop() As T
  If count_ > 0 Then
    Dim value As T = a(1)
    If count_ > 1 Then  '' move remaining elements to fill space vacated 
      For i As Integer = 2 To count_
        a(i - 1) = a(i)
      Next 
    End If  
    a(count_) = a(0)  '' zero last element
    count_ -= 1
    Return value
  End If
  Print "Error: Attempted to remove 'front' element of an empty queue"
  Return a(0)  '' return default element
End Function
 
Sub Queue(T).push(item As T)
  Dim size As Integer = UBound(a)
  count_ += 1
  If count_ >  size Then
    size = resize(size)
    Redim Preserve a(0 to size)
  End If
  a(count_) = item   
End Sub
 
Function Queue(T).resize(size As Integer) As Integer
  If size = 0 Then
    size = 4
  ElseIf size <= 32 Then
    size  = 2 * size
  Else
    size += 32
  End If
  Return size
End Function
#EndMacro