Daily Archives: January 4, 2015

Queue with min and max value

I’ve read the Queue with min and max value code from Junmin Liu link. The one he mentioned is really good idea. It uses 2 stacks to keep the min/max for queue.
This problem is orignated from the count bound sliced problem. For that problem, I used another way to implement. By that, I can evolve it to another way of implementation queue with min/max. As I mentioned before, this min/max value is similar to the sliding window problem. Just evolve it with another min value.
I would say, both are good idea for queue with min/max.
2 queues solution should always change the queues more than 1 time operaiton. There is no constant O(1) time enqueue and dequeue.
2 stacks solution can always take O(1) time for enqueue and dequeue. But disadvantage is that there would be sometime that it takes O(n) for dequeue.
Here is my code:

  1. package util;
  2. import java.util.LinkedList;
  3. public class MQueue2 {
  4.     private LinkedList<Integer> q = new LinkedList<Integer>();
  5.     private LinkedList<Integer> maxq = new LinkedList<Integer>();
  6.     private LinkedList<Integer> minq = new LinkedList<Integer>();
  7.     public boolean enQueue(int e){
  8.         enMaxq(e);
  9.         enMinq(e);
  10.         q.addLast(e);
  11.         return true;
  12.     }
  13.     public int deQueue(){
  14.         if(q.size()<1){
  15.             return Integer.MIN_VALUE;
  16.         }
  17.         int curr = q.removeFirst();
  18.         deMaxq(curr);
  19.         deMinq(curr);
  20.         return curr;
  21.     }
  22.     private void enMaxq(int e){
  23.         if(maxq.size()==0){
  24.             maxq.addLast(e);
  25.             return;
  26.         }
  27.         int curr = maxq.getLast();
  28.         while(e>curr&&maxq.size()>0){
  29.             maxq.removeLast();
  30.             if(maxq.size()<1){
  31.                 break;
  32.             }
  33.             curr = maxq.getLast();
  34.         }
  35.         maxq.addLast(e);
  36.     }
  37.     private void deMaxq(int e){
  38.         if(maxq.size()<1){
  39.             return;
  40.         }
  41.         int curr = maxq.getFirst();
  42.         if(e==curr){
  43.             maxq.removeFirst();
  44.         }
  45.     }
  46.     private void enMinq(int e){
  47.         if(minq.size()==0){
  48.             minq.addLast(e);
  49.             return;
  50.         }
  51.         int curr = minq.getLast();
  52.         while(e<curr&&minq.size()>0){
  53.             minq.removeLast();
  54.             if(minq.size()<1){
  55.                 break;
  56.             }
  57.             curr = minq.getLast();
  58.         }
  59.         minq.addLast(e);
  60.     }
  61.     private void deMinq(int e){
  62.         if(minq.size()<1){
  63.             return;
  64.         }
  65.         int curr = minq.getFirst();
  66.         if(e==curr){
  67.             minq.removeFirst();
  68.         }
  69.     }
  70.     public int min(){
  71.         if(minq.size()<1){
  72.             return Integer.MAX_VALUE;
  73.         }
  74.         return minq.getFirst();
  75.     }
  76.     public int max(){
  77.         if(maxq.size()<1){
  78.             return Integer.MIN_VALUE;
  79.         }
  80.         return maxq.getFirst();
  81.     }
  82. }

I also attach Junmin Liu’s code:

  1. package util;
  2. import java.util.Stack;
  3. //a queue(FIFO) can track min and max of all elements in amortized O(1) time
  4. public class MQueue {
  5.     MStack s_new = new MStack(), s_old = new MStack();
  6.     public void enqueue(int i) {
  7.         s_new.push(i);
  8.     }
  9.     public int dequeue() {
  10.         if (s_old.isEmpty()) {
  11.             while (!s_new.isEmpty()) {
  12.                 s_old.push(s_new.pop());
  13.             }
  14.         }
  15.         return s_old.pop();
  16.     }
  17.     public boolean isEmpty() {
  18.         return s_new.isEmpty() && s_old.isEmpty();
  19.     }
  20.     public int min() {
  21.         return Math.min(s_new.min(), s_old.min());
  22.     }
  23.     public int max() {
  24.         return Math.max(s_new.max(), s_old.max());
  25.     }
  26. }
  27. // a stack node which contains min and max of all underlying elements
  28. class MNode {
  29.     Integer i, min, max;
  30.     MNode(int i, int max, int min) {
  31.         this.i = i;
  32.         this.max = max;
  33.         this.min = min;
  34.     }
  35. }
  36. // a stack(LIFO) can track min and max of all elements in amortized O(1) time
  37. class MStack {
  38.     Stack<MNode> s = new Stack<MNode>();
  39.     public boolean isEmpty() {
  40.         return s.isEmpty();
  41.     }
  42.     public int min() {
  43.         if (s.isEmpty())
  44.             return Integer.MAX_VALUE;
  45.         return s.peek().min;
  46.     }
  47.     public int max() {
  48.         if (s.isEmpty())
  49.             return Integer.MIN_VALUE;
  50.         return s.peek().max;
  51.     }
  52.     public void push(int i) {
  53.         int max = Math.max(i, max());
  54.         int min = Math.min(i, min());
  55.         s.push(new MNode(i, max, min));
  56.     }
  57.     public int pop() {
  58.         System.out.println(s.peek().i);
  59.         return s.pop().i;
  60.     }
  61. }