implementing two stacks using one array

 This C Program Implements two Stacks using a Single Array & Check for Overflow & Underflow. The task is to create a data structure twoStacks that represents two stacks. Implementation of twoStacks should use only one array, i.e., both stacks should use the same array for storing elements. Following functions must be supported by twoStacks.

To implement two stacks in one array, there can be two methods.

*First is to divide the array in to two equal parts and then give one half two each stack. But this method wastes space.

*So a better way is to let the two stacks to push elements by comparing tops of each other, and not up to one half of the array.Push and Pop functions of both stack in the following code has their Time Complexity as O(1). They take constant time.

push1(int x) --> pushes x to first stack.

push2(int x) --> pushes x to second stack.

pop1() --> pops an element from the first stack and return the popped element.

pop2() --> pops an element from the second stack and return the popped element.

Below the space-efficient implementation:

c++:

// C++ program to implement two stacks
// in one Array

#include<iostream>
#include<stdlib.h>

using namespace std;

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

    public:
    twoStacks(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);
        }
    }
};


// Driver Program
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;
}

java:

// Java program to implement two stacks in a
// single array

class TwoStacks
{
    int size;
    int top1, top2;
    int arr[];

    // Constructor
    TwoStacks(int n)
    {
        arr = new int[n];
        size = 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
        {
            System.out.println("Stack Overflow");
            System.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
        {
            System.out.println("Stack Overflow");
            System.exit(1);
        }
    }

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

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

        }
        return 0;
    }

    // Driver program to test twoStack class
    public static void main(String args[])
    {
        TwoStacks ts = new TwoStacks(5);
        ts.push1(5);
        ts.push2(10);
        ts.push2(15);
        ts.push1(11);
        ts.push2(7);
        System.out.println("Popped element from" +
                           " stack1 is " + ts.pop1());
        ts.push2(40);
        System.out.println("Popped element from" +
                         " stack2 is " + ts.pop2());
    }
}

output:

Popped element from stack1 is 11
Popped element from stack2 is 40

The time complexity of all of the four push and pop operations of both stacks is O(1).