Quiz 3 -- Princeton Algorithm

Queue with two stacks. Implement a queue with two stacks so that each queue operations takes a constant amortized number of stack operations.

Hint: If you push elements onto a stack and then pop them all, they appear in reverse order. If you repeat this process, they're now back in order.

enqueue is to push element to stack 1 and dequeue is to pop element from stack 2, if stack 2 is empty then pop all the element from stack 1 and push them into stack 2 first. 


so for enqueue there is only one push operation, for dequeue , there is at most 2n operations , n is the number of element that was enqueued that was not dequeued. so the amortized number of operations for dequeue is at most 2.


Stack with max. Create a data structure that efficiently supports the stack operations (push and pop) and also a return-the-maximum operation. Assume the elements are reals numbers so that you can compare them.

Hint: Use two stacks, one to store all of the items and a second stack to store the maximums.

A maximum heap with linked list recording the insertion sequence.


or a stack with an sorted array to maintain the order ( each push is a binary search to the sorted array)

Java generics. Explain why Java prohibits generic array creation.

Hint: to start, you need to understand that Java arrays are covariant but Java generics are not: that is, 𝚂𝚝𝚛𝚒𝚗𝚐[] is a subtype of 𝙾𝚋𝚓𝚎𝚌𝚝[], but 𝚂𝚝𝚊𝚌𝚔<𝚂𝚝𝚛𝚒𝚗𝚐> is not a subtype of 𝚂𝚝𝚊𝚌𝚔<𝙾𝚋𝚓𝚎𝚌𝚝>.

It's due to type erasure. Java's Generics type parameter is the compile time information. It's erased in runtime, so a List<String> is erased to List. All the generic type of List share the common class List.class. While java's array is different, different type of array has its own class, for example , String[] and Integer[] have two different class. To determine an array's class type, we need the component type which is the type of the array element which is returned by Class.getComponentType method.