3
$\begingroup$

In "Real Time Queue Operations in Pure LISP" (ML implementation), Hood and Melville show an $O(1)$ worst-case simulation of a queue using 6 stacks and global rebuilding. Can a real-time queue be simulated with fewer stacks?

In "Simple and Efficient Purely Functional Queues and Deques", Okasaki shows an implementation using one stack and two lazy stacks.

Both Okasaki's and Hood & Melville's queues require purely functional stacks as building blocks, and both produce purely functional queues. If push and pop are destructive, can global rebuilding be used to simulate an ephemeral queue with 6 ephemeral stacks? Fewer?

$\endgroup$
3
$\begingroup$

Not sure I fully understand your question, but it seems related to Problem 1.3.49 from Sedgewicks Algorithm book.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.