Data Structures

Question: Design a data structure that can push, pop, and getmin in O(1), on given set of data.


Question: Design a data structure that allow insert, delete, max in O(1)

Question: Design a special stack that support these operation pop(), push(), isFull and getMin() or getMax(), in O(1).
Answer:
Maintain two stack, Main stack and other stack. Other stack will maintain the current max or min in Main stack. If you want minimum element then other stack will maintain minimum element, otherwise if you want maximum element then other stack will maintain current max element.
The answer is, you use two stacks: the main stack, and a min (or max) stack.
So for example, after pushing 1,2,3,4,5 onto the stack, your stacks would look like this:

MAIN   MIN
+---+  +---+
| 5 |  | 1 |
| 4 |  | 1 |
| 3 |  | 1 |
| 2 |  | 1 |
| 1 |  | 1 |
+---+  +---+

However, if you were to push 5,4,3,2,1, the stacks would look like this:

MAIN   MIN
+---+  +---+
| 1 |  | 1 |
| 2 |  | 2 |
| 3 |  | 3 |
| 4 |  | 4 |
| 5 |  | 5 |
+---+  +---+

For 5,2,4,3,1 you would have:

MAIN   MIN
+---+  +---+
| 1 |  | 1 |
| 3 |  | 2 |
| 4 |  | 2 |
| 2 |  | 2 |
| 5 |  | 5 |
+---+  +---+

and so on.
You can also save some space by pushing to the min stack only when the minimum element changes, iff the items are known to be distinct.