There are 2 methods to solve this problem.
1. Divide the array into 2 halves and allot equal space to both the stacks.
2. Start the array from the extreme ends.
1. Dividing the array into 2 halves
We will divide the array into 2 parts. Then allot first half of the array to the first stack and the rest half to the 2nd stack.
For example: arr[0] to arr[n/2] for stack1 and arr[n/2+1] to arr[n-1] for stack2. n is the size of the array.
Problem with the method: Inefficient use of the array space. Push operation can result in an overflow of stack even if there is space available.
For example, array size is 8 and we push 4 elements to stack1 and do not push any data to stack2. When we push the 5th element to stack1, there will be overflow even if there is space for 4 more elements.
class twoStacks{
int* arr; int size; int top1, top2;
}
public : twoStacks(int n)
{ size=n; arr=new int[n];
top1=n/2+1; top2= n/2;
}
//push method for stack1
void push1(int element)
{ //check overflow condition
if(top>0) {
top1--; arr[top1]=element;
}
else {
cout<<"stack overflow"<<"by element:"
<<x<<endl; return;
}
} //push1 ends
//push2 for stack2
void push2(int element)
{ if(top2<size-1 {
top2++; arr[top2]= element;
}
else {
cout<<"stack overflow "<<"by element:"<<x<<endl; return;
}
} //push2 ends
//pop1 for stack1
int pop1(){
if(top<=size/2) {
int element= arr[top1]; top1++ ; return element;
}
else {
cout<<"stack underflow" ; exit(1);
}
}
void pop2() {
if(top2>=size/2+1)
{ int element= arr[top2]; top2--; return element;
}
else {cout<<"stack underflow"; exit(1);}
}
int main()
{ twoStacks ts(5); ts.push1(5); ts.push2(10);
ts.push2(15); ts.push1(11); ts.push2(7);
cout<<""popped element from stack1 is"<<":"<<ts.pop1()<<endl;
ts.push2(40);
cout<<"\npopped element from stack2 is"<<":"<<ts.pop2()<<endl;
return 0;
}
Result:
Stack Overflow By element :7
Popped element from stack1 is : 11
Stack Overflow By element :40
Popped element from stack2 is : 15
2. Method2: Stating the stacks from the extremes
In this method, we will start the stack1 from the left and the stack2 from the right. In this way the first element is pushed at index0 and the first element in stack2 is pushed at index n-1.
Both the stacks grow or shrink in the opposite direction.
Code:
class twoStacks{
int *arr; int size; int top1, top2;
}
public:
twoStacks(int n) //constructor
{ size=n; arr= new int[n]; top1=-1;
top2= size;
}
//push1 for stack1
void push1(int element)
{ //therer is atleast 1empty space for the new element
if(top1< top2-1)
{top1++; arr[top1]=element;}
else
{cout<<"stack overflow"; exit(1);}
} //push1 ends
//push2 for stack2
void push2(int element)
{ //there is atlesast one emptyspace for the new element
if(top1<to2-1)
{top2--; arr[top2]=element;}
else
{cout<<"stack overflow"; exit(1);}
} //push2 ends
//pop1 for stack1
int pop1()
{
if (top1>0=)
{int element= arr[top1];
top1--; return element;
}
else
{ cout<<"stack underflow"; exit(1);}
}
//pop2 for stack2
int pop2()
{
if(top2<size)
{int element= arr[top2];
top2++; return element;
}
else{cout<<"stack underflow"; exit(1);}
}
int main()
{
twoStacks ts(5); ts.push1(5); ts.push2(10);
ts.push2(15); ts.push1(11); ts.push2(7);
cout<<"popped element from stack1 is"<<ts.pop1();
ts.push2(40);
cout<<"\npopped element from stack2 is"<<ts.pop2();
return 0;
}
Reference
https://www-geeksforgeeks-org.cdn.ampproject.org/v/s/www.geeksforgeeks.org/implement-two-stacks-in-an-array/amp/?amp_js_v=a2&_gsa=1&usqp=mq331AQHKAFQArABIA%3D%3D#aoh=16121771215341&referrer=https%3A%2F%2Fwww.google.com&_tf=From%20%251%24s&share=https%3A%2F%2Fwww.geeksforgeeks.org%2Fimplement-two-stacks-in-an-array%2F
