14

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.

Community
  • 1
  • 1
smandape
  • 1,033
  • 2
  • 14
  • 31
  • 4
    I don't think there's any advantage to it. They just want to see if you understand both data structures well enough that you can **do** it. Well, perhaps there are some languages that have a builtin stack data type, but not a queue. – Tom Zych Sep 13 '11 at 00:01
  • @Oli: I went through it and was unable to get the real answer out of it. So I asked it again. Thank you for your help. – smandape Sep 13 '11 at 00:04
  • @smandape: If you couldn't understand the answer from the other question then perhaps your real question is about the purpose of purely functional datastructures instead? – hugomg Sep 13 '11 at 00:08
  • Having an answer doesn't make the question any less of a dupe unfortunately, so I _am_ voting to close. – paxdiablo Sep 13 '11 at 00:23
  • If the answer you saw on the dupe was not understood, I believe the right thing to do was to leave a comment stating so, which would give the answerer (or anyone else for that matter) a chance to expand on it, hopefully making it more clear. Having the same question asked and answered twice is going to render SO a lot less useful. And you _didn't_ get -ve rep by the way, +3 and -1 (to date) gives you positive rep, if that's important. – paxdiablo Sep 13 '11 at 01:24

1 Answers1

18

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!

Community
  • 1
  • 1
templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
  • This really helps a lot and makes a non-computer guy like me understand things clearly. Thank you for your help and I appreciate the links provided with the answer. – smandape Sep 13 '11 at 00:16
  • Just out of interest, do you have a citation for the assertion that implementing a queue as two stacks is amortised O(1)? – paxdiablo Sep 13 '11 at 00:24
  • @paxdiablo- There's a great resource here (http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15750-s04/www/lect07-sc.txt) that's by Daniel Sleator, inventor of splay heaps. Hope this helps! – templatetypedef Sep 13 '11 at 00:26
  • Apologies, on rereading your answer, I should have picked up that you were talking about a _single_ item going through the queue as amortised O(1). For some bizarre reason, I though you meant `n` items, which was hard to believe :-) My mistake. – paxdiablo Sep 13 '11 at 01:30
  • @paxdiablo- No worries! Though I'd love a queue that could process n elements in O(1) time... :-) – templatetypedef Sep 13 '11 at 01:31
  • I've also read that by implementing the queue this way, you make it immutable. I'm really confused about it, how is it immutable? – hattenn Dec 02 '11 at 00:47
  • 1
    @hattenn It's not necessarily immutable (you can make a mutable queue this way too), but it is a good way to implement an immutable queue. It's easy to take this approach and not have the push and pop operations change the queue, but return a new queue. So you now have the old queue unchanged, and a new one. An interesting feature is that since these queues are immutable, and the internal stacks can also be immutable, then these different queues with different stacks will contain lots of sub-stacks in common which (since they are immutable) can safely be the same stacks, with low memory use. – Jon Hanna Dec 30 '11 at 13:42
  • 1
    @templatetypedef: I think the direction of your queue automaton argument is wrong: say I have a Turing machine, and you have to construct a queue automaton which mimics it. You convert my Turing machine into a two-stack automaton, and then... what? Convert your queue automaton into a two-stack one? But which queue automaton? What you need to show what you claim is a queue-based emulation of two stacks; what you can show with your assumptions is that queue automatons aren't *more* than Turing complete. – Jonas Kölker Feb 08 '13 at 18:44
  • @JonasKölker- You're absolutely right - good catch! – templatetypedef Feb 08 '13 at 19:18