:PROPERTIES: :ID: f1e2ca96-3b11-4d6a-bbe2-297f1bf45213 :mtime: 20231027022512 :ctime: 20231027022511 :END: #+title: queue (computer science) #+filetags: :public:project: * Definition of a queue ** FIFO Here is the interface for a first-in first-out (FIFO) queue #+BEGIN_SRC haskell empty_queue :: queue A queue_null :: queue A -> bool queue_head :: queue A -> A queue_pop :: queue A -> queue A queue_back :: queue A -> queue A #+END_SRC * Implementation of Queue ** Implementation of a FIFO queue in [[id:8952459c-5076-4e68-8a68-5f658209f39e][Ocaml]] #+BEGIN_SRC ocaml type 'a queue = | Q of 'a list * 'a list let normalise = function | Q ([] , tails) -> Q (List.rev tails , []) | q -> q let empty_queue = Q([], []) let queue_null = (=) empty_queue let queue_append (Q (heads, tails)) x = normalise (Q (heads , x :: tails)) exception EmptyQueue let queue_pop = function | Q (x :: heads , tails) -> normalise (Q (heads , tails)) | _ -> raise EmptyQueue let queue_head = function | Q (x :: _ , _) -> x | _ -> raise EmptyQueue #+END_SRC #+RESULTS: : <fun>