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;
}

Back | Next

All problems on Stacks and Queues
* Implement a stack using an array
* Implement a queue using an array
* Implement a circular queue using an array
* Design and implement an extended stack using linked list which permits push, pop & maxElement (gets maximum element in the stack) in O(1) time complexity
* Implement a circular queue using linked list
* Implement a Queue data structure using two stacks
* Sort a Queue using two stacks
* Convert infix expression to the postfix notation
* Implement an algorithm to evaluate a postfix expression
* Given a stack with only 0s & 1s, find the majority element in the stack
* Implement an inplace algorithm to sort a stack
About    Contact    Sitemap    Terms    Privacy