In Java:

1. If we add a, b, c, d onto a stack and pop(), what will be returned?

2. If we add a, b, c, d into a queue and dequeue(), what will be returned?

3. Explain how to implement a [queue | stack] with a [singly | doubly] linked list with the optimal BigO? Which end(s) should you insert/remove from for the optimal Big-O?

4. Explain how to store a stack in an array with the optimal big-O.