Question: Suppose that some application requires using two stacks whose elements are of the same type. A natural storage structure of such a two-stack data type would consist of two arrays and two top pointers. Explain why this may not be a spacewise efficient implementation.

Answer: 
I think that what this question is getting at is that if you want to represent two stacks simultaneously, it's possible to do so using a single array of elements. In a typical array implementation of a stack, the elements are stored in an array with some amount of "slack space" available for growth. When that space is exhausted, the array is increased in size (usually by doubling to get amortized O(1) insertions), the old elements are copied over, and growth can continue.

This approach works very well, but if you know that you're going to have two stacks it can be made a bit better. In particular, suppose that you have two stacks, each of which has some "slack space," and one of the stacks runs out of slack space. If this happens, it would be really great if it would be possible to use some of the unused slack space from the other stack to continue growing the first stack. This would save us an extra allocation/copy and would allow us to make more efficient use of the space we have available.

One way you can do this, if you have two stacks, is to have the two of them share an array and grow from opposite sides inward. For example, if I have one stack with elements `1 2 3` and another with elements `4 5 6`, then this might have the following representation in memory:

```
[1] [2] [3] [ ] [ ] [6] [5] [4]

```

If we push a value onto the first stack, say, `9`, we grow the stack like this:

```
[1] [2] [3] [9] [ ] [6] [5] [4]

```

If we push a value onto the second stack, say, `0`, we grow its stack as

```
[1] [2] [3] [9] [0] [6] [5] [4]

```

If we now need to grow either stack by pushing a value, then we would use the standard reallocation technique to move it to a larger array. The advantage, though, is that if one stack is mostly empty and the other is fairly large, then we can get very good usage out of our memory. For example, here's one possible stack configuration:

```
[1] [2] [3] [4] [5] [6] [ ] [0]

```

Here, one stack has six values and one stack has just one. Notice that we're using our space very efficiently by sharing the array.
If the arrays are allocated dynamically then the only possible way of that implementation being size-inefficient is not taking into account intersection between them. It can be taken into account by using algorithms like Huffman compression. On the other hand, if the arrays are allocated statically, that can be really inefficient, because the stack may differ in size considerably. One can solve such a problem by using just *one* array for *two* stacks.