Module Queue
: (moduleStdlib__Queue)
Unsynchronized accesses
Unsynchronized accesses to a queue may lead to an invalid queue state. Thus, concurrent accesses to
queues must be synchronized (for instance with a Mutex.t ).
type!'at
The type of queues containing elements of type 'a .
exceptionEmpty
Raised when Queue.take or Queue.peek is applied to an empty queue.
valcreate : unit->'at
Return a new queue, initially empty.
valadd : 'a->'at->unitaddxq adds the element x at the end of the queue q .
valpush : 'a->'at->unitpush is a synonym for add .
valtake : 'at->'atakeq removes and returns the first element in queue q , or raises Queue.Empty if the queue is empty.
valtake_opt : 'at->'aoptiontake_optq removes and returns the first element in queue q , or returns None if the queue is empty.
Since 4.08
valpop : 'at->'apop is a synonym for take .
valpeek : 'at->'apeekq returns the first element in queue q , without removing it from the queue, or raises Queue.Empty
if the queue is empty.
valpeek_opt : 'at->'aoptionpeek_optq returns the first element in queue q , without removing it from the queue, or returns None if
the queue is empty.
Since 4.08
valtop : 'at->'atop is a synonym for peek .
valdrop : 'at->unitdropq removes the first element in queue q , or raises Queue.Empty if the queue is empty.
Since 5.3
valclear : 'at->unit
Discard all elements from a queue.
valcopy : 'at->'at
Return a copy of the given queue.
valis_empty : 'at->bool
Return true if the given queue is empty, false otherwise.
vallength : 'at->int
Return the number of elements in a queue.
valiter : ('a->unit)->'at->unititerfq applies f in turn to all elements of q , from the least recently entered to the most recently
entered. The queue itself is unchanged.
valfold : ('acc->'a->'acc)->'acc->'at->'accfoldfaccuq is equivalent to List.fold_leftfaccul , where l is the list of q 's elements. The queue
remains unchanged.
valtransfer : 'at->'at->unittransferq1q2 adds all of q1 's elements at the end of the queue q2 , then clears q1 . It is equivalent
to the sequence iter(funx->addxq2)q1;clearq1 , but runs in constant time.
Iteratorsvalto_seq : 'at->'aSeq.t
Iterate on the queue, in front-to-back order. The behavior is not specified if the queue is modified
during the iteration.
Since 4.07
valadd_seq : 'at->'aSeq.t->unit
Add the elements from a sequence to the end of the queue.
Since 4.07
valof_seq : 'aSeq.t->'at
Create a queue from a sequence.
Since 4.07
ExamplesBasicExample
A basic example:
#letq=Queue.create()valq:'_weak1Queue.t=<abstr>#Queue.push1q;Queue.push2q;Queue.push3q-:unit=()#Queue.lengthq-:int=3#Queue.popq-:int=1#Queue.popq-:int=2#Queue.popq-:int=3#Queue.popqException:Stdlib.Queue.Empty.SearchThroughaGraph
For a more elaborate example, a classic algorithmic use of queues is to implement a BFS (breadth-first
search) through a graph.
typegraph={edges:(int,intlist)Hashtbl.t}(*Searchingraph[g]usingBFS,startingfromnode[start].Itreturnsthefirstnodethatsatisfies[p],or[None]ifnonodereachablefrom[start]satisfies[p].*)letsearch_for~(g:graph)~(start:int)(p:int->bool):intoption=letto_explore=Queue.create()inletexplored=Hashtbl.create16inQueue.pushstartto_explore;letrecloop()=ifQueue.is_emptyto_explorethenNoneelse(*nodetoexplore*)letnode=Queue.popto_exploreinexplore_nodenodeandexplore_nodenode=ifnot(Hashtbl.memexplorednode)then(ifpnodethenSomenode(*found*)else(Hashtbl.addexplorednode();letchildren=Hashtbl.find_optg.edgesnode|>Option.value~default:[]inList.iter(funchild->Queue.pushchildto_explore)children;loop()))elseloop()inloop()(*asamplegraph*)letmy_graph:graph=letedges=List.to_seq[1,[2;3];2,[10;11];3,[4;5];5,[100];11,[0;20];]|>Hashtbl.of_seqin{edges}#search_for~g:my_graph~start:1(funx->x=30)-:intoption=None#search_for~g:my_graph~start:1(funx->x>=15)-:intoption=Some20#search_for~g:my_graph~start:1(funx->x>=50)-:intoption=Some100
OCamldoc 2025-06-12 Stdlib.Queue(3o)
Install Now
PNG Icons
