This is a quick post to show how easy (and beautiful) it is to implement a simple (not the best though) and elegant FIFOs and LIFOs in OCaml.
For the Queue (FIFO), here is an elegant implementation using references on Lists:
The Queue is composed of 2 Lists holding the front elements (used for adding new elements to the Queue) and a back list holding elements when we call take (or dequeue).
The add function is simple, it just take an elements and put it at the beginning of the front list queue := (x::front, back)
The take function is the one that does all the work, it checks if the Queue is not empty (an empty queue is a queue that both front and back lists are empty), then it checks if the back list has at least one element, if this is the case, the element is deleted from the queue and then returned.
Otherwise the back list is empty, so we take elements from the front list (the one used to store elements when we call add), reverse them, and store them in the back list, then the function calls itself recursively to extract the new available elements.
And in case you didn’t notice, both the Stack and Queue are generics by nature, they accept any type for their elements.