Problem Statement:
You need to create a data structure called two_stacks that represents 2 stacks.
It should use only one array.
Both stacks should use the same array to store the elements.
Below are the functions to be created:
push_1(int x) -> should push element ‘x’ into first stack
push_2(int x) -> should push element ‘x’ into second stack
pop_1() -> pop element from the first stack and return the element.
pop_2() -> pop element from the second stack and return the element.
Solution
We can solve this problem using multiple methods:
Method 1:
In this method we divide the array into two halves and assign the first half to stack 1 and next half to stack 2.
The problem in this is, inefficient use of array space.
Method 2:
This is an space efficient version.
In this method, we start two stacks from two extreme corner.
i.e stack_1 will start from index 0 and stack_2 will start from index(n-1)
Solution in C++
#include <algorithm>
//visit www.ProDeveloperTutorial.com for 450+ solved questions
#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <stack>
using namespace std;
using namespace std;
class two_stacks_method_1
{
int *arr;
int size;
int top1, top2;
public:
// Constructor
two_stacks_method_1(int n)
{
size = n;
arr = new int[n];
top1 = n / 2 + 1;
top2 = n / 2;
}
void push1(int x)
{
if (top1 > 0)
{
top1--;
arr[top1] = x;
}
else
{
cout << "Stack Overflow" << endl;
return;
}
}
void push2(int x)
{
if (top2 < size - 1)
{
top2++;
arr[top2] = x;
}
else
{
cout << "Stack Overflow" << endl;
return;
}
}
int pop1()
{
if (top1 <= size / 2)
{
int x = arr[top1];
top1++;
return x;
}
else
{
cout << "Stack UnderFlow"<<endl;
exit(1);
}
}
int pop2()
{
if (top2 >= size / 2 + 1)
{
int x = arr[top2];
top2--;
return x;
}
else {
cout << "Stack UnderFlow"<<endl;
exit(1);
}
}
};
class two_stacks_space_optimized
{
int* arr;
int size;
int top1, top2;
public:
two_stacks_space_optimized(int n)
{
size = n;
arr = new int[n];
top1 = -1;
top2 = size;
}
void push1(int x)
{
if (top1 < top2 - 1)
{
top1++;
arr[top1] = x;
}
else {
cout << "Stack Overflow"<<endl;
exit(1);
}
}
void push2(int x)
{
if (top1 < top2 - 1) {
top2--;
arr[top2] = x;
}
else {
cout << "Stack Overflow"<<endl;
exit(1);
}
}
int pop1()
{
if (top1 >= 0)
{
int x = arr[top1];
top1--;
return x;
}
else {
cout << "Stack UnderFlow"<<endl;
exit(1);
}
}
int pop2()
{
if (top2 < size)
{
int x = arr[top2];
top2++;
return x;
}
else {
cout << "Stack UnderFlow"<<endl;
exit(1);
}
}
};
int main()
{
two_stacks_method_1 ts_m1(7);
ts_m1.push1(1);
ts_m1.push2(2);
ts_m1.push1(4);
ts_m1.push2(5);
cout << "Element popped from stack1 is "
<< " : " << ts_m1.pop1()
<< endl;
ts_m1.push2(50);
cout << "Element popped from stack2 is "
<< ": " << ts_m1.pop2()
<< endl;
two_stacks_space_optimized ts_m2(5);
ts_m2.push1(10);
ts_m2.push2(20);
ts_m2.push2(30);
ts_m2.push1(40);
ts_m2.push2(50);
cout << "\n\nElement popped from stack1 is "
<< ts_m2.pop1()<<endl;
ts_m2.push2(60);
cout << "Element popped from stack2 is "
<< ts_m2.pop2();
return 0;
}
Output:
Element popped from stack1 is : 4
Element popped from stack2 is : 50
Element popped from stack1 is 40
Element popped from stack2 is 60