David Feuer is a long-time Haskell puzzler and lead maintainer of the containers and unordered-containers packages.

Stacks and queues with amortized logarithmic-time operations

Functional stacks are usually represented as linked lists. Functional queues are usually represented as tree structures. All of these have substantial space overhead and potentially poor locality. By mashing together array doubling with something like Okasaki’s implicit queue structures, we obtain stacks and queues that require only logarithmic space overhead. In exchange, we give up constant-time operations for logarithmic-time ones.