Skip to content

Instantly share code, notes, and snippets.

@muratg
Created March 26, 2014 04:03
Show Gist options
  • Save muratg/9776793 to your computer and use it in GitHub Desktop.
Save muratg/9776793 to your computer and use it in GitHub Desktop.
Queue implementation using linked list
module QueueWithLL =
type Node<'T> = {
Item: 'T
mutable Next: Option<Node<'T>>
}
let node (x:'T) = { Item = x; Next = None }
type Queue<'T> = {
mutable Head: Option<Node<'T>>
mutable Tail: Option<Node<'T>>
}
let queue() = { Head = None; Tail = None }
let enqueue (q:Queue<'T>) (x:'T) : unit =
let n = node x
if q.Head.IsNone then
q.Head <- Some n
q.Tail <- Some n
else
q.Tail.Value.Next <- Some n
q.Tail <- Some n
()
let dequeue (q:Queue<'T>) : Option<'T> =
if q.Head.IsNone then
None
else
let item = q.Head.Value.Item
if q.Tail = q.Head then
q.Head <- None
q.Tail <- None
else
q.Head <- q.Head.Value.Next
Some item
module Test =
open QueueWithLL
let shouldEqual expected result =
printf "Result: %A " result
if result = expected then printfn "as expected." else printfn "should've been %A" expected
let run () =
let q: Queue<int> = queue()
// No item case
shouldEqual None (dequeue q)
// 1 item case
enqueue q 1
shouldEqual (Some 1) (dequeue q)
shouldEqual None (dequeue q)
// 3 item case
enqueue q 1
enqueue q 2
enqueue q 3
shouldEqual (Some 1) (dequeue q)
shouldEqual (Some 2) (dequeue q)
shouldEqual (Some 3) (dequeue q)
shouldEqual None (dequeue q)
[<EntryPoint>] let main argv = Test.run(); 0
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment