A Propose A Data Structure That Supports The Stack Push

a. Propose a data structure that supports the stack push and pop operations and a third operation findMin, which returns the smallest element in the data structure, all in O(1) worst-case time.
b. Prove that if we add the fourth operation deleteMin which finds and removes the smallest element, then at least one of the operations must take Ω(logN) time. (This requires reading Chapter 7.)

Posted in Uncategorized