Minimum Queue

Implementation of Minimum Queue

Example 1:

Input: push={5,3,10} ,getminimum ,push={2,4}, getminimum, pop, getminimum     
Output: 3, 2, 2

Approach:

Java

import java.util.Stack;

import javafx.util.Pair;

@SuppressWarnings("restriction")
public class MinimumQueue {
    public static void main(String[] args) {
        // stack pair to hold the element and the
        // minimum 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, 23);
        addELement(stack1, 10);
        // find minimum element
        System.out.print(findMinimumElement(stack1, stack2) + " ");
        // add again element's
        addELement(stack1, 3);
        addELement(stack1, 6);
        // find minimum
        System.out.print(findMinimumElement(stack1, stack2) + " ");
        removeElement(stack1, stack2);
        // find minimum
        System.out.print(findMinimumElement(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 minimum;

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

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

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

    }

    private static int findMinimumElement(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 min of both stack1, stack2
        } else {
            return Math.min(stack2.peek().getValue(),
                 stack1.peek().getValue());
        }
    }

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

    }

}

C++

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

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

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

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

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

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

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

   //else return min of both
   //stacks
    else
      return min(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 minimum;
                 
                 //if second is empty
                 //minimum is the current element
                 if(st2.empty())
                   minimum=element;

                 //else the minimum
                 //is min of current element and
                 //stack top
                else
                  minimum=min(element,st2.top().second);
                
                //push into the new stack
                st2.push({element,minimum});
             }
      }
    //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,10);

     //print 3
     cout<<findMinimumElement(st1,st2)<<"\n";

     addElement(st1,2);
     addElement(st1,4);

    //print 2
    cout<<findMinimumElement(st1,st2)<<"\n";
     removeElement(st1,st2);

     //print 2
     cout<<findMinimumElement(st1,st2)<<"\n";
     return 0;

}