Designing a stack that supports all the standard operations like push(), pop(), and an additional operation getMin() that returns the minimum element from the stack in O(1) is the problem we will solve in this article. We can use two stacks to implement this special stack data structure. The first stack will store the actual elements of the stack, and the second stack will store the minimum values.
We will start by implementing the push() operation. To insert an element x to the special stack, we will push x to the first stack, which stores the actual elements. Then we will compare x with the top element of the second stack, which is the auxiliary stack that stores the minimum values. Let the top element be y.
If x is smaller than y, we will push x to the auxiliary stack. Otherwise, we will push y to the auxiliary stack. This way, the top of the auxiliary stack will always be the minimum element in the special stack.
Let's implement the pop() operation now. When we remove an element from the special stack, we will pop the top element from the auxiliary stack first. Then, we will pop the top element from the actual stack and return it. This ensures that the auxiliary stack is also updated for future operations.
Finally, we will implement the getMin() operation. This operation will simply return the top element of the auxiliary stack, which is the minimum element in the special stack.
All of the above operations take O(1) time because we are only performing simple stack operations like push, pop, and peek on both the actual and auxiliary stacks.
Here is an example to illustrate how our special stack works. Let's assume that both stacks are initially empty, and we insert the elements 18, 19, 29, 15, and 16 in sequence to the special stack.
When we insert 18, both stacks change to the following.
Actual Stack
18 <--- top
Auxiliary Stack
18 <---- top
When 19 is inserted, both stacks change to the following.
Actual Stack
19 <--- top
18
Auxiliary Stack
18 <---- top
18
When 29 is inserted, both stacks change to the following.
Actual Stack
29 <--- top
19
18
Auxiliary Stack
18 <---- top
18
18
When 15 is inserted, both stacks change to the following.
Actual Stack
15 <--- top
29
19
18
Auxiliary Stack
15 <---- top
18
18
18
When 16 is inserted, both stacks change to the following.
Actual Stack
16 <--- top
15
29
19
18
Auxiliary Stack
15 <---- top
15
18
18
18
When we call the getMin() operation, it will return 15, which is the minimum element in the special stack.
Similarly, we can perform all the standard stack operations along with the additional getMin() operation in O(1) time using our special stack implementation.