Implement two stacks in an array

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
Write a Comment

Leave a Comment

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