Search code examples
queuestack

Number of Minimum Stacks required to implement Queue


What is the minimum number of stacks needed to implement a queue? A queue can be implemented using 2 stacks but, Can it be implemented by using a single stack? All the enqueue operations can be push operations to the stack and all the dequeue operations would be reverse the stack, pop and reverse it again using recursion?


Solution

  • Yes, you can write a recursive method to reverse a stack, so it is possible to implement a queue using a single stack. It would be horribly inefficient, but it would work. See How to Reverse a Stack using Recursion for an example. Whether that counts as using only one stack is an open question. You're using only one explicit stack, but you're leaning pretty heavily on the process stack.

    Note, however, that the size of queue you can implement this way is limited by the size of the process stack. That's usually about a megabyte. In a 64-bit process you'll be lucky to support a queue of more than about 64K items because every recursive call will push a return address and a parameter (16 bytes total). You could of course increase the process' stack size at build time.