I am now preparing for a test in my algorithms course and I have stumbled upon a question about a data structure which seems too trivial for me, but is probably not trivial at all.
The question is:
Let a "minimum stack" be a data structure that supports the following functions:
Creating a new empty data structure.
Inserting element X.
Returning the newest element and removing it from the data structure.
Returning the minimal element (the element with the smallest value). (without removing it)
Changing the minimal element's value to k. (Hint: say T is the number of elements added after the minimal element).
Now, I have thought about using a linked list which is isomorphic to an actual stack, hence elements can be added and removed only from the tail, but scanning the list from head to tail is possible.
I've checked and all the functions except 4 and 5 turn out to be O(1), but 4 turns out to be O(n) at best, and 5 turns out to be O(T).
My question is: How can I do 4 in O(1) time, so that all the other functions are also O(1)? I am not looking for full answers, just hints that will guide me to a full answer.