
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


type
 
  Node[T] = ref object
    value: T
    next: Node[T]
 
  Queue*[T] = object
    head, tail: Node[T]
    length: Natural
 
func initQueue*[T](): Queue[T] = Queue[T]()
 
func len*(queue: Queue): Natural =
  queue.length
 
func isEmpty*(queue: Queue): bool {.inline.} =
  queue.len == 0
 
func push*[T](queue: var Queue[T]; value: T) =
  let node = Node[T](value: value, next: nil)
  if queue.isEmpty: queue.head = node
  else: queue.tail.next = node
  queue.tail = node
  inc queue.length
 
func pop*[T](queue: var Queue[T]): T =
  if queue.isEmpty:
    raise newException(ValueError, "popping from empty queue.")
  result = queue.head.value
  queue.head = queue.head.next
  dec queue.length
  if queue.isEmpty: queue.tail = nil
 
 
when isMainModule:
 
  var fifo = initQueue[int]()
 
  fifo.push(26)
  fifo.push(99)
  fifo.push(2)
  echo "Fifo size: ", fifo.len()
  try:
    echo "Popping: ", fifo.pop()
    echo "Popping: ", fifo.pop()
    echo "Popping: ", fifo.pop()
    echo "Popping: ", fifo.pop()
  except ValueError:
    echo "Exception catched: ", getCurrentExceptionMsg()