Question

1. 5 marks] A MinStack supports three main operations: the standard Stack operations push(x) and pop() and the non-standard min() operation which returns the minimum value stored on the stack. The zip file gives an implementation SlowMinStack that implements these operations so that push(x) and pop() each run in O(1) time, but  min()runs in Θ(n) time.
   For this question, you should complete the implementation of FastMinStack that implements all three operations in O(1) time per operation. As part of your implementation, you may use any of the classes in the Java Collections Framework and you may use any of the source code provided with the Java version of the textbook. Don't forget to also implement the size() and iterator()^* methods.
   Think carefully about your solution before you start coding. Here are two hints: (i) don't use any kind of SortedSet or SortedMap, These all require Ω(logn) time per operation; (ii) take a look at the sample solution for Part 10 of Assignment 1.  Really understanding this solution will help you design your data structure.
2. [5 marks] A MinDeque supports five operations: The standard Deque operations addFirst(x), removeFirst(), addLast(x), and removeLast() and the non-standard min() operation that returns the minimum value stored in the Deque. Again, the zip file provides an implementation SlowMinDeque that supports each of the first four operation in O(1) time per operation but requires Ω(n) time for the min() operation.
   For this question, you should complete the implementation of FastMinDeque that implements all five operations in O(1) (amortized) time per operation. As part of your implementation, you may use any of the classes in the Java Collections Framework and you may use any of the source code provided with the Java version of the textbook. Don't forget to also implement the size() and iterator()^* methods. Think carefully about your solution before you start coding. Here are two hints: (i) don't use any kind of SortedSet or SortedMap, These all require Ω(logn) time per operation; (ii) consider using one of the techniques we've seen in class for implementing the Deque interface.

^*You can still get part marks without correctly implementing the iterator() method. But for full marks, the iterator() method needs to return an Object that supports the next() and hasNext() methods from the Iterator<T> interface. For a MinStack, the iterator should output the elements at the bottom of the stack first (the elements that have been in the stack the longest), finishing with the element at the top of the stack (the element that would be returned by a call to pop()). For a MinDeque, the iterator should output the elements beginning with the first element (the one that would be returned by removeFront()) and finishing with the last element (the one that would be returned by removeLast()).

Hint: There's no need to build your iterators from scratch. The collections in java.util all have iterators.

package comp2402a2;

import java.util.Comparator;
import java.util.List;
import java.util.LinkedList;
import java.util.Iterator;

public class FastMinStack<T> implements MinStack<T> {

protected Comparator<? super T> comp;

public FastMinStack() {
this(new DefaultComparator<T>());
}

public FastMinStack(Comparator<? super T> comp) {
this.comp = comp;
// TODO: Your code goes here
}

public void push(T x) {
// TODO: Your code goes here
}

public T pop() {
// TODO: Your code goes here
return null;
}

public T min() {
// TODO: Your code goes here
return null;
}

public int size() {
// TODO: Your code goes here
return -1;
}

public Iterator<T> iterator() {
// TODO: Your code goes here
return null;
}

public Comparator<? super T> comparator() {
return comp;
}
}

package comp2402a2;

import java.util.Comparator;
import java.util.List;
import java.util.LinkedList;
import java.util.Iterator;

public class FastMinDeque<T> implements MinDeque<T> {

protected Comparator<? super T> comp;

public FastMinDeque() {
this(new DefaultComparator<T>());
}

public FastMinDeque(Comparator<? super T> comp) {
this.comp = comp;
// TODO: Your code goes here
}

public void addFirst(T x) {
// TODO: Your code goes here
}

public void addLast(T x) {
// TODO: Your code goes here
}

public T removeFirst() {
// TODO: Your code goes here
return null;
}

public T removeLast() {
// TODO: Your code goes here
return null;
}

public T min() {
// TODO: Your code goes here
return null;
}

public int size() {
// TODO: Your code goes here
return -1;
}

public Iterator<T> iterator() {
// TODO: Your code goes here
return null;
}

public Comparator<? super T> comparator() {
return comp;
}

}

Answer 1

import java.util.Comparator;
import java.util.List;
import java.util.LinkedList;
import java.util.Iterator;

public class FastMinStack<T> implements MinStack<T> {

  protected Comparator<? super T> comp;
  
  // we will take two linked list ds will hold our original value
  // and auxiliary will store the minimum value till now.
  
  protected List<T> ds;
  protected List<T> auxiliary;

  public FastMinStack() {
    this(new DefaultComparator<T>());
  }

  public FastMinStack(Comparator<? super T> comp) {
    this.comp = comp;
    ds=new LinkedList<T>();
    auxiliary=new LinkedList<T>();
  }

  public void push(T x) {
    // TODO: Your code goes here
        
          // when we push any element we will see that if stack is empty then insert 
          // x into both ds and auxiliary list
          // if stack is not empty then compare the top value from auxiliary list
          // with x if x is smaller then add it to auxiliary list also
          
          if(ds.size()==0)
          {
                  ds.add(x);
                  auxiliary.add(x);
                  return ;
                  
          }
          
          T y=auxiliary.get(auxiliary.size()-1);
          if(comp.compare(x, y)<0)
          {
                  auxiliary.add(x);
          }
          
          
  }

  public T pop() {
    // TODO: Your code goes here
         //  while poping we will see that if poped element is also top element of the
          // auxiliary list then also removed from auxiliary list.
          
         if(size()==0)
                 return null;
         T x=ds.remove(size()-1);
         if(comp.compare(x, auxiliary.get(size()-1))==0)
         {
                 auxiliary.remove(auxiliary.size()-1);
         }
         
    return null;
  }

  public T min() {
    if(size()==0)
    return null;
    return auxiliary.get(auxiliary.size()-1);
  }

  public int size() {
    // TODO: Your code goes here
    return ds.size();
  }

  public Iterator<T> iterator() {
    // TODO: Your code goes here
    return ds.iterator();
  }

  public Comparator<? super T> comparator() {
    return comp;
  }
}