1.
Introduction
1.1.
Problem Statement
1.2.
Sample Example
2.
Brute Force Approach
2.1.
Pseudocode
2.2.
Implementation in C++
2.3.
Implementation in Python
2.4.
Complexity Analysis
3.
Optimized Approach
3.1.
Pseudocode
3.2.
Implementation in C++
3.3.
Implementation in Python
3.4.
Complexity Analysis
4.
4.1.
What is the condition of overflow and underflow in a stack?
4.2.
What is the time complexity of pop() and push() operations?
4.3.
How many queues are required to implement a stack?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

# Two stacks in an array

## Introduction

In this blog, we will look at the approach to store the elements of two stacks in an array, i.e. both the stacks will be using the same array for storing elements.

### Problem Statement

Given: Two stacks with elements

Problem: Store the value of the two stacks in an array such that both stacks use the same array for storing elements.

### Sample Example

Let us look at an example to understand the given problem.

The given stacks are:

``````Stack 1 - 1  2  3  4  5
Stack 2 - 6  7  8  9``````

Total elements are 9 and they will be stored in such a manner that stack 1 will occupy the indices from 0 to 4(n/2) and stack 2 will occupy the indices from 5 (n/2) to 8 (n-1).

In this way the array of 9 elements will be used to store the elements of both the stacks.

## Brute Force Approach

In this approach, we will divide the array into two sub-arrays and then store the elements. The array will be divided into two equal subarrays if the number of elements are even, and if the number of elements are odd then the left subarray will have n/2 elements and the right subarray will have n/2+1 elements.

### Pseudocode

The pseudocode to implement two stacks in an array is as follows:

1. Store the elements in the two stacks and initialize an array with the total number of elements in both the stacks.
2. Run a loop to divide the array into two halves, from ar[0] to a[n/2] for stack1 and from ar[n/2 + 1] to ar[n-1] for stack2.
3. Iterate over the loops and perform push and pop operations for stack throughout the loop for every element and store it in the array.
4. When all the elements are stored in either of the stack, then store the remaining elements from another stack.

### Implementation in C++

``````// Program to implement two stacks in an array/list
#include <iostream>
#include <stdlib.h>

using namespace std;

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

public:
twoStacks(int n)
{
size = n;
ar = new int[n];
top1 = n / 2 + 1;
top2 = n / 2;
}

void push1(int x)
{
if (top1 > 0) {
top1--;
ar[top1] = x;
}
else {
cout << "Stack Overflow"
<< " By element :" << x << endl;
return;
}
}

void push2(int x)
{
if (top2 < size - 1) {
top2++;
ar[top2] = x;
}
else {
cout << "Stack Overflow"
<< " By element :" << x << endl;
return;
}
}

int pop1()
{
if (top1 <= size / 2) {
int x = ar[top1];
top1++;
return x;
}
else {
cout << "Stack UnderFlow";
exit(1);
}
}

int pop2()
{
if (top2 >= size / 2 + 1) {
int x = ar[top2];
top2--;
return x;
}
else {
cout << "Stack UnderFlow";
exit(1);
}
}
};

int main()
{
twoStacks ts(5);
ts.push1(5);
ts.push2(10);
ts.push2(16);
ts.push1(13);
ts.push2(6);
cout << "Popped element from stack1 is "
<< " : " << ts.pop1()
<< endl;
ts.push2(12);
cout << "\nPopped element from stack2 is "
<< ": " << ts.pop2()
<< endl;
return 0;
}``````

### Implementation in Python

``````# Program to implement two stacks in an array/list
import math

class twoStacks:

def __init__(self, n):
self.size = n
self.ar = [None] * n
self.top1 = math.floor(n/2) + 1
self.top2 = math.floor(n/2)

def push1(self, x):

if self.top1 > 0:
self.top1 = self.top1 - 1
self.ar[self.top1] = x
else:
print("Stack Overflow by element : ", x)

def push2(self, x):

if self.top2 < self.size - 1:
self.top2 = self.top2 + 1
self.ar[self.top2] = x
else :
print("Stack Overflow by element : ", x)

def pop1(self):
if self.top1 <= self.size/2:
x = self.ar[self.top1]
self.top1 = self.top1 +1
return x
else:
print("Stack Underflow ")
exit(1)

def pop2(self):
if self.top2 >= math.floor(self.size/2) + 1:
x = self.ar[self.top2]
self.top2 = self.top2 - 1
return x
else:
print("Stack Underflow ")
exit(1)

# Main program
ts = twoStacks(5)
ts.push1(5)
ts.push2(10)
ts.push2(16)
ts.push1(13)
ts.push2(6)

print("Popped element from stack1 is : " + str(ts.pop1()))
ts.push2(12)
print("Popped element from stack2 is : " + str(ts.pop2()))``````

Output:

``````Stack Overflow By element :6
Popped element from stack1 is  : 13
Stack Overflow By element :12
Popped element from stack2 is : 16``````

### Complexity Analysis

Time Complexity - We have traversed over n elements and therefore, the time complexity is O(n).

Space Complexity - The auxiliary space is used for n elements and therefore, the space complexity is O(n).

## Optimized Approach

In this approach, the starting index of both stacks is chosen as the extreme corners of the stack, i.e. from the leftmost and rightmost corner indices. Iteration is continued for every element and the array starts to shrink towards the middle while storing elements. The space between the top elements of the stacks is checked and if there is space, the elements are stored in those indices.

### Pseudocode

The pseudocode for this approach is similar to the brute force approach with the difference that the loop iterations start from 0 for stack1 and from (n-1) for stack2.

### Implementation in C++

``````// Program to implement two stacks in an array
#include <iostream>
#include <stdlib.h>

using namespace std;

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

public:
twoStacks(int n)
{
size = n;
ar = new int[n];
top1 = -1;
top2 = size;
}

void push1(int x)
{
if (top1 < top2 - 1) {
top1++;
ar[top1] = x;
}
else {
cout << "Stack Overflow";
exit(1);
}
}

void push2(int x)
{
if (top1 < top2 - 1) {
top2--;
ar[top2] = x;
}
else {
cout << "Stack Overflow";
exit(1);
}
}

int pop1()
{
if (top1 >= 0) {
int x = ar[top1];
top1--;
return x;
}
else {
cout << "Stack UnderFlow";
exit(1);
}
}

int pop2()
{
if (top2 < size) {
int x = ar[top2];
top2++;
return x;
}
else {
cout << "Stack UnderFlow";
exit(1);
}
}
};

int main()
{
twoStacks ts(5);
ts.push1(5);
ts.push2(10);
ts.push2(16);
ts.push1(13);
ts.push2(6);
cout << "Popped element from stack1 is "
<< ts.pop1();
ts.push2(12);
cout << "\nPopped element from stack2 is "
<< ts.pop2();
return 0;
}``````

### Implementation in Python

``````# Python Script to Implement two stacks in a list
class twoStacks:

def __init__(self, n):
self.size = n
self.ar = [None] * n
self.top1 = -1
self.top2 = self.size

def push1(self, x):

if self.top1 < self.top2 - 1 :
self.top1 = self.top1 + 1
self.ar[self.top1] = x

else:
print("Stack Overflow ")
exit(1)

def push2(self, x):

if self.top1 < self.top2 - 1:
self.top2 = self.top2 - 1
self.ar[self.top2] = x

else :
print("Stack Overflow ")
exit(1)

def pop1(self):
if self.top1 >= 0:
x = self.ar[self.top1]
self.top1 = self.top1 -1
return x
else:
print("Stack Underflow ")
exit(1)

def pop2(self):
if self.top2 < self.size:
x = self.ar[self.top2]
self.top2 = self.top2 + 1
return x
else:
print("Stack Underflow ")
exit()

# Main program
ts = twoStacks(5)
ts.push1(5)
ts.push2(10)
ts.push2(16)
ts.push1(13)
ts.push2(6)

print("Popped element from stack1 is " + str(ts.pop1()))
ts.push2(12)
print("Popped element from stack2 is " + str(ts.pop2()))``````

Output:

``````Popped element from stack1 is 13
Popped element from stack2 is 12``````

### Complexity Analysis

Time Complexity - We have traversed over n elements and therefore, the time complexity is O(n).

Space Complexity - The auxiliary space is used for n elements and therefore, the space complexity is O(n), but the space is used more efficiently in this approach.

Check out this problem - Search In Rotated Sorted Array

### What is the condition of overflow and underflow in a stack?

Removing elements from an empty stack is called stack underflow and adding elements to a full stack is called stack overflow.

### What is the time complexity of pop() and push() operations?

O(1) is the time complexity of pop() operation as it accesses only one end of the stack and the same is the case for push() operations.

### How many queues are required to implement a stack?

To implement a stack using enqueue and dequeue operations, we require two queues.

## Conclusion

In this blog, we have discussed the approach to implement two stacks in an array where both the stacks use the same array for storing elements.

Recommended problems -

Refer to our guided paths on Coding Ninjas Studio to upskill yourself in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem Design, and many more! If you want to test your competency in coding, you may check out the mock test series and participate in the contests hosted on Coding Ninjas Studio! But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, Uber, etc; you must have a look at the problemsinterview experiences, and interview bundle for placement preparations.

Nevertheless, you may consider our paid courses to give your career an edge over others!

Do upvote our blogs if you find them helpful and engaging!

Happy Learning!

Live masterclass