
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


 
;; put info string in permanent storage for later use
(info 'make-Q 
"usage: (define q (make-Q)) ;  (q '[top | empty? | pop | push value | to-list | from-list list])")
 
;; make-Q
(define (make-Q)
  (let ((q (make-vector 0)))
    (lambda (message . args)
      (case message
        ((empty?) (vector-empty? q))
        ((top) (if (vector-empty? q) (error  'Q:top:empty q) (vector-ref q 0)))
        ((push) (vector-push q (car args)))
        ((pop) (if (vector-empty? q) (error 'Q:pop:empty q) (vector-shift q)))
        ((to-list) (vector->list q))
        ((from-list) (set! q (list->vector (car args))) q )
        (else (info 'make-Q) (error  "Q:bad message:" message )))))) ; display info if unknown message
 
;; 
(define q (make-Q))
(q 'empty?) → #t
(q 'push 'first) → first
(q 'push 'second) → second
(q 'pop) → first
(q 'pop) → second
(q 'top)
"💬 error: Q:top:empty #()"
(q 'from-list '( 6 7 8)) → #( 6 7 8)
(q 'top) → 6
(q 'pop) → 6
(q 'to-list)→ (7 8)
(q 'delete)
"💭 error: Q:bad message: delete"
 
;; save make-Q
(local-put 'make-Q)
 