Stacks, queues, priority queues and buffers

Building a 10,000-line report by joining strings with ^ allocated 80,393,105 words of memory; the same report built with a Buffer allocated 488,915, about 164 times fewer. The standard library keeps a mutable container for each shape of waiting work, and reaching for the wrong one is how a program that passes every small test falls over on real input.

You will use Stack, Queue and OCaml 5.4’s Pqueue, implement Dijkstra’s shortest travel times with a min-priority queue, build a long string with Buffer and measure what it saves over ^, and choose a container by reading its cost table.

A stack is last in, first out

A stackLIFO: Last in, first out: the order a stack serves items, where the most recently added item is removed first. serves the item added most recently. The OCaml Stack module is mutable: Stack.push x s adds x to the top in place and returns unit, and Stack.pop s removes and returns the top. Adding to an immutable list gives you a second list and leaves the first untouched; pushing changes the one stack you already hold. Push 10, 20 and 30, then pop them, and they come back 30, 20, 10, the reverse of the order they went in:

An empty stack has nothing to return, so Stack.pop raises Stack.Empty; Stack.pop_opt answers None instead, and Stack.top looks at the top without removing it. An OCaml Stack holds elements of one type, written 'a Stack.t. The toplevel session shows each of these, then compiles an editor whose undo and redo are two stacks:

from session import run, toplevel, write

# A stack is last in, first out: the same pushes and pops as the AlgoViz stack figure, then the two exceptions, then
# an editor whose undo and redo are two stacks. Deterministic: no times, no addresses.

toplevel("""
let s = Stack.create ();;

Stack.push 10 s; Stack.push 20 s; Stack.push 30 s; Stack.length s;;

Stack.top s;;

Stack.pop s;;

Stack.pop s;;

Stack.pop s;;

Stack.pop s;;

Stack.pop_opt s;;
""")

write("undo_redo.ml", """let undo : string Stack.t = Stack.create ()
let redo : string Stack.t = Stack.create ()
let doc = ref ""

let show label =
  Printf.printf "%-13s doc=%-14S undo=%d redo=%d\\n"
    label !doc (Stack.length undo) (Stack.length redo)

let typ s =
  Stack.push !doc undo;   (* remember the document before the edit *)
  Stack.clear redo;       (* a fresh edit cancels anything to redo *)
  doc := !doc ^ s;
  show (Printf.sprintf "type %S" s)

let undo_one () =
  match Stack.pop_opt undo with
  | None -> print_string "nothing to undo\\n"
  | Some prev -> Stack.push !doc redo; doc := prev; show "undo"

let redo_one () =
  match Stack.pop_opt redo with
  | None -> print_string "nothing to redo\\n"
  | Some next -> Stack.push !doc undo; doc := next; show "redo"

let () =
  show "start";
  typ "hello";
  typ " world";
  undo_one ();
  undo_one ();
  redo_one ()
""")

run("""
ocamlfind ocamlopt undo_redo.ml -o undo_redo
./undo_redo
""")

$ ocaml
OCaml version 5.5.1
Enter #help;; for help.

# let s = Stack.create ();;
val s : '_weak1 Stack.t = <abstr>
# 
  Stack.push 10 s; Stack.push 20 s; Stack.push 30 s; Stack.length s;;
  - : int = 3
# 
  Stack.top s;;
  - : int = 30
# 
  Stack.pop s;;
  - : int = 30
# 
  Stack.pop s;;
  - : int = 20
# 
  Stack.pop s;;
  - : int = 10
# 
  Stack.pop s;;
  Exception: Stdlib.Stack.Empty.
# 
  Stack.pop_opt s;;
  - : int option = None
$ ocamlfind ocamlopt undo_redo.ml -o undo_redo
$ ./undo_redo
start         doc=""             undo=0 redo=0
type "hello"  doc="hello"        undo=1 redo=0
type " world" doc="hello world"  undo=2 redo=0
undo          doc="hello"        undo=1 redo=1
undo          doc=""             undo=0 redo=2
redo          doc="hello"        undo=1 redo=1

The editor keeps the document in a refref: A mutable cell holding one value, created with ref v: !r reads its contents and r := v replaces them. It is a record with a single mutable field, contents. More in “Refs, loops and mutable state” and two stacks. Typing pushes the old document onto the undo stack and clears the redo stack, because a fresh edit cancels anything there was to redo. Undo pops the undo stack onto the redo stack; redo does the reverse. Follow the two stacks through two edits, two undos and one redo:

After typing hello and world, the undo stack held two earlier documents. Two undos emptied it and left the redo stack holding two, and a single redo moved one back, so the document returned to hello with one step left to undo and one to redo.

That single Stack.clear is the difference between a redo the user can trust and one that resurrects text from a branch they had left behind.

A queue is first in, first out

A queueFIFO: First in, first out: the order a queue serves items, where the item that has waited longest is removed first. serves the item that has waited longest. The OCaml Queue module is mutable too: Queue.add x q adds x at the back, Queue.take q removes and returns the front, and Queue.peek q looks at the front without removing it. Queues keep their arrival order, so adding 1, 2 and 3 and taking three times gives 1, 2, 3, the order they arrived:

Taking from an empty queue raises Queue.Empty, and Queue.take_opt returns None instead. A round-robin scheduler uses a queue to give each task one time slice in turn: take the task at the front, run one slice, and if it still has work, add it to the back so the others go before it comes round again. The session shows both:

from session import run, toplevel, write

# A queue is first in, first out: the same enqueues and takes as the AlgoViz queue figure, the empty-queue exception
# and take_opt, then a round-robin scheduler that gives each task one time slice in turn. Deterministic.

toplevel("""
let q = Queue.create ();;

Queue.add 1 q; Queue.add 2 q; Queue.add 3 q; Queue.length q;;

Queue.peek q;;

Queue.take q;;

Queue.take q;;

Queue.take q;;

Queue.take q;;

Queue.take_opt q;;
""")

write("round_robin.ml", """(* Each task needs a number of time slices; the scheduler gives one slice to the
   task at the front, then puts it back if it still has work. *)
let q : (string * int) Queue.t = Queue.create ()

let () =
  List.iter (fun job -> Queue.add job q) [ "build", 3; "lint", 1; "test", 2 ];
  let slice = ref 0 in
  while not (Queue.is_empty q) do
    let name, left = Queue.take q in
    incr slice;
    Printf.printf "slice %d: %s (%d left)\\n" !slice name (left - 1);
    if left - 1 > 0 then Queue.add (name, left - 1) q
  done;
  Printf.printf "finished after %d slices\\n" !slice
""")

run("""
ocamlfind ocamlopt round_robin.ml -o round_robin
./round_robin
""")

$ ocaml
OCaml version 5.5.1
Enter #help;; for help.

# let q = Queue.create ();;
val q : '_weak1 Queue.t = <abstr>
# 
  Queue.add 1 q; Queue.add 2 q; Queue.add 3 q; Queue.length q;;
  - : int = 3
# 
  Queue.peek q;;
  - : int = 1
# 
  Queue.take q;;
  - : int = 1
# 
  Queue.take q;;
  - : int = 2
# 
  Queue.take q;;
  - : int = 3
# 
  Queue.take q;;
  Exception: Stdlib.Queue.Empty.
# 
  Queue.take_opt q;;
  - : int option = None
$ ocamlfind ocamlopt round_robin.ml -o round_robin
$ ./round_robin
slice 1: build (2 left)
slice 2: lint (0 left)
slice 3: test (1 left)
slice 4: build (1 left)
slice 5: test (0 left)
slice 6: build (0 left)
finished after 6 slices

Three tasks needing 3, 1 and 2 slices finished in six slices, each task stepping to the back after its turn: build, lint, test, build, test, build. A stack would have run one task to completion before starting the next; the queue shares the machine fairly because the longest waiter always goes first.

A priority queue hands back the smallest first

A list keeps arrival order and a sorted structure keeps every element in order; a priority queuepriority queue: A collection that hands back the item of highest priority; OCaml's Pqueue serves the smallest (MakeMin) or largest (MakeMax) element under a compare function. keeps only enough order to answer one question fast: what is the smallest element right now? OCaml’s Pqueue, new in 5.4, provides it. Pqueue.MakeMin builds a min-priority queue over a totally orderedtotal order: An ordering in which any two values are either equal or one is smaller than the other, the answer agrees whichever way round they are compared, and it is transitive: if a < b and b < c then a < c. Map.Make and Set.Make need a compare that is one. More in “Maps and sets” type, and Pqueue.MakeMax a max one. The module stores its elements as a binary heapA tree kept in an array where every parent is at most (a min-heap) or at least (a max-heap) its children, so the extreme element is always at the root. in a dynamic arraydynamic array: A collection that keeps its elements in an array and replaces that array with a larger one when it fills, so elements can be appended without a length being fixed in advance; OCaml's is Dynarray. More in “Arrays, Dynarray and immutable arrays”, so min_elt is constant time while add and pop_min take time logarithmic in the size. Watch the min-heap take shape as five numbers are inserted, the smallest climbing to the root:

The same five numbers go into a Pqueue.MakeMin (Int) queue below. of_list builds the queue in linear time, faster than adding one at a time; min_elt returns the smallest without removing it, and pop_min removes and returns it. The manual guarantees that min_elt names exactly the element pop_min will remove. On an empty queue min_elt and pop_min return None, while get_min_elt raises Invalid_argument:

from session import toplevel

# A priority queue always hands back the smallest. MakeMin (Int) shows the API the curriculum names (create, add,
# min_elt, pop_min, length, of_list), that min_elt names the element pop_min removes, the empty cases, and the
# tuple-of-pops evaluation-order trap with its let fix. The signature printed once lists the whole module.

toplevel("""
module Pq = Pqueue.MakeMin (Int);;

let q = Pq.of_list [ 5; 3; 8; 1; 9 ];;

Pq.length q;;

Pq.min_elt q;;

Pq.pop_min q;;

Pq.pop_min q;;

Pq.length q;;

let empty = Pq.create () in Pq.min_elt empty, Pq.pop_min empty;;

let empty = Pq.create () in Pq.get_min_elt empty;;

let q2 = Pq.of_list [ 5; 3; 8; 1; 9 ] in
(Pq.pop_min q2, Pq.pop_min q2, Pq.length q2);;

let q3 = Pq.of_list [ 5; 3; 8; 1; 9 ] in
let a = Pq.pop_min q3 in
let b = Pq.pop_min q3 in
let n = Pq.length q3 in
(a, b, n);;
""")

$ ocaml
OCaml version 5.5.1
Enter #help;; for help.

# module Pq = Pqueue.MakeMin (Int);;
module Pq :
  sig
    type t = Pqueue.MakeMin(Int).t
    val create : unit -> t
    val length : t -> int
    val is_empty : t -> bool
    val add : t -> Int.t -> unit
    val add_iter : t -> ((Int.t -> unit) -> 'x -> unit) -> 'x -> unit
    val min_elt : t -> Int.t option
    val get_min_elt : t -> Int.t
    val pop_min : t -> Int.t option
    val remove_min : t -> unit
    val clear : t -> unit
    val copy : t -> t
    val of_array : Int.t array -> t
    val of_list : Int.t list -> t
    val of_iter : ((Int.t -> unit) -> 'x -> unit) -> 'x -> t
    val iter_unordered : (Int.t -> unit) -> t -> unit
    val fold_unordered : ('acc -> Int.t -> 'acc) -> 'acc -> t -> 'acc
  end
# 
  let q = Pq.of_list [ 5; 3; 8; 1; 9 ];;
  val q : Pq.t = <abstr>
# 
  Pq.length q;;
  - : int = 5
# 
  Pq.min_elt q;;
  - : Int.t option = Some 1
# 
  Pq.pop_min q;;
  - : Int.t option = Some 1
# 
  Pq.pop_min q;;
  - : Int.t option = Some 3
# 
  Pq.length q;;
  - : int = 3
# 
  let empty = Pq.create () in Pq.min_elt empty, Pq.pop_min empty;;
  - : Int.t option * Int.t option = (None, None)
# 
  let empty = Pq.create () in Pq.get_min_elt empty;;
  Exception: Invalid_argument "empty priority queue".
# 
  let q2 = Pq.of_list [ 5; 3; 8; 1; 9 ] in
  (Pq.pop_min q2, Pq.pop_min q2, Pq.length q2);;
    - : Int.t option * Int.t option * int = (Some 3, Some 1, 5)
# 
  let q3 = Pq.of_list [ 5; 3; 8; 1; 9 ] in
  let a = Pq.pop_min q3 in
  let b = Pq.pop_min q3 in
  let n = Pq.length q3 in
  (a, b, n);;
          - : Int.t option * Int.t option * int = (Some 1, Some 3, 3)

pop_min returned 1 then 3, the two smallest, and the length fell from 5 to 3. For a job scheduler the element is usually a (priority, payload) pair, with a compare that looks only at the priority, so two jobs of equal priority are treated as equal. The manual says nothing about which of two equal-priority elements leaves first, so never rely on that order. The next program drains such a queue one pop at a time, and takes the top three scores from a MakeMax queue:

from session import run, write

# (priority, payload) pairs: a compare that looks only at the priority, draining the queue one pop at a time (a match,
# never a tuple or list, so the pops run in order), and a MakeMax queue. Equal priorities come out in an order the
# manual does not fix, so the two priority-5 jobs may appear either way round.

write("jobs.ml", """(* The element is (priority, payload); the compare ignores the payload. *)
module Jq = Pqueue.MakeMin (struct
  type t = int * string
  let compare (p1, _) (p2, _) = Int.compare p1 p2
end)

let () =
  let jq = Jq.of_list [ (5, "mail"); (3, "backup"); (5, "cleanup"); (1, "alert") ] in
  let rec drain () =
    match Jq.pop_min jq with
    | None -> ()
    | Some (p, name) ->
        Printf.printf "run %s (priority %d)\\n" name p;
        drain ()
  in
  drain ()

module Top = Pqueue.MakeMax (Int)

let () =
  let scores = Top.of_list [ 71; 88; 64; 95; 88 ] in
  let rec take n =
    if n = 0 then []
    else match Top.pop_max scores with
      | None -> []
      | Some s -> s :: take (n - 1)
  in
  Printf.printf "top three scores: %s\\n"
    (String.concat ", " (List.map string_of_int (take 3)))
""")

run("""
ocamlfind ocamlopt jobs.ml -o jobs
./jobs
""")

$ ocamlfind ocamlopt jobs.ml -o jobs
$ ./jobs
run alert (priority 1)
run backup (priority 3)
run cleanup (priority 5)
run mail (priority 5)
top three scores: 95, 88, 88

The jobs ran in priority order: the alert (1), then the backup (3), then the two priority-5 jobs, and the manual does not promise which of those two goes first. A Pqueue keeps its heap in a Dynarray, whose manual calls unsynchronized access a programming error, so a shared priority queue needs a lock just as a stack or a queue does. The MakeMax queue gave the top three scores as 95, 88 and 88: a repeated score counts once per entry.

Sequenced with let, the pops happen in the order you read them, and the queue’s own behaviour is simple to reason about.

Shortest travel times with a priority queue

Dijkstra’s algorithm finds the shortest path from one place to every other, and a min-priority queue is the piece that makes it fast: it always hands back the nearest city not yet settled. The queue holds (distance so far, city) pairs and compares only the distance. The program runs on a small made-up network of Indian cities, with invented travel times in whole hours; the two-letter codes are DL Delhi, JP Jaipur, AG Agra, LK Lucknow, BP Bhopal, NG Nagpur and HY Hyderabad. Step through the same graph the program uses, settling the closest unsettled city each round:

Each round pops the nearest city, settles its distance and adds its neighbours with their new tentative distances. The program prints the cities as it settles them and then the final times:

from session import run, write

# Dijkstra's shortest paths with Pqueue.MakeMin, on the SAME made-up graph of Indian cities the AlgoViz dijkstra
# figure runs. Travel times are invented, in whole hours. Two-letter codes: DL Delhi, JP Jaipur, AG Agra, LK Lucknow,
# BP Bhopal, NG Nagpur, HY Hyderabad. Output is deterministic (cities are settled in a fixed order).

write("dijkstra.ml", """(* An element of the priority queue: (distance so far, city). The compare looks
   only at the distance, so the queue always hands back the nearest unsettled city. *)
module Frontier = Pqueue.MakeMin (struct
  type t = int * string
  let compare (d1, _) (d2, _) = Int.compare d1 d2
end)

(* The made-up road network: each edge is undirected, the weight a travel time in hours. *)
let roads =
  [ "DL", "JP", 5; "DL", "AG", 4; "JP", "AG", 4; "JP", "BP", 9;
    "AG", "LK", 6; "AG", "BP", 6; "LK", "BP", 8; "BP", "NG", 5;
    "BP", "HY", 11; "NG", "HY", 7 ]

let neighbours city =
  List.concat_map
    (fun (a, b, w) ->
      if a = city then [ (b, w) ] else if b = city then [ (a, w) ] else [])
    roads

let dijkstra start =
  let best = Hashtbl.create 16 in
  let q = Frontier.create () in
  Frontier.add q (0, start);
  let rec loop () =
    match Frontier.pop_min q with
    | None -> ()
    | Some (d, city) ->
        if not (Hashtbl.mem best city) then begin
          Hashtbl.add best city d;
          Printf.printf "settled %s at %2d h\\n" city d;
          List.iter
            (fun (next, w) ->
              if not (Hashtbl.mem best next) then Frontier.add q (d + w, next))
            (neighbours city)
        end;
        loop ()
  in
  loop ();
  best

let () =
  let best = dijkstra "DL" in
  print_string "shortest times from Delhi:\\n";
  List.iter
    (fun city -> Printf.printf "  %s %2d h\\n" city (Hashtbl.find best city))
    [ "AG"; "JP"; "LK"; "BP"; "NG"; "HY" ]
""")

run("""
ocamlfind ocamlopt dijkstra.ml -o dijkstra
./dijkstra
""")

$ ocamlfind ocamlopt dijkstra.ml -o dijkstra
$ ./dijkstra
settled DL at  0 h
settled AG at  4 h
settled JP at  5 h
settled LK at 10 h
settled BP at 10 h
settled NG at 15 h
settled HY at 21 h
shortest times from Delhi:
  AG  4 h
  JP  5 h
  LK 10 h
  BP 10 h
  NG 15 h
  HY 21 h

Delhi settled at 0, Agra at 4 and Jaipur at 5; Lucknow and Bhopal both at 10, and the priority queue settled whichever it popped first without the result depending on that choice; then Nagpur at 15 and Hyderabad at 21. A city can be added to the queue more than once with different distances, so the program keeps the settled distances in a Hashtbl and ignores a city it has already settled when it pops a stale, larger entry. Ignoring is safe because a travel time is never negative: the first time a city comes off the queue, no route still waiting can reach it sooner. That is simpler than searching the queue for an entry to update, which Pqueue has no operation for: the program only ever adds entries and pops the smallest.

Building a long report without recopying it

Joining strings with ^ makes a brand-new string every time, copying both sides, so building a report line by line with acc := !acc ^ line copies the whole report so far on every line. The cost grows with the square of the number of lines. A Buffer is a mutable, growing byte store: Buffer.add_string writes into the space it already has and only occasionally grows, which the manual gives as constant amortisedamortised cost: The average cost of one operation over a long run of them: a Dynarray append may copy every element when the array fills, yet n appends copy about 2n elements in all, so each append costs a constant on average. More in “Arrays, Dynarray and immutable arrays” time per character. The program builds a 10,000-line report both ways and measures the words each allocates, counting allocation rather than time so two runs print the same numbers:

from session import run, write

# Building a long string: repeated ^ copies the whole text so far on every line, so its cost grows with the square of
# the number of lines; Buffer writes into one growing byte store. We measure words allocated (Gc.allocated_bytes,
# which counts the large strings that skip the minor heap), never time, so two runs print the same lines.

write("report.ml", """let lines = 10_000

let row i = Printf.sprintf "row %d: ok\\n" i

(* Words allocated while f runs, from the GC's own total counter. *)
let words f =
  let before = Gc.allocated_bytes () in
  let r = f () in
  (r, int_of_float ((Gc.allocated_bytes () -. before) /. 8.))

let with_concat () =
  let acc = ref "" in
  for i = 1 to lines do
    acc := !acc ^ row i
  done;
  !acc

let with_buffer () =
  let b = Buffer.create 256 in
  for i = 1 to lines do
    Buffer.add_string b (row i)
  done;
  Buffer.contents b

let () =
  let s1, w1 = words with_concat in
  let s2, w2 = words with_buffer in
  Printf.printf "lines:            %d\\n" lines;
  Printf.printf "same report:      %b (%d bytes)\\n" (s1 = s2) (String.length s1);
  Printf.printf "concat allocated: %d words\\n" w1;
  Printf.printf "buffer allocated: %d words\\n" w2;
  Printf.printf "concat / buffer:  %d times\\n" (w1 / w2)
""")

run("""
ocamlfind ocamlopt report.ml -o report
./report
""")

$ ocamlfind ocamlopt report.ml -o report
$ ./report
lines:            10000
same report:      true (128894 bytes)
concat allocated: 80393105 words
buffer allocated: 488915 words
concat / buffer:  164 times

Both ways produced the identical 128,894-byte report, but the ^ version allocated 80,393,105 words against the buffer’s 488,915, about 164 times more, almost all of it thrown away at once as each longer intermediate string replaced the last. The earlier strings lesson introduces Buffer and Bytes for text that changes in place; here the point is the cost: buffers turn a quadratic pile of copies into a single growing store.

The report was identical both ways, so the only thing the buffer changed was the cost of building it.

Choosing a container from its cost table

The standard library’s own “Comparison of Standard Containers” tabulates what each operation costs, and the choice of container follows from which operation a task does most. The four mutable containers of this lesson each do their own job in constant or near-constant time, as the page and the modules’ manuals state:

Stacks, queues and priority queues serve one end only, and a buffer holds nothing but bytes (Buffer.nth reads one by position), so none of them is the container for a lookup by key or for general access by position. For those you want the containers of the earlier lessons: arrays and Dynarray for access by position, maps and sets for sorted keys, and hash tables for fast lookup by key. Answer two questions about your task and the table marks what fits:

In short: a stack when you want the most recent item back, a queue when you want the oldest, a priority queue when you want the smallest or largest key, and a buffer when you are assembling one string rather than serving items at all.

Practise: stacks, queues, priority queues and buffers

These questions put new values through the lesson’s containers. Predict each result or cost first, then check it:

Interview questions

Warm-up (fresher to 2–5 years): how do a stack and a queue differ, and when does each fit?

Both are mutable containers you add to and take from in constant time, and both keep their contents in one place rather than copying. They differ in which item they give back. A stack is last in, first out: Stack.pop returns the item pushed most recently, which suits undo histories, backtracking and depth-first search, where you want to finish the newest piece of work before older ones. A queue is first in, first out: Queue.take returns the item that has waited longest, which suits fair scheduling, buffering between a producer and a consumer, and breadth-first search, where every item should be handled in the order it arrived. Reach for a stack when newer work should pre-empt older, and a queue when older work should go first.

Two harder questions follow. For each one, decide what you would reach for and what you would measure first, then open its first step:

Key takeaways

• A stack is last in, first out and a queue is first in, first out; both add and serve in constant time, and two stacks model an editor’s undo and redo while a queue schedules tasks round-robin.
• A priority queue serves the smallest (MakeMin) or largest (MakeMax) element, with min_elt constant time and add and pop_min logarithmic, and it does not promise an order among equal priorities.
• Dijkstra’s shortest paths use a min-priority queue of (distance, city) pairs compared on distance, and ignore a stale entry for a city that is already settled.
• Building a 10,000-line report with ^ allocated about 164 times the words of a Buffer, because each ^ recopies the whole string so far while a buffer writes into one growing store.
• Stacks and queues cost O(1) at their ends and a priority queue O(log n); none of them looks an element up by key or reads a middle position, so an array, a map or a hash table is the right choice when you need that.