Two stacks with a deque, what's the purpose of implementing it?

Question

From Algorithms 4th:

1.3.48 Two stacks with a deque. Implement two stacks with a single deque so that each operation takes a constant number of deque operations (see Exercise 1.3.33).

What's the meaning of implementing 2 stacks with 1 single deque? Any practical reasons? Why don't I just create 2 stacks directly?

---

1.3.49 Queue with three stacks. Implement a queue with three stacks so that each queue operation takes a constant (worst-case) number of stack operations. Warning : high degree of difficulty.

Related question: How to implement a queue with three stacks?

Also, why do I have to implement a queue with three stacks? Can't I just create a queue directly too?

Answer 1

Stacks from Deques

Stacks are first-in, last-out structures. Deques let you push/pop from both their front and back. If you keep track of the number of items you've stored in the front/back then you can use the front as one stack and the back as the other, returning NULL items if your counters go to zero.

Why would you do this? Who knows, but read on.

Queues from Stacks

You can implement a queue so that it has O(1) amortized time on all of its operations by using two stacks. When you're placing items on the queue place them in one stack. When you need to pull things off the queue, empty that stack into the other stack and pop from the top of that stack (while filling up the other stack with new incoming items).

Why would you want to do this?

Because, this is, roughly speaking, how you make a queue. Data structures have to be implemented somehow. In a computer you allocate memory starting from a base address and building outwards. Thus, a stack is a very natural data structure because all you need to do is keep track of a single positive offset to know where the top of your stack is.

Implementing a queue directly is more difficult... you are adding items to one end but pulling them off of the other. Two stacks gives you a way to do it.

But why 3 queues?

Because this algorithm (if it exists) ensures that there is a constant bound on the time complexity of a queue operation. With our 2-stack solution on average each item takes O(1) time, but, if we have a really big stack, once in a while there'll be an operation that takes a long time. While that's happening the car crashes, the rocket blows up, or your patient dies.

You don't want a crummy algorithm that gives unpredictable performance.

You want guarantees.

This StackOverflow answer explains that a 3-stack solution isn't known, but that there is a 6-stack solution.

Why Stacks From Deques

Let's return to your first question. As we've seen, there are good reasons to be able to build queues from stacks. For a computer it's a natural way of building a complex data structure from a simple one. It can even offer us performance guarantees.

Stacks from Dequeues doesn't strike me as being practical in a computer. But computer science isn't about computers; it's about finding efficient algorithmic solutions to problems. Maybe you're storing stuff on a multi-directional conveyor belt in a factory. You can program the belt to act like a dequeue and use the dequeue to make stacks. In this context the question makes more sense.

Answer 2

Seems there is no practical usage for these implementations.

The main purpose is to encourage student to invent complex solutions using simple tools - important skill for every qualified developer.

(perhaps the secondary goal is to teach programmer to implement ridiculous visions of the boss :))

Answer 3

That first problem looks more like it's designed as an exercise than as anything else. I doubt that there are many cases where you'd want to implement two stacks using a single deque, though I'm happy to be proven wrong. I think the purpose of the question, though, is to get you to think about the "geometry" of deques and stacks. There's a really beautiful solution to the problem that's quite elegant, and if you see how it works it'll give you a much deeper appreciation for how all these types work.

To your second question - in imperative programming languages, there isn't much of a reason to implement a queue with three stacks. However, in functional programming languages like Lisp, typically, stacks are fairly simple to implement, but it's actually quite difficult to get a queue working with a constant number of operations required per operation. In fact, for a while, if I remember correctly, it was believed that this simply wasn't possible. You could implement a queue with two stacks (this is a very common exercise, and it's actually a really good one because the resulting queue is extremely fast), but this usually only gives good amortized performance rather than good worst-case performance, and in functional languages where amortization is either not a thing or much harder to achieve this isn't necessarily a good idea. Getting a queue out of three stacks with constant complexity is a Big Deal, then, as it unlocks the ability to use a number of classical algorithms that rely on queues that otherwise wouldn't be available in a functional context.

But again, in both cases, these are primarily designed as exercises to help you build a better understanding of the fundamentals. Would you actually do either of these things in practice? Probably not - some library designer will likely do it for you. But will doing these exercises give you a much deeper understanding of how these data types work, the sorts of things they're good and bad at, and an appreciation for how hard library designers have to work? Yes, totally!