Create an algorithms for data structure that is capable of s

Create an algorithms for data structure that is capable of storing a collection of integers, and supporting the following operations:

- add(d, x): add the integer x to the collection for the data structure d

- remove(d): return and remove the last integer added to the data structure d (that is still in the collection)

- min(d): return the minimum value stored in the data structure d

All of the operations must run in O(1) time. Clearly indicate what fields you are using in your data structure, as well as how they are implemented (if there are multiple possible implementations). Note: we just need algorithms not actual code.

Solution

We use two stacks to achieve this. The first stacks contains all the numbers in the collection and the top of second stack contains the maximum number in the stack.

add operation:

We add the number k to stack1 and we compare the number k with top of stack2 lets call it p if the k is less than pwe add k to stack2 or we again a push p to stack2.

remove:

We pop the numbers from both stacks and return the popped number from stack1.

min:

This will return the top of stack2.

Example:

Stack1 Stack2

5 1

3 1

1 1

6 2

4 2

2 2