How to implement two stacks in one array?

I want to begin by saying that this is NOT a homework question. I am reading Introduction to Algorithms - the famous CLRS text to become a better programmer. I am trying to solve the problems and exercises given in the book by myself.

I am trying to solve Excercise 10.1-2 from Chapter 10 Elementary Data Structures from CLRS Second Edition. Here is what its states:

Explain how to implement two stacks in one array A[1..n] in such a way that neither stack overflows unless the total number of elements in both stacks together is n. The PUSH and POP operations should run in O(1) time.

The solution that I have come up with so far is:

Let array A[1..n] implement two stacks: S1[1..i] and S2[i..n].

For the PUSH-S1 and PUSH-S2 operations, if the stack is 'full' then start pushing elements into the other stack (eg. if stack S1 is full when a new element is trying to be pushed in, then push that element into stack S2 and vice versa).

The problem with this approach is I will not be able to POP-S1 or POP-S2 reliably as there is no way of 'remembering' which element belongs to which stack. If the elements of the stack are (key,value) pairs, the key being the stack number, then to pop an element I would have to search, in the worst case, i or (n-i) times - which will be O(n) (feel free to correct me if I am wrong here), which would not be O(1).

I have been banging my head on the question for quite a while now. Am I on the right track? Can someone give my possible pointers for solving this problem?

In general, how should I 'think' about these problems? Or can only really intelligent people solve these types of problems? Will tackling/solving problems like these (i.e. gaining experience) help me become better at this?

I await enlightenment.

• "Will tackling/solving problems like these (i.e. gaining experience) help me become better at this?" In my experience, this is definitely the case. If nothing else, you will have thought in multiple ways about the problem, and by that alone develop more insight. As I was recently told: the best way to have good ideas is to have many ideas. – G. Bach Jul 28 '13 at 15:15

Another hint in addition to what Yuval said: it helps to place the stacks in a specific way in the arrays and fix their direction of growth accordingly. They don't have to grow in the same direction.

Here are some hints:

1. One of the stacks should grow "up" and the other "down".
2. There is no way of 'remembering' which element belongs to which stack - you are allowed to use additional variables to help you with stuff like that. (This makes more sense with the solution proposed by the first hint.)

The first stack starts at 1 and grows up towards n, while the second starts form n and grows down towards 1. Stack overflow happens when an element is pushed when the two stack pointers are adjacent.

This method efficiently utilizes the available space. It doesn’t cause an overflow if there is space available in arr[]. The idea is to start two stacks from two extreme corners of arr[]. stack1 starts from the leftmost element, the first element in stack1 is pushed at index 0. The stack2 starts from the rightmost corner, the first element in stack2 is pushed at index (n-1). Both stacks grow (or shrink) in opposite direction. To check for overflow, all we need to check is for space between top elements of both stacks.

I thought of another solution. If we split the array into half (or as close as possible if the array has odd length) and make the first element go into the first stack and the second element go into the second stack. While popping we could retrace these steps. However, by implementing in this way would it violate any stack principle?

• Welcome to Computer Science! Unfortunately, your proposal doesn't work. In an array of length $N$, you're supposed to be able to store two stacks that won't overflow unless their total size exceeds N (so it should be able to cope with an empty stack and a stack of length $N$). Your solution overflows if either one of the stacks exceeds $N/2$. – David Richerby Jan 10 '15 at 15:08

Some hints

Make an array

Array elements with odd index are for stack1

Array elements with even index are for stack2

Now You can grow both stacks from left to right direction

Just keep variables that maintain top position of both stacks. You won't have to search the array.

and if stack1 becomes full while stack2 is empty you can keep track for additional stack1 elements in the stack2 by maintaining some variables

• This is very convoluted. The existing answers already give much simpler ways of solving the problem – David Richerby Jan 10 '15 at 17:14