Using the interface below create a simple stack class.

$$ Use a node based structure to implement the stack

USE YOU STACK TO SOLVE THE STOCK SPAN

PROBLEM

The stock span problem

is a financial problem

where we have a series

of $n$ daily price quotes

for a stock and we need

to calculate span of

stock's price for all $n$

days.

public interface StackInterface $\{$

$/**$

$*$ Insert a new item into the stack.

$*$ @param item the item to insert.

$*/$

public void push$($Item item$)$;

$/**$

$*$ Remove the most recently inserted item from the stack.

$*/$

public void pop$()$;

$/**$

$*$ Get the most recently inserted item in the stack. Does not alter the stack.

$*$

$*/$

public Item top$()$;

$/**$

$*$ Return and remove the most recently inserted item from the stack.

$*$ @return the most recently inserted item in the stack.

$*/$

Item topAndPop$()$;

$/**$

$*$ Test if the stack is logically empty.

$*$ @return true if empty, false otherwise.

$*/$

public boolean isEmpty$()$;

$/**$

$*$Make the stack logically empty.

$*/$

public void makeEmpty$()$;

$/**$

$*$Return the size of the stack.

$*/$

public int size$()$;

$\}$

import java.util.ArrayList;

public class StockSpan $\{$

private ArrayList prices $=$ new ArrayList$()$;

private ArrayList spans $=$ new ArrayList$()$;

public StockSpan$()\{$

super$()$;

$\}$

$/*$

$*$ Fill the spans arrayList with the span for the day or the same index in prices.

$*$ ###### Use Brute Force ######

$*/$

void calculateSpansBruteForce$()$

$\{$

$\}$

$/*$

$*$ Fill the spans arrayList with the span for the day or the same index in prices.

$*$ ###### Use better algorithm $--$ Stack based algorithm?! ######

$*/$

private void calculateSpans$()$

$\{$

$\}$

public void addPrices$($int price$)$

$\{$

prices.add$($price$)$;

$\}$

public void print$()$

$\{$

calculateSpansBruteForce$()$;

for $($int i $=0$; i $$ spans.size$()$; i$++)$

$\{$

System.out.printf$("|$ D:$\%$d S:$\%$d $|",$i$,$ spans.get$($i$))$;

$\}$

System.out.println$()$;

$\}$

public int getSpan$($int day$)$

$\{$

calculateSpansBruteForce$()$;

if$($day $>=$ spans.size$())$

$\{$

return $-1$;

$\}$

return spans.get$($day$)$;

$\}$

$\}$

public class Main $\{$

public static void main$($String$[]$ args$)\{$

int prices$[]=\{100,80,60,70,60,75,85\}$;

StockSpan stockSpan $=$ new StockSpan$()$;

for$($int i $=0$; i $$ prices.length; i$++)$

$\{$

stockSpan.addPrices$($prices$[$i$])$;

$\}$

stockSpan.print$()$;

$\}$

$\}$