(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);
    }
}

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 year ago

JAVA Stack - Implementation. You will be able to use the push, pop and peek of...

JAVA Stack - Implementation. You will be able to use the push, pop and peek of Stack concept. Post-Fix calculator - When an arithmetic expression is presented in the postfix form, you can use a stack to evaluate the expression to get the final value. For example: the expression 3 + 5 * 9 (which is in the usual infix form) can be written as 3 5 9 * + in the postfix. More interestingly, post form removes all parentheses...

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)

Reverse the contents of a stack using only stack operations [ push() and pop() ]. Using the...

Reverse the contents of a stack using only stack operations [ push() and pop() ]. Using the java and give the explanation

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

Consider an ADT with the same operators as a stack (push(), pop(), size(), empty()), except that...

Consider an ADT with the same operators as a stack (push(), pop(), size(), empty()), except that the pop() operator returns the largest element rather than the element most recently pushed. For this to make sense, the objects on the stack must be totally ordered (e.g. numbers). Describe array and linked list implementations of the ADT. Your implementations should be as time and space efficient as you can manage. Give the running times for the CRUD operators.

# ArrayStack # TODO: push and pop using array stack with doubling technique. import numpy as...

# ArrayStack # TODO: push and pop using array stack with doubling technique. import numpy as np from future import print_function # Definisi class ArrayStack class ArrayStack(object): def __init__(self): self.data = np.zeros(20, dtype=np.int) self.count = 0 def isEmpty(self): pass # ubah saya def size(self): pass # ubah saya def push(self, obj): pass # ubah saya def pop(self): pass # ubah saya #-------------------------- # End of class if __name__ == "__main__": stack = ArrayStack() randn = np.random.permutation(1000) for i in range(1000):...

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

Using Python list tools, create the standard stack (push, pop) and queue (enqueue, dequeue) operations Counting...

Using Python list tools, create the standard stack (push, pop) and queue (enqueue, dequeue) operations Counting Letter Challenge: Create a function that... Takes in a string as parameter Counts how often each letter appears in the string Returns a dictionary with the counts BONUS: make it so lowercase and uppercase letter count for the same letter

JAVA I need to make it that I can expand the stack for everytime a push...

JAVA I need to make it that I can expand the stack for everytime a push operation is performed that would normally cause an overflow, returning a false value. Should accompany 3 nodes initially. DriverStack.java public class DriverStack { public static void main (String[] args) { Stack s = new Stack(3); Listing l; Listing l1 = new Listing ("Bill", "1st Avenue", "123 4567"); Listing l2 = new Listing ("Alec", "2nd Avenue", "456 4567"); Listing l3 = new Listing...

Question