#### Stacks & Queues

Problem
Given a stack with only 0s & 1s, find the majority element in the stack.
For e.g, if no. of 0s is more than no. of 1s, then 0 is the majority element.
Implement an inplace algorithm.

Solution
We use the basic recursion funda of storing the elements on the system stack.
Pop off elements and store them on system stack and during the process, maintain a count of no. of 0s & 1s.
Finally, push all elements from system stack to original stack & return the majority element.

```#include<iostream>
#include<stack>
using namespace std;

// get the majority element in a stack of only 0s and 1s
// inplace algorithm
int getMajorityElement(stack<int> &s) {
// store the counts of 0s and 1s
static int count_0 = 0, count_1 = 0;
if (!s.empty()) {
// get the top element
int top = s.top();
if (top == 0)
count_0++;
else
count_1++;
s.pop(); // remove the top element
// recursive call with updated stack
getMajorityElement(s);
// push all the elements again in the stack
// recursion funda (all the top elements are stored in
// system stack)
s.push(top);
return ((count_0 >= count_1) ? 0 : 1);
}
// return -1 if the stack is empty
return -1;
}

// main
int main() {
// we are using STL stack and not implementing our own stack
// since the purpose is to demonstrate the logic of getting
// the majority element inplace
stack<int> s;
s.push(0);
s.push(1);
s.push(0);
s.push(0);
s.push(1);
int major = getMajorityElement(s);
cout<<"\nMajority element is "<<major;
cout<<endl;
return 0;
}```