Maximum Queue

Implementation of Maximum Queue

Example 1:

Input: push={5,3,40} ,getmaximum ,push={60,50}, getmaximum, pop, getmaximum     
Output: 40, 60, 60

Approach:

Java

import java.util.Stack;

import javafx.util.Pair;

@SuppressWarnings("restriction")
public class MaximumQueue {
    public static void main(String[] args) {
        // stack pair to hold the element and the
        // maximum at the top of stack
        Stack<Pair<Integer, Integer>> stack1 = 
                new Stack<Pair<Integer, Integer>>();
        Stack<Pair<Integer, Integer>> stack2 = 
                new Stack<Pair<Integer, Integer>>();
        // add element's
        addELement(stack1, 5);
        addELement(stack1, 3);
        addELement(stack1, 10);
        // find maximum element
        System.out.print(findmaximumElement(stack1, stack2) + " ");
        // add again element's
        addELement(stack1, 12);
        addELement(stack1, 4);
        // find maximum
        System.out.print(findmaximumElement(stack1, stack2) + " ");
        removeElement(stack1, stack2);
        // find maximum
        System.out.print(findmaximumElement(stack1, stack2) + " ");
    }

    private static void removeElement(Stack<Pair<Integer, Integer>> 
                stack1, Stack<Pair<Integer, Integer>> stack2) {

        // if second is empty
        if (stack2.isEmpty()) {
            // this means convert the stack into queue
            while (!stack1.isEmpty()) {

                int element = stack1.pop().getValue();
                int maximum;

                // if second is empty
                // maximum is the current element
                if (stack2.isEmpty())
                    maximum = element;

                // else the maximum is max of current
                // element and stack top
                else
                    maximum = Math.max(element, stack2.peek().getValue());

                // push into the new stack
                stack2.add(new Pair<Integer, Integer>(element, maximum));
            }
        }
        // if second stack is not empty then pop the top element
        if (!stack2.isEmpty())
            stack2.pop();

    }

    private static int findmaximumElement(Stack<Pair<Integer, Integer>> 
            stack1, Stack<Pair<Integer, Integer>> stack2) {
        // if both stack is empty then -1
        if (stack1.isEmpty() && stack2.isEmpty())
            return -1;
        // if stack1 is empty then
        // top of stack2
        else if (stack1.isEmpty()) {
            return stack2.peek().getValue();
            // if stack2 is empty then
            // top of stack1
        } else if (stack2.isEmpty()) {
            return stack1.peek().getValue();
            // find max of both stack1, stack2
        } else {
            return Math.max(stack2.peek().getValue(),
                 stack1.peek().getValue());
        }
    }

    private static void addELement(Stack<Pair<Integer, Integer>> 
                stack1, int value) {
        int max = 0;
        // if stack is empty then
        // the maximum element is the given elememt
        if (stack1.isEmpty())
            max = value;
        // else the maximum element is
        // the max of stack top and current element
        else {
            max = Math.max(stack1.peek().getValue(), value);
        }
        // push the current element
        // with the maximum element
        stack1.add(new Pair<Integer, Integer>(value, max));

    }

}

C++

#include <bits/stdc++.h>
using namespace std;

//function to add the new element
void addElement(stack<pair<int,int>> &st1,int value)
{
    int maximum;

    //if stack is empty 
    //then maximum element is the
    //new element
    if(st1.empty())
       maximum=value;
  
  //else the maximum element
  //is the max of stack top and current 
  //element
    else
      maximum=max(value,st1.top().second);

    //push the new element into the stack
    st1.push({value,maximum});
}

//function to find the maximum element
//of the queue
int findMaximumElement(stack<pair<int,int>> &st1,
             stack<pair<int,int>> &st2)
{

    //if both are empty return -1
    if(st1.empty()&&st2.empty())
       return -1;
    
    //if first is empty return
    //second top element
    else if(st1.empty())
       return st2.top().second;

    //if second is empty return
    //first top element 
    else if(st2.empty())
       return st1.top().second;

   //else return max of both
   //stacks
    else
      return max(st1.top().second,st2.top().second);
}

//function to remove the element
void removeElement(stack<pair<int,int>> &st1,stack<pair<int,int>> &st2)
{

    //if second is empty
    if(st2.empty())
      {

          //this means convert the stack into
          //queue
          while(!st1.empty())
             {

                 int element=st1.top().first;
                 st1.pop();
                 int maximum;
                 
                 //if second is empty
                 //maximum is the current element
                 if(st2.empty())
                   maximum=element;

                 //else the maximum
                 //is max of current element and
                 //stack top
                else
                  maximum=max(element,st2.top().second);
                
                //push into the new stack
                st2.push({element,maximum});
             }
      }
    //if second stack is not 
    //empty then pop the top
    //element
    if(!st2.empty())
      st2.pop();
}
int main()
{
    stack<pair<int,int>> st1,st2;

     addElement(st1,5);
     addElement(st1,3);
     addElement(st1,40);

     //print 40
     cout<<findMaximumElement(st1,st2)<<"\n";

     addElement(st1,60);
     addElement(st1,50);

    //print 60
    cout<<findMaximumElement(st1,st2)<<"\n";
     removeElement(st1,st2);

     //print 60
     cout<<findMaximumElement(st1,st2)<<"\n";
     return 0;

}