
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


 
#lang racket
 
(define (make-queue) (mcons #f #f))
(define (push! q x)
  (define new (mcons x #f))
  (if (mcar q) (set-mcdr! (mcdr q) new) (set-mcar! q new))
  (set-mcdr! q new))
(define (pop! q)
  (define old (mcar q))
  (cond [(eq? old (mcdr q)) (set-mcar! q #f) (set-mcdr! q #f)]
        [else (set-mcar! q (mcdr old))])
  (mcar old))
(define (empty? q)
  (not (mcar q)))
 
(define Q (make-queue))
(empty? Q) ; -> #t
(push! Q 'x)
(empty? Q) ; -> #f
(for ([x 3]) (push! Q x))
(pop! Q)   ; -> 'x
(list (pop! Q) (pop! Q) (pop! Q)) ; -> '(0 1 2)
 