The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

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