How to implement two stacks in one array?

Question

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.

Answer 1

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.

Answer 2

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.)

Answer 3

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.

Answer 4

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.

Answer 5

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?

Answer 6

I guess there are many solutions to this problem. For the particular case of 2 stacks in one array, I like the solution of starting one stack at the first index and the second one at the last index. As the stacks grow, you know the array is full when the heads of each stack are adjacent.

However, you could implement this the same way as implementing K stacks in 1 array. If you store a queue with the free slots available, you have everything you need. For instance, you would know in which slot you would add your next value (independently from the stack you are pushing to). Everytime you push or pop a value, you pop or push a free slot, respectively. Storing such a queue might be considered overhead, still, the space complexity would remain the same.

The only thing you would have to do is to properly set the pointers (or indexes, after all, we are using an array).

Here is a short description, space complexity O(N) where N is the size of the array. Pop/push complexities O(1).

1) initialize a queue holding the free slots from 0 to N - 1.
2) initialize the heads of all the stacks to -1 (the stacks are empty)
3) POP: given a stack, set the head of that stack to the next element
   pointed to by the current head, and then remove the current head.
   Enqueue the index of the slot which just came free to the queue of free slots.
4) ADD: get the next available index from the queue of free slots.
   Create your new node in the new slot, and make it point to the current 
   head of that stack. Then set the current head of that stack to the newly added node.

Answer 7

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