# 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 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());
}
}
```

Popped element from stack1 is 11

Popped element from stack2 is 40

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