(In Java) Design a stack that supports getMin(), pop() and push() in O(1) time. Must use...

(In Java) Design a stack that supports getMin(), pop() and push() in O(1) time. Must use the iterator and comparator, does not need to be a linked list, although it's what I've tried using. I'm using another tester class to test this class.

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

public class FMinStack<T> implements MinStack<T>
{
    protected Comparator<? super T> comp;
    T min;
    protected List<T> ds;


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

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

    public void push(T x)
    {
       
    }

    public T pop()
    {
    }

    public T getMin() {
    }

    public int size() {
        return ds.size();
    }

    public Iterator<T> iterator()
    {
    }

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

Classes it extends to:

import java.util.Comparator;

public interface MinStack<T> extends Iterable<T> {
    public Comparator<? super T> comparator();

    public void push(T x);

    public T pop();

    public T getMin();

    public int size();
}

And

import java.util.Comparator;

class DefaultComparator<T> implements Comparator<T> {
    @SuppressWarnings("unchecked")
    public int compare(T a, T b) {
        return ((Comparable<T>)a).compareTo(b);
    }
}

Solutions

Expert Solution

Here is the completed code for this problem. Comments are included, go through it, learn how things work and let me know if you have any doubts or if you need anything to change. If you are satisfied with the solution, please rate the answer. If not, PLEASE let me know before you rate, I’ll help you fix whatever issues. Thanks

Note: Since you mentioned that you already have a test program, I am not including any.


//FMinStack.java

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

public class FMinStack<T> implements MinStack<T> {
        protected Comparator<? super T> comp;
        protected LinkedList<T> ds;
        // a linked list to store minimum values
        protected LinkedList<T> minValues;

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

        public FMinStack(Comparator<? super T> comp) {
                this.comp = comp;
                ds = new LinkedList<T>();
                // also initializing minValues
                minValues = new LinkedList<T>();
        }

        public void push(T x) {
                // adding x to the head of ds
                ds.addFirst(x);
                // if minValues is empty, or if x<head value of minValues, adding x to
                // the head of minValues
                if (minValues.isEmpty() || comp.compare(x, minValues.getFirst()) <= 0) {
                        minValues.addFirst(x);
                }
                // otherwise adding the same head value to the head of minValues
                else {
                        minValues.addFirst(minValues.getFirst());
                }
                // the idea is that, at any point, the first element in minValues point
                // to the current smallest element CURRENTLY on the stack.
        }

        public T pop() {
                if (size() > 0) {
                        // removing front/head values from ds and minValues. so minValues
                        // will now point to the next smallest value available on the stack.
                        T top = ds.removeFirst();
                        minValues.removeFirst();
                        return top;
                }
                return null; //empty
        }

        public T getMin() {
                if (size() > 0) {
                        //returning value at the head of minValues
                        return minValues.getFirst();
                }
                return null;
        }

        public int size() {
                return ds.size();
        }

        public Iterator<T> iterator() {
                return ds.iterator();
        }

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

venereology answered 1 month ago

Next > < Previous

Related Solutions

5 marks] A MinStack supports three main operations: the standard Stack operations push(x) and pop() and...

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...

Write a function that returns the largest value in a stack (only use push and pop)

Please code in C /* Implements functions that operate on Stack 1. PUSH 2. POP 3....

Please code in C /* Implements functions that operate on Stack 1. PUSH 2. POP 3. isEmpty 4. PEEK 5. Size */ #include <stdio.h> #define CAPACITY 1000 //Two stacks .. for each stack we need // 1. An Array that can hold capacity of elements // 2. A top initialzied to -1 (signifying that the stak is empty at the start) //NOTE : THESE STACKS ARE OF TYPE CHAR :( ... so you need to FIX IT!!!! to int and...

All code should be in Python 3. Implement the Stack Class, using the push, pop, str,...

All code should be in Python 3. Implement the Stack Class, using the push, pop, str, init methods, and the insurance variable 'list'.

Java [(1)] Design a Stack that is composed ONLY of one or two Queue objects ergo...

Java [(1)] Design a Stack that is composed ONLY of one or two Queue objects ergo the ONLY instance variables that exist in this stack are queues. Stack class should contain the following methods: Print, Pop, Push, Top, Size, isEmpty, copy [(2)] Design a Queue that is composed ONLY of two Stacks objects ergo the ONLY instance variables that exist in this queue are stacks. Queue class should contain the following methods: Print, Enqueue, Dequeue, Front, Rear, Size, isEmpty, Copy...

Exercise 3: Stack Write a program in Java to manipulate a Stack List: 1. Create Stack...

Exercise 3: Stack Write a program in Java to manipulate a Stack List: 1. Create Stack List 2. Display the list 3. Create the function isEmply 4. Count the number of nodes 5. Insert a new node in the Stack List. 6. Delete the node in the Stack List. 7. Call all methods above in main method with the following data: Test Data : Input the number of nodes : 4 Input data for node 1 : 5 Input data...

In java thanks! Design a Stack that is composed ONLY of one or two Queue objects...

In java thanks! Design a Stack that is composed ONLY of one or two Queue objects ergo the ONLY instance variables that exist in this stack are queues. Stack class should contain the following methods: Print Pop Push Top Size isEmpty copy [(2)] Design a Queue that is composed ONLY of two Stacks objects ergo the ONLY instance variables that exist in this queue are stacks. Queue class should contain the following methods: Print Enqueue Dequeue Front Rear Size isEmpty...

"""stack.py implements stack with a list""" class Stack(object): def init(self): #creates an empty stack. O(1) self.top...

"""stack.py implements stack with a list""" class Stack(object): def __init__(self): #creates an empty stack. O(1) self.top = -1 #the index of the top element of the stack. -1: empty stack self.data = [] def push(self, item): # add item to the top of the stack. O(1) self.top += 1 self.data.append(item) def pop(self): # removes and returns the item at the top O(1) self.top -=1 return self.data.pop() def peek(self): # returns the item at the top O(1) return self.data[len(self.data)-1] def isEmpty(self):...

Explain why the number of nonterminals that can pop from an LL(1) parse stack is not...

Explain why the number of nonterminals that can pop from an LL(1) parse stack is not bounded by a grammar-specific constant.

On December 1, year1, Pop Copration( U.S company)sold inventory to Java A.M. inc. on credit. ?Java...

On December 1, year1, Pop Copration( U.S company)sold inventory to Java A.M. inc. on credit. ?Java A.M will pay Pop corp. 10,000 eruos in 90days. Pop Corp has a December 31 year-end. The following rates are known: ?December 1 spot rate: 1USD=1.24 euros ?December 1, 90 day forward rat: 1 USD=1.4 euros ?December 31, spot rate: 1 USD= 1.20 euros ?December 31, 60-day forward rate: 1 USU=1.3 euros ?Prepare Sony Coro. jounral entries, December 1, December 31. March 1st....

Subjects