Why do we do "implement a queue using 2 stacks"? [duplicate]

Question

Possible Duplicate:
Why use two stacks to make a queue?

I got this assignment question that asks me to implement a queue using two stacks. My question is not how to do it but why to do it? I am not from computer background and I tried to find the answer for this, but couldn't really find why to do it? I think you experts can help me understand what are advantages of implementing such a thing. I found a related article Why use two stacks to make a queue? talking about this, but want to know if there is anything more.

Answer 1

There are a few very good reasons to do this.

First, some functional programming languages like Haskell, ML, or Lisp support lists as a built-in type. Lists typically are represented as singly, forward-linked lists, which means that they support O(1) prepend but O(n) concatenate. In languages like this, it's extremely easy to make a stack - you just prepend to a list to push and drop the first element to pop. Because of the internal implementation, this runs in O(1) time. If you tried to make a queue using this sort of list, enqueue would take O(n) time because you'd have to add to the end of a singly-linked list that doesn't store a pointer to the last element. On the other hand, if you implement the queue using two stacks (or more; the Hood-Melville queue uses six!), then you can get amortized O(1) enqueue and dequeue even if you only have stacks in your language. Although more advanced data structures have been devised to support purely functional queues and lists (such as the 2-3 finger tree), the two-stack construction is still quite useful in many applications.

In addition to this, in some cases you may want to use special stacks to implement the queue to get extra functionality out. For example, you can augment a stack data structure to support O(1) find-min/find-max. If you have a stack like this, you can then use the two-stack construction to make a queue that also has O(1) find-min/find-max. Trying to solve this problem directly is much harder (check out my considerably more complex construction to make a queue with these properties!)

Finally, it is interesting from a theoretical perspective to know that a queue can be simulated with two stacks. In computability theory, a two-stack pushdown automaton is a theoretical computing device with power equivalent to a Turing machine. A queue automaton is a similar structure that uses a queue instead of two stacks. Because we know that you can simulate a queue with two stacks, you can immediately prove that the queue automaton is at least as powerful as a Turing machine, and thus that queue automata are Turing-complete.

Hope this helps!