Build two stacks using single array one is forward direction and is backward?

Question

I was trying to get maximum rectangle area for a given histogram but I used brute force approach which have O(n^2) time complexity so I want some better solution using stack so that we could reduce time complexity to O(n) or O(log n ).

Answer 1

Two stacks implementation is a very common question in interview. Where one stack will move from top to bottom starting from top and another one moves from bottom to top starting from bottom. Here is the sample class which may be helpful for two stack implementation (everything is self explanatory nothing complex) -

class two_stacks
{
    int *arr;
    int size;
    int top1, top2;

public:
   two_stacks(int n)  // constructor
   {
       size = n;
       arr = new int[n];
       top1 = -1;
       top2 = size;
   }

   // Method to push an element x to stack1
   void push1(int x)
   {
       // There is at least one empty space for new element
       if (top1 < top2 - 1)
       {
           top1++;
           arr[top1] = x;
       }
       else
       {
           cout << "Stack Overflow";
           exit(1);
       }
   }

   // Method to push an element x to stack2
   void push2(int x)
   {
       // There is at least one empty space for new element
       if (top1 < top2 - 1)
       {
           top2--;
           arr[top2] = x;
       }
       else
       {
           cout << "Stack Overflow";
           exit(1);
       }
   }

   // Method to pop an element from first stack
   int pop1()
   {
       if (top1 >= 0 )
       {
          int x = arr[top1];
          top1--;
          return x;
       }
       else
       {
           cout << "Stack UnderFlow";
           exit(1);
       }
   }

   // Method to pop an element from second stack
   int pop2()
   {
       if (top2 < size)
       {
          int x = arr[top2];
          top2++;
          return x;
       }
       else
       {
           cout << "Stack UnderFlow";
           exit(1);
       }
   }
};

Answer 2

First things If you don't want to use array, LinkedList is better option as you can make it easily according to question (leaving array) with two operation
1. Insert At first, Delete at First and Top_FirstElement
2. Insert at last, Delete at last and top_lastElement
and using array:

int array[SIZE];
//access the same array by dividing its size by 2
topForward=SIZE/2+1;

function ForwardElementPush(topForward, InputValue){
  if(top<=SIZE)
    set topForward=top+1;
  array[topForward]=InputValue;
}

topBackward=SIZE/2;
function BackwardElementPush(topBackward,InputValue){
  if(topBackward!=-1)
    topBackward--;
  array[topBackward]=InputValue;
}