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

78 views
Build two stacks using single array one is forward direction and is backward? posted Feb 3, 2016

+1 vote

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 Feb 4, 2016

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;
}
`````` answer Feb 3, 2016
Similar Questions