You are to code the following:

$1.$ A Stack backed by a singly$-$linked list without a tail reference.

$2.$ A Stack backed by an array

$3.$ A Queue backed by a singly$-$linked list with a tail reference

$4.$ A Queue backed by an array

A Stack is a last$-$in$,$ first$-$out $($LIFO$)$ data structure; the last item to be inserted is the first item to be

removed. A Queue is a first$-$in$,$ first$-$out $($FIFO$)$ data structure; the first item inserted is the first item to

be removed.

All your data structures must follow the requirements stated in the javadocs of each method you must

implement.

Note that the linked versions of the data structures should NOT be circular.

Capacity

The starting capacit