Use a LinkedList with a head and tail pointer, add to the back of the linkedlist for push, remove and return from back for pop. Keep a min variable/pointer (depending on what the interviewer wants) that updates every time an element is added.