Queue

Write a program to retrieve the maximum and minimum element from a queue

Pinterest LinkedIn Tumblr

Write a program to retrieve the maximum and minimum element from a queue.

Algorithm Explanation

Create two stacks. Minimum stack and maximum stack.
Push operation checks the value with minimum value. If the value less than min value, push to the Minimum stack. If the value greater than the maximum value, push to the Maximum stack.
Pop operation checks the top value. If the value is equal to the minimum, pop the element from the minimum stack.
If the value equals to the maximum value, pop the element from the maximum stack.

Source Code

package com.dsacode.DataStructre.queue;
 
import java.util.Arrays;
import java.util.Stack;
 
public class QueueMaxMin extends Stack < Integer > {
    private static final long serialVersionUID = 1L;
    private Stack < Integer > minStack = null;
    private Stack < Integer > maxStack = null;
 
        public QueueMaxMin () {
            minStack = new Stack < Integer >();   
            maxStack = new Stack < Integer >();   
        }
 
        public void push(int value){
            if (value <= min()) {
                minStack.push(value);
            }
 
            if (value >= max()) {
                maxStack.push(value);
            }
 
            super.push(value);
        }
 
        public Integer pop() {
            int value = super.pop();
 
            if (value == min()) {
                minStack.pop();        
            }
 
            if (value == max()) {
                maxStack.pop();        
            }
 
            return value;
        }
 
        public int min() {
            if (minStack.isEmpty()) {
                return Integer.MAX_VALUE;
            } else {
                return minStack.peek();
            }
        }
 
        public int max() {
            if (maxStack.isEmpty()) {
                return Integer.MIN_VALUE;
            } else {
                return maxStack.peek();
            }
        }
      
    public void display(){
         Stack < Integer > l = new Stack < Integer >();
         l.addAll(minStack);
         l.addAll(maxStack);
            if(!l.isEmpty())
                System.out.println("Itmes in the Stack: "+Arrays.toString(l.toArray()));
 
    }
    public static void main(String[] args) {
        int[] array={12,1,56,34,78,99,11};
         QueueMaxMin obj = new QueueMaxMin();
         for(int i : array)
             obj.push(i);
          
         obj.display();
         System.out.println("Minimum item from the stack:" + obj.min());
         System.out.println("Maximum item from the stack:" + obj.max());
 
    }
}

Output

Itmes in the Stack: [12, 1, 12, 56, 78, 99]
Minimum item from the stack:1
Maximum item from the stack:99

Write A Comment