Design a special dynamic Stack using an array that supports all the stack operations such as push(), pop(), peek(), isEmpty(), and getMin() operations in constant Time and Space complexities.
Examples:
Assuming the right to left orientation as the top to bottom orientation and performing the operations:
- Push(10): 10 is added to the top of the stack. Thereafter, the stack modifies to {10}.
- Push(4): 4 is added to the top of the stack. Thereafter, the stack modifies to {10, 4}.
- Push(9): 9 is added to the top of the stack. Thereafter, the stack modifies to {10, 4, 9}.
- Push(6): 6 is added to the top of the stack. Thereafter, the stack modifies to {10, 4, 9, 6}.
- Push(5): 5 is added to the top of the stack. Thereafter, the stack modifies to {10, 4, 9, 6, 5}.
- Peek(): Prints the top element of the stack 5.
- getMin(): Prints the minimum element of the stack 4.
- Pop(): Deletes the top most element, 5 from the stack. Thereafter, the stack modifies to {10, 4, 9, 6}.
- Pop(): Deletes the top most element, 6 from the stack. Thereafter, the stack modifies to {10, 4, 9}.
- Pop(): Deletes the top most element, 9 from the stack. Thereafter, the stack modifies to {10, 4}.
- Pop(): Deletes the top most element, 4 from the stack. Thereafter, the stack modifies to {10}.
- Peek(): Prints the top element of the stack 10.
- getMin(): Prints the minimum element of the stack 10.
Approach: To implement a dynamic stack using an array the idea is to double the size of the array every time the array gets full. Follow the steps below to solve the problem:
- Initialize an array, say arr[] with an initial size 5, to implement the stack.
- Also, initialize two variables, say top and minEle to store the index of the top element of the stack and minimum element of the stack.
- Now, perform the following stack operations:
- isEmpty(): Checks if the stack is empty or not.
- Return true if the top is less or equal to 0. Otherwise, return false.
- Push(x): Inserts x at the top of the stack.
- If the stack is empty, insert x into the stack and make minEle equal to x.
- If the stack is not empty, compare x with minEle. Two cases arise:
- If x is greater than or equal to minEle, simply insert x.
- If x is less than minEle, insert (2*x – minEle) into the stack and make minEle equal to x.
- If the array used is full then, double the size of the array and then copy all the elements of the previous array to the new array and then assign the address of the new array to the original array. Thereafter, perform the push operation as discussed above.
- Pop(): Removes an element from the top of the stack.
- Let the removed element be y. Two cases arise
- If y is greater than or equal to minEle, the minimum element in the stack is still minEle.
- If y is less than minEle, the minimum element now becomes (2*minEle – y), so update minEle as minEle = 2*minEle-y.
- getMin(): Finds the minimum value of the stack.
- If the stack is not empty then return the value of minEle. Otherwise, return “-1” and print “Underflow“.
- isEmpty(): Checks if the stack is empty or not.
Illustration:
Push(x)
- Number to be Inserted: 3, Stack is empty, so insert 3 into stack and minEle = 3.
- Number to be Inserted: 5, Stack is not empty, 5> minEle, insert 5 into stack and minEle = 3.
- Number to be Inserted: 2, Stack is not empty, 2< minEle, insert (2*2-3 = 1) into stack and minEle = 2.
- Number to be Inserted: 1, Stack is not empty, 1< minEle, insert (2*1-2 = 0) into stack and minEle = 1.
- Number to be Inserted: 1, Stack is not empty, 1 = minEle, insert 1 into stack and minEle = 1.
- Number to be Inserted: -1, Stack is not empty, -1 < minEle, insert (2*-1 – 1 = -3) into stack and minEle = -1.
Pop()
- Initially the minimum element minEle in the stack is -1.
- Number removed: -3, Since -3 is less than the minimum element the original number being removed is minEle which is -1, and the new minEle = 2*-1 – (-3) = 1
- Number removed: 1, 1 == minEle, so number removed is 1 and minEle is still equal to 1.
- Number removed: 0, 0< minEle, original number is minEle which is 1 and new minEle = 2*1 – 0 = 2.
- Number removed: 1, 1< minEle, original number is minEle which is 2 and new minEle = 2*2 – 1 = 3.
- Number removed: 5, 5> minEle, original number is 5 and minEle is still 3
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// A class to create// our special stackclass Stack {private: // Initial size of // the Array int Max = 5; // Array for the stack // implementation int* arr = new int(Max); // Stores the minimum // Element of the stack int minEle = 0; // Stores the top element // of the stack int top = 0;public: // Method to check whether // stack is empty or not bool empty() { if (top <= 0) { return true; } else { return false; } } // Method to push elements // to the Special Stack void push(int x) { // If stack is empty if (empty()) { // Assign x to minEle minEle = x; // Assign x to arr[top] arr[top] = x; // Increment top by 1 top++; } // If array is full else if (top == Max) { // Update the Max size Max = 2 * Max; int* temp = new int(Max); // Traverse the array arr[] for (int i = 0; i < top; i++) { temp[i] = arr[i]; } // If x is less than minEle if (x < minEle) { // Push 2*x-minEle temp[top] = 2 * x - minEle; // Assign x to minEle minEle = x; top++; } // Else else { // Push x to stack temp[top] = x; top++; } // Assign address of the // temp to arr arr = temp; } else { // If x is less // than minEle if (x < minEle) { // Push 2*x-minEle arr[top] = 2 * x - minEle; top++; // Update minEle minEle = x; } else { // Push x to the // stack arr[top] = x; top++; } } } // Method to pop the elements // from the stack. void pop() { // If stack is empty if (empty()) { cout << "Underflow" << endl; return; } // Stores the top element // of the stack int t = arr[top - 1]; // If t is less than // the minEle if (t < minEle) { // Pop the minEle cout << "Popped element : " << minEle << endl; // Update minEle minEle = 2 * minEle - t; } // Else else { // Pop the topmost element cout << "Popped element : " << t << endl; } top--; return; } // Method to find the topmost // element of the stack int peek() { // If stack is empty if (empty()) { cout << "Underflow" << endl; return -1; } // Stores the top element // of the stack int t = arr[top - 1]; // If t is less than // the minEle if (t < minEle) { return minEle; } // Else else { return t; } } // Method to find the Minimum // element of the Special stack int getMin() { // If stack is empty if (empty()) { cout << "Underflow" << endl; return -1; } // Else else { return minEle; } }};// Driver Codeint main(){ Stack S; S.push(10); S.push(4); S.push(9); S.push(6); S.push(5); cout << "Top Element : " << S.peek() << endl; cout << "Minimum Element : " << S.getMin() << endl; S.pop(); S.pop(); S.pop(); S.pop(); cout << "Top Element : " << S.peek() << endl; cout << "Minimum Element : " << S.getMin() << endl; return 0;} |
Java
// Java program for the above approachpublic class Main{ // Initial size of // the Array static int Max = 5; // Array for the stack // implementation static int[] arr = new int[Max]; // Stores the minimum // Element of the stack static int minEle = 0; // Stores the top element // of the stack static int Top = 0; // Method to check whether // stack is empty or not static boolean empty() { if (Top <= 0) { return true; } else { return false; } } // Method to push elements // to the Special Stack static void push(int x) { // If stack is empty if (empty()) { // Assign x to minEle minEle = x; // Assign x to arr[top] arr[Top] = x; // Increment top by 1 Top++; } // If array is full else if (Top == Max) { // Update the Max size Max = 2 * Max; int[] temp = new int[Max]; // Traverse the array arr[] for (int i = 0; i < Top; i++) { temp[i] = arr[i]; } // If x is less than minEle if (x < minEle) { // Push 2*x-minEle temp[Top] = 2 * x - minEle; // Assign x to minEle minEle = x; Top++; } // Else else { // Push x to stack temp[Top] = x; Top++; } // Assign address of the // temp to arr arr = temp; } else { // If x is less // than minEle if (x < minEle) { // Push 2*x-minEle arr[Top] = 2 * x - minEle; Top++; // Update minEle minEle = x; } else { // Push x to the // stack arr[Top] = x; Top++; } } } // Method to pop the elements // from the stack. static void pop() { // If stack is empty if (empty()) { System.out.print("Underflow"); return; } // Stores the top element // of the stack int t = arr[Top - 1]; // If t is less than // the minEle if (t < minEle) { // Pop the minEle System.out.println("Popped element : " + minEle); // Update minEle minEle = 2 * minEle - t; } // Else else { // Pop the topmost element System.out.println("Popped element : " + t); } Top--; return; } // Method to find the topmost // element of the stack static int peek() { // If stack is empty if (empty()) { System.out.println("Underflow"); return -1; } // Stores the top element // of the stack int t = arr[Top - 1]; // If t is less than // the minEle if (t < minEle) { return minEle; } // Else else { return t; } } // Method to find the Minimum // element of the Special stack static int getMin() { // If stack is empty if (empty()) { System.out.println("Underflow"); return -1; } // Else else { return minEle; } } // Driver code public static void main(String[] args) { push(10); push(4); push(9); push(6); push(5); System.out.println("Top Element : " + peek()); System.out.println("Minimum Element : " + getMin()); pop(); pop(); pop(); pop(); System.out.println("Top Element : " + peek()); System.out.println("Minimum Element : " + getMin()); }}// This code is contributed by rameshtravel07. |
Python3
# Python3 program for the above approach # Initial size of# the ArrayMax = 5# Array for the stack# implementationarr = [0]*Max# Stores the minimum# Element of the stackminEle = 0# Stores the top element# of the stackTop = 0# Method to check whether# stack is empty or notdef empty(): if (Top <= 0): return True else: return False# Method to push elements# to the Special Stackdef push(x): global arr, Top, Max, minEle # If stack is empty if empty(): # Assign x to minEle minEle = x # Assign x to arr[top] arr[Top] = x # Increment top by 1 Top+=1 # If array is full elif (Top == Max): # Update the Max size Max = 2 * Max temp = [0]*Max # Traverse the array arr[] for i in range(Top): temp[i] = arr[i] # If x is less than minEle if (x < minEle): # Push 2*x-minEle temp[Top] = 2 * x - minEle # Assign x to minEle minEle = x Top+=1 # Else else: # Push x to stack temp[Top] = x Top+=1 # Assign address of the # temp to arr arr = temp else: # If x is less # than minEle if (x < minEle): # Push 2*x-minEle arr[Top] = 2 * x - minEle Top+=1 # Update minEle minEle = x else: # Push x to the # stack arr[Top] = x Top+=1# Method to pop the elements# from the stack.def pop(): global Top, minEle # If stack is empty if empty(): print("Underflow") return # Stores the top element # of the stack t = arr[Top - 1] # If t is less than # the minEle if (t < minEle) : # Pop the minEle print("Popped element :", minEle) # Update minEle minEle = 2 * minEle - t # Else else: # Pop the topmost element print("Popped element :", t) Top-=1 return# Method to find the topmost# element of the stackdef peek(): # If stack is empty if empty(): print("Underflow") return -1 # Stores the top element # of the stack t = arr[Top - 1] # If t is less than # the minEle if (t < minEle): return minEle # Else else: return t# Method to find the Minimum# element of the Special stackdef getMin(): # If stack is empty if empty(): print("Underflow") return -1 # Else else: return minElepush(10)push(4)push(9)push(6)push(5)print("Top Element :", peek())print("Minimum Element :", getMin())pop()pop()pop()pop()print("Top Element :", peek())print("Minimum Element :", getMin())# This code is contributed by mukesh07. |
C#
// C# program for the above approachusing System;class GFG { // Initial size of // the Array static int Max = 5; // Array for the stack // implementation static int[] arr = new int[Max]; // Stores the minimum // Element of the stack static int minEle = 0; // Stores the top element // of the stack static int Top = 0; // Method to check whether // stack is empty or not static bool empty() { if (Top <= 0) { return true; } else { return false; } } // Method to push elements // to the Special Stack static void push(int x) { // If stack is empty if (empty()) { // Assign x to minEle minEle = x; // Assign x to arr[top] arr[Top] = x; // Increment top by 1 Top++; } // If array is full else if (Top == Max) { // Update the Max size Max = 2 * Max; int[] temp = new int[Max]; // Traverse the array arr[] for (int i = 0; i < Top; i++) { temp[i] = arr[i]; } // If x is less than minEle if (x < minEle) { // Push 2*x-minEle temp[Top] = 2 * x - minEle; // Assign x to minEle minEle = x; Top++; } // Else else { // Push x to stack temp[Top] = x; Top++; } // Assign address of the // temp to arr arr = temp; } else { // If x is less // than minEle if (x < minEle) { // Push 2*x-minEle arr[Top] = 2 * x - minEle; Top++; // Update minEle minEle = x; } else { // Push x to the // stack arr[Top] = x; Top++; } } } // Method to pop the elements // from the stack. static void pop() { // If stack is empty if (empty()) { Console.WriteLine("Underflow"); return; } // Stores the top element // of the stack int t = arr[Top - 1]; // If t is less than // the minEle if (t < minEle) { // Pop the minEle Console.WriteLine("Popped element : " + minEle); // Update minEle minEle = 2 * minEle - t; } // Else else { // Pop the topmost element Console.WriteLine("Popped element : " + t); } Top--; return; } // Method to find the topmost // element of the stack static int peek() { // If stack is empty if (empty()) { Console.WriteLine("Underflow"); return -1; } // Stores the top element // of the stack int t = arr[Top - 1]; // If t is less than // the minEle if (t < minEle) { return minEle; } // Else else { return t; } } // Method to find the Minimum // element of the Special stack static int getMin() { // If stack is empty if (empty()) { Console.WriteLine("Underflow"); return -1; } // Else else { return minEle; } } static void Main() { push(10); push(4); push(9); push(6); push(5); Console.WriteLine("Top Element : " + peek()); Console.WriteLine("Minimum Element : " + getMin()); pop(); pop(); pop(); pop(); Console.WriteLine("Top Element : " + peek()); Console.WriteLine("Minimum Element : " + getMin()); }}// This code is contributed by suresh07. |
Javascript
<script> // Javascript program for the above approach // Initial size of // the Array let Max = 5; // Array for the stack // implementation let arr = new Array(Max); // Stores the minimum // Element of the stack let minEle = 0; // Stores the top element // of the stack let Top = 0; // Method to check whether // stack is empty or not function empty() { if (Top <= 0) { return true; } else { return false; } } // Method to push elements // to the Special Stack function push(x) { // If stack is empty if (empty()) { // Assign x to minEle minEle = x; // Assign x to arr[top] arr[Top] = x; // Increment top by 1 Top++; } // If array is full else if (Top == Max) { // Update the Max size Max = 2 * Max; let temp = new Array(Max); // Traverse the array arr[] for (let i = 0; i < Top; i++) { temp[i] = arr[i]; } // If x is less than minEle if (x < minEle) { // Push 2*x-minEle temp[Top] = 2 * x - minEle; // Assign x to minEle minEle = x; Top++; } // Else else { // Push x to stack temp[Top] = x; Top++; } // Assign address of the // temp to arr arr = temp; } else { // If x is less // than minEle if (x < minEle) { // Push 2*x-minEle arr[Top] = 2 * x - minEle; Top++; // Update minEle minEle = x; } else { // Push x to the // stack arr[Top] = x; Top++; } } } // Method to pop the elements // from the stack. function pop() { // If stack is empty if (empty()) { document.write("Underflow" + "</br>"); return; } // Stores the top element // of the stack let t = arr[Top - 1]; // If t is less than // the minEle if (t < minEle) { // Pop the minEle document.write("Popped element : " + minEle + "</br>"); // Update minEle minEle = 2 * minEle - t; } // Else else { // Pop the topmost element document.write("Popped element : " + t + "</br>"); } Top--; return; } // Method to find the topmost // element of the stack function peek() { // If stack is empty if (empty()) { document.write("Underflow" + "</br>"); return -1; } // Stores the top element // of the stack let t = arr[Top - 1]; // If t is less than // the minEle if (t < minEle) { return minEle; } // Else else { return t; } } // Method to find the Minimum // element of the Special stack function getMin() { // If stack is empty if (empty()) { document.write("Underflow" + "</br>"); return -1; } // Else else { return minEle; } } push(10); push(4); push(9); push(6); push(5); document.write("Top Element : " + peek() + "</br>"); document.write("Minimum Element : " + getMin() + "</br>"); pop(); pop(); pop(); pop(); document.write("Top Element : " + peek() + "</br>"); document.write("Minimum Element : " + getMin() + "</br>"); // This code is contributed by divyesh072019.</script> |
Output
Top Element : 5 Minimum Element : 4 Popped element : 5 Popped element : 6 Popped element : 9 Popped element : 4 Top Element : 10 Minimum Element : 10
Time Complexity: O(1) for each operation
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
