URL

Implement Stack using Queues - LeetCode

Code

https://github.com/syohex/dotnet-study/tree/master/fsharp/leetcode/challenge/202308/implement_stack_using_queues/main.fsx

type MyStack =
    { queue: int list }

    static member empty() : MyStack = { queue = [] }

    static member push (x: int) (s: MyStack) : MyStack = { s with queue = s.queue @ [ x ] }

    static member pop(s: MyStack) : (int * MyStack) =
        let rec pop' q acc =
            match q with
            | [] -> failwith "never reach here"
            | h :: [] -> h, { queue = List.rev acc }
            | h :: t -> pop' t (h :: acc)

        pop' s.queue []

    static member top(s: MyStack) : int =
        let rec top' q =
            match q with
            | [] -> failwith "never reach here"
            | h :: [] -> h
            | _ :: t -> top' t

        top' s.queue

    static member empty(s: MyStack) : bool = List.isEmpty s.queue