Two stacks with a deque, what's the purpose of implementing it?
An answer to this question on Stack Overflow.
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: https://stackoverflow.com/questions/5538192/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
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.