What is fork. How are processes created using fork
January 12, 2013
Find size of a struct without using sizeof operator
January 14, 2013

Implement two stacks in one array

Given a linear memory (in the form of an array). Implement two stacks such that memory is used in an optimal manner. i.e if user wants to push an element in either of the two stacks, then the implementation should not give error until the entire array is full (So cannot use half array for first stack and half for second).
Obviously, dividing the array in two parts and using one part for one Stack will not work. 

Let us use the first half for Stack-1 and second half for Stack-2. If the user only push in Stack-2 and does not use Stack-1 at all. Then after some time Stack-2 will be full and user will not be allowed to push in Stack-2. But half of the Array (used by Stack-1) is still empty. So this is not efficient usage of memory.


Solution:

The idea is to have two Stacks growing in opposite direction (toward each other).

The first Stack (top1) will grow in forward direction and second stack (top2) will grow in the backward direction.

If array has 100 elements, then initially,

top1 = -1
top2 = 100

to indicate that the two stacks are empty.

In this case user will be able to insert 10 elements in first stack and 90 in second or 50 in first and 50 in second or in any ratio (as long as the total number of elements is <= 100). If user inserts in only one stack, then the entire array will be used by that stack.

Hence, memory is used in an optimized manner.

The Empty Condition for two stacks are as follows:

// EMPTY condition for FORWARD Stack
if (top1 == -1)
    ... Forward Stack is Empty
// EMPTY condition for BACKWARD Stack
if(top2 == 100)
    .. Backward Stack is Empty

None of the two stacks will be full unless all the 100 memory locations in the array are used. Hence the FULL condition for both the stacks will be

// FULL condition for BOTH Stacks
if (top1 == top2-1)
    ... Both the stacks are full

The Push and Pop operation for the two stacks should move the pointer in reverse direction. For Example: After pushing element in Stack-1 (Forward) top1 will INCREMENTED, and after pushing element in Stack-2 (BACKWARD Stack), top2 will be DECREMENTED.

Code:

#define FORWARD 1
#define BACKWARD 2
int arr[100];
int top1 = -1;
int top2 = 100;
/**
 * If popping from Stack-1 (Forward Stack) Then
 *     return arr[top1] and DECREMENT top1
 * If popping from Stack-2 (Backward Stack) Then
 *     return arr[top2] and INCREMENT top2
 */
int pop(int stackNo)
{
    if(stackNo == FORWARD)
    {
        // Forward Stack Empty
        if(top1 == -1)
            return -1;
        else
            return arr[top1--];
    }
    else
    {
        // Backward Stack Empty
        if(top2 == 100)
            return -1;
        else
            return arr[top2++];
    }
}
/**
 * If Forward Stack (stackNo == FORWARD)
 *     Push an element into FORWARD Stack
 * Else
 *     Push an element into BACKWARD Stack
 *
 * return false if unable to push (because array is full)
 * return true is push is successful.
 */
bool push(int stackNo, int value)
{
    // If Both the stacks are full
    if(top1 == top2-1)
        return false;
    if(stackNo == FORWARD)
        // Pushing in FORWARD Stack
        arr[++top1] = value;
    else
        // Pushing in BACKWARD stack
        arr[--top2] = value;
}

 I am sure you can write the others functions like isEmpty etc.

2 Comments

  1. Shailesh says:

    thank you for explanation and code…

  2. Anshul says:

    Best explanation ever

Leave a Reply

Your email address will not be published. Required fields are marked *