Implement Two Stacks in a Single Array
“Implement Two Stacks in a Single Array” is a popular technical interview problem based on stack data structure. Here, we are given an array of size ‘n’ and our task is to implement two stacks in a single array.
We need to ensure that the space in an array is maximally utilized.
This problem is quite tricky one and requires some basic thinking.
METHOD 1: Dividing the Array into Two Halves To Implement two stacks in a single array
The Brute-Force Solution to Implement two stacks in a single array is, that, we can divide the given array into two halves and allocate first half of the array to implement first stack and second half of the array to implement second stack.
For example, If the array size is 1000(0 to 999). Then, we can reserve indexes from 0 to 499 to implement first stack, and indexes from 500 to 999 to implement second stack.
This Approach seems quite simple and efficient, but there is a problem in this approach. Suppose, we need to push 600 elements into first stack and 30 elements into second stack. Now, for first stack, we can only push at max 500 elements because, we already defined the limit. For second stack, we can easily push 30 elements into the stack.
Previously, we had total space to store 1000 elements.
Total Elements inserted into first stack is 500 and total elements inserted into second stack is 30. So, 1000 – (500+30) = 470 is still available and still we cannot insert 100 left out elements which are needed to be pushed into first stack.
So, here, using the following approach, we are wasting the space and also, we are not able to push elements into stack, when array space is still available. Therefore, we are not utilizing the space efficiently.
METHOD 2: Pushing Elements into Array from Extreme End (A Space Efficient Approach) To Implement Two Stacks in a Single Array
This Method to implement two stacks in a single array is space efficient method and utilises the array space efficiently. In this method, we push the elements into the stacks from extreme ends (‘0’ and ‘n-1’) of the array and grow the stack accordingly.
For example:
There is an array of size 1000. Now, if we want to push 600 elements into first stack and 30 elements into second stack, we can easily store these into array as:
- From index 0 to 599, elements of first stack will be pushed.
- From index 999 to 970(in reverse order), elements of the second stack will be pushed.
And, for Pop Operation also, both the stack will pop out the elements in opposite direction.
In this approach, an overflow condition occurs only if the space is fully utilized and there will be no space in an array to push an element from either of stack.
C++ Program to Implement Two Stacks in a Single Array is as follows:
/* C++ Program to Implement Two Stacks in a Single Array */
#include<bits/stdc++.h>
using namespace std;
/* Class to Implement Two Stack */
class implementTwoStacks
{
int *arr;
int size;
int top1; /* Variable to monitor top of first stack */
int top2; /* variable to monitor top of second stack */
public:
/* Constructor */
implementTwoStacks(int n)
{
size = n;
arr = new int[size]; /* Dynamically Allocating Memory to First Stack */
top1 = -1; /* Initial Top of First Stack */
top2 = n; /* Initial Top of Second Stack */
}
/* Method to Push an Element into First Stack */
void pushFirst(int ele)
{
/*
Check Overflow Condition!!
Check if there is a space left in the array, where an
Element can be pushed.
*/
if(top2 > top1 + 1)
{
top1++;
arr[top1] = ele;
}
else
{
cout<<"Array is Already Full!! No More Elements can be pushed Now!!\n";
}
}
/* Method to Push an Element into Second Stack */
void pushSecond(int ele)
{
/*
Check Overflow Condition!!
Check if there is a space left in the array, where an
Element can be pushed.
*/
if(top2 > top1 + 1)
{
top2--;
arr[top2] = ele;
}
else
{
cout<<"Array is Already Full!! No More Elements can be pushed Now!!\n";
}
}
/* Method to Pop an Element from First Stack */
int popFirst()
{
/* Check Underflow Condition */
if(top1 == -1)
{
cout<<"The First Stack is empty!! Nothing to Pop Out!!\n";
exit(1);
}
else
{
int ele = arr[top1];
top1--;
return ele;
}
}
/* Method to Pop an Element from Second Stack */
int popSecond()
{
/* Check Underflow Condition */
if(top2 == size)
{
cout<<"The Second Stack is empty!! Nothing to Pop Out!!\n";
exit(1);
}
else
{
int ele = arr[top2];
top2++;
return ele;
}
}
};
int main()
{
implementTwoStacks Stack(100); /* Creating an array of size 100 */
/* Pushing Some Elements into First Stack */
Stack.pushFirst(1);
Stack.pushFirst(2);
Stack.pushFirst(3);
Stack.pushFirst(4);
/* Pushing Some Elements into Second Stack */
Stack.pushSecond(5);
Stack.pushSecond(6);
Stack.pushSecond(7);
Stack.pushSecond(8);
/* Popping and Printing Some Elements from First Stack */
cout<<"\nThe Popped Elements of First Stack is "<<Stack.popFirst();
cout<<"\nThe Popped Elements of First Stack is "<<Stack.popFirst();
/* Popping and Printing Some Elements from Second Stack */
cout<<"\nThe Popped Elements of Second Stack is "<<Stack.popSecond();
cout<<"\nThe Popped Elements of Second Stack is "<<Stack.popSecond();
}
OUTPUT: The Popped Elements of First Stack is 4 The Popped Elements of First Stack is 3 The Popped Elements of Second Stack is 8 The Popped Elements of Second Stack is 7
Related Posts:
- Check whether given Parentheses String are Balanced Parentheses or Not.
- Next Greater Element
- Find Minimum number of bracket reversals required to make an expression balanced.
- Implement Queue Using Two Stacks.
- Merge Overlapping Intervals using Stacks
- Implement Stack Using Linked List
- Largest Rectangular Area in Histogram
- Length of Longest Valid Substring
- Reverse a String using Stack
- Find Most Frequent Character of the String.
- Check Anagram Strings.
- Program to Reverse Each word of the String.
- Program to Print All the Substring of the Given String.
- Check Whether Given String is Palindromic Anagram or Not.
- Check Whether Given String is Panagram or Not.
- Find First Non-Repeating Character of the String.
- Find Most Frequent Element of the Array.
- Find Pair in an Array with Given Sum.
- Find First Repeating Element of an Array.
- Find Majority Element of an Array.
