Queue minimum using stack

Problem

Implement a queue which has an efficient get minimum function along with enqueue and dequeue method.

Brute force

when queue is implemented using circular array or linked list, the enqueue and dequeue operation is of O(1) complexity. but the brute force algorithm for implementing the get minimum is of O(n) complexity.

Solution

In our previous example we have seen that we can implement a stack which has push, pop and get minimum method all having O(1) complexity. See StackMinimum. And we have also seen that a queue can be implemented using two stacks. See Queue using stack. Using these two solutions we can implement a queue with get minimum method with O(1) complexity.

Code

/*
 * Implement a queue in which push_rear(), pop_front() 
 * and get_min() are all constant time operations. 
 * first solution using two stacks
 */
public class QueueMinUsingStack
{

 static StackMinimum stackMinimum1=new StackMinimum();
 static StackMinimum stackMinimum2=new StackMinimum();
 public static void enqueue(int a)
 {
  stackMinimum1.push(a);
 }
 
 public static int dequeue()
 {
  if(stackMinimum2.size()==0)
  {
   while(stackMinimum1.size()!=0)
    stackMinimum2.push(stackMinimum1.pop());
  }
  return stackMinimum2.pop();
 }
 
 public int getMinimum()
 {
  return Math.min(
   stackMinimum1.size()==0?
     Integer.MAX_VALUE:stackMinimum1.getMinimum(),
   stackMinimum2.size()==0?
     Integer.MAX_VALUE:stackMinimum2.getMinimum()
        );
 }
}

Index