O (1) ಸಮಯ ಮತ್ತು O (1) ಹೆಚ್ಚುವರಿ ಜಾಗದಲ್ಲಿ ಗೆಟ್‌ಮಿನ್ () ಅನ್ನು ಬೆಂಬಲಿಸುವ ಸ್ಟಾಕ್ ಅನ್ನು ವಿನ್ಯಾಸಗೊಳಿಸಿ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಡೋಬ್ ಅಮೆಜಾನ್ ಫ್ಯಾಕ್ಟ್‌ಸೆಟ್ ಫ್ಲಿಪ್ಕಾರ್ಟ್ ಗೋಲ್ಡ್ಮನ್ ಸ್ಯಾಚ್ಸ್ ಗ್ರೇ ಆರೆಂಜ್ ಕುಲಿಜಾ ಮೈಕ್ರೋಸಾಫ್ಟ್ ಪೇಟ್ಮ್ ಪಬ್ಲಿಸಿಸ್ ಸೇಪಿಯಂಟ್ ಸ್ಯಾಪ್ ಸ್ನ್ಯಾಪ್ಡಿಯಲ್ ವರೆ
ಸ್ಟಾಕ್

O (1) ಸಮಯ ಮತ್ತು O (1) ಹೆಚ್ಚುವರಿ ಜಾಗದಲ್ಲಿ ಗೆಟ್‌ಮಿನ್ () ಅನ್ನು ಬೆಂಬಲಿಸುವ ಸ್ಟಾಕ್ ಅನ್ನು ವಿನ್ಯಾಸಗೊಳಿಸಿ. ಹೀಗಾಗಿ ವಿಶೇಷ ಸ್ಟಾಕ್ ಡೇಟಾ ರಚನೆಯು ಸ್ಟಾಕ್ನ ಎಲ್ಲಾ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ಬೆಂಬಲಿಸಬೇಕು -

  • ಅನೂರ್ಜಿತ ಪುಶ್ ()
  • ಇಂಟ್ ಪಾಪ್ ()
  • bool isFull ()
  • bool isEmpty ()

ಸ್ಥಿರ ಸಮಯದಲ್ಲಿ. ವಿಶೇಷ ಸ್ಟ್ಯಾಕ್‌ನಲ್ಲಿ ಕನಿಷ್ಠ ಮೌಲ್ಯವನ್ನು ಸ್ಥಿರ ಸಮಯದಲ್ಲಿ ಮತ್ತು ಒ (1) ಹೆಚ್ಚುವರಿ ಜಾಗದಲ್ಲಿ ಹಿಂದಿರುಗಿಸಲು ಹೆಚ್ಚುವರಿ ಕಾರ್ಯಾಚರಣೆ ಗೆಟ್‌ಮಿನ್ () ಸೇರಿಸಿ.

O (1) ಸಮಯ ಮತ್ತು O (1) ಹೆಚ್ಚುವರಿ ಜಾಗದಲ್ಲಿ ಗೆಟ್‌ಮಿನ್ () ಅನ್ನು ಬೆಂಬಲಿಸುವ ಸ್ಟಾಕ್ ಅನ್ನು ವಿನ್ಯಾಸಗೊಳಿಸಿ

ಉದಾಹರಣೆ

push(30)
push(20)
push(10)
getMin()
pop()
getMin()
Minimum element : 10
Popped element : 10
Minimum element : 20
push(500)
push(50)
push(5)
getMin()
pop()
getMin()
Minimum element : 5
Popped element : 5
Minimum element : 50

ಮಿನ್‌ಸ್ಟ್ಯಾಕ್ ಅನ್ನು ಕಾರ್ಯಗತಗೊಳಿಸಲು ಗಣಿತ / ಗಮನಿಸಿದ ವಿಧಾನ

ಈ ವಿಧಾನದಲ್ಲಿ ನಾವು ಕನಿಷ್ಟ ಅಂಶವನ್ನು ನವೀಕರಿಸುತ್ತಿದ್ದೇವೆ -

ಪುಶ್ () ಕಾರ್ಯದಲ್ಲಿ ಪೂರ್ಣಾಂಕವನ್ನು ತಳ್ಳಬೇಕಾದರೆ ನಾವು ಕನಿಷ್ಟ ಅಂಶಕ್ಕಿಂತ ಕಡಿಮೆಯಿದ್ದರೆ ಆ ಪೂರ್ಣಾಂಕದ ಮೈನಸ್ ಕನಿಷ್ಠ ಅಂಶವನ್ನು ನಾವು ಸ್ಟ್ಯಾಕ್‌ನಲ್ಲಿ ಎರಡು ಬಾರಿ ಸೇರಿಸುತ್ತಿದ್ದೇವೆ ಅದು ಕೊಟ್ಟಿರುವ ಪೂರ್ಣಾಂಕಕ್ಕಿಂತ ಯಾವಾಗಲೂ ಚಿಕ್ಕದಾಗಿರುತ್ತದೆ -

  • ಕೊಟ್ಟಿರುವ ಪೂರ್ಣಾಂಕ <ಕನಿಷ್ಠ ಅಂಶ ಅಂದರೆ ಕೊಟ್ಟಿರುವ ಪೂರ್ಣಾಂಕ - ಕನಿಷ್ಠ ಅಂಶ <0
  • // ಎರಡೂ ಬದಿಗಳಲ್ಲಿ ಕೊಟ್ಟಿರುವ ಪೂರ್ಣಾಂಕವನ್ನು ಸೇರಿಸುವುದು
  • ಕೊಟ್ಟಿರುವ ಪೂರ್ಣಾಂಕ - ಕನಿಷ್ಠ ಅಂಶ + ಕೊಟ್ಟಿರುವ ಪೂರ್ಣಾಂಕ <0 + ನೀಡಿದ ಪೂರ್ಣಾಂಕ
  • 2 * ಕೊಟ್ಟಿರುವ ಪೂರ್ಣಾಂಕ - ಕನಿಷ್ಠ ಅಂಶ <ಕೊಟ್ಟಿರುವ ಪೂರ್ಣಾಂಕ
  • ನಾವು 2 * ಕೊಟ್ಟಿರುವ ಪೂರ್ಣಾಂಕವನ್ನು ತೀರ್ಮಾನಿಸಬಹುದು - ಕನಿಷ್ಠ ಅಂಶ <ಹೊಸ ಕನಿಷ್ಠ ಅಂಶ

ಆದ್ದರಿಂದ ಈ ಅಂಶವನ್ನು ಹೊರಹಾಕುವಾಗ ಅದು ಕನಿಷ್ಠ ಅಂಶಕ್ಕಿಂತ ಕಡಿಮೆಯಿರುತ್ತದೆ ಆದ್ದರಿಂದ ನಾವು ಕನಿಷ್ಟ ಅಂಶವನ್ನು ನವೀಕರಿಸುತ್ತೇವೆ.

ಅಂತೆಯೇ, ಪಾಪ್ () ಕಾರ್ಯದಲ್ಲಿ, ಪ್ರಸ್ತುತ ಅಂಶವು ಕನಿಷ್ಟ ಅಂಶಕ್ಕಿಂತ ಕಡಿಮೆಯಿದ್ದರೆ ನಾವು ಅದನ್ನು ನವೀಕರಿಸುತ್ತೇವೆ.

ಕ್ರಮಾವಳಿ

  1. ರಚನೆಯನ್ನು ಪ್ರಾರಂಭಿಸಿ ಹೊಸ ಸ್ಟ್ಯಾಕ್ ಮತ್ತು ಕಾರ್ಯವನ್ನು ರಚಿಸಿ ಪುಶ್ () ಅದರಲ್ಲಿ ಒಂದು ಪೂರ್ಣಾಂಕವನ್ನು ನಿಯತಾಂಕವಾಗಿ ಸ್ವೀಕರಿಸುತ್ತದೆ.
  2. ಸ್ಟಾಕ್ ಖಾಲಿಯಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ, ಸಂಗ್ರಹಿಸಿ ಪೂರ್ಣಾಂಕ ವೇರಿಯಬಲ್ ನಿಮಿಷದಲ್ಲಿ, ಪೂರ್ಣಾಂಕವನ್ನು ಸ್ಟ್ಯಾಕ್‌ನಲ್ಲಿ ಸೇರಿಸಿ ಮತ್ತು ಹಿಂತಿರುಗಿ.
  3. ಪೂರ್ಣಾಂಕವು ನಿಮಿಷಕ್ಕಿಂತ ಕಡಿಮೆಯಿದ್ದರೆ 2 * x - ನಿಮಿಷವನ್ನು ಸ್ಟಾಕ್‌ನಲ್ಲಿ ಸೇರಿಸಿ ಮತ್ತು ನಿಮಿಷವನ್ನು x ಎಂದು ನವೀಕರಿಸಿ.
  4. ಇಲ್ಲದಿದ್ದರೆ ಪೂರ್ಣಾಂಕವನ್ನು ಸ್ಟಾಕ್‌ನಲ್ಲಿ ತಳ್ಳಿರಿ.
  5. ಪಾಪ್ () ಕಾರ್ಯವನ್ನು ರಚಿಸಿ. ಸ್ಟಾಕ್ ಖಾಲಿಯಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ “ಸ್ಟಾಕ್ ಖಾಲಿಯಾಗಿದೆ” ಮತ್ತು ಹಿಂತಿರುಗಿ.
  6. ಇಲ್ಲದಿದ್ದರೆ ಅಂಶವನ್ನು ಸ್ಟ್ಯಾಕ್‌ನ ಮೇಲ್ಭಾಗದಲ್ಲಿ ವೇರಿಯಬಲ್ ಟಿ ಯಲ್ಲಿ ಸಂಗ್ರಹಿಸಿ ಮತ್ತು ಮೇಲಿನ ಅಂಶವನ್ನು ಸ್ಟ್ಯಾಕ್‌ನಿಂದ ತೆಗೆದುಹಾಕಿ / ತೆಗೆದುಹಾಕಿ.
  7. ಟಿ ನಿಮಿಷ ಮುದ್ರಣ ನಿಮಿಷಕ್ಕಿಂತ ಕಡಿಮೆಯಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ ಮತ್ತು ನಿಮಿಷವನ್ನು 2 * ನಿಮಿಷ - ಟಿ ಎಂದು ನವೀಕರಿಸಿ.
  8. ಬೇರೆ ಮುದ್ರಣ ಟಿ.
  9. GetMin () ಕಾರ್ಯವನ್ನು ರಚಿಸಿ ಮತ್ತು ಸ್ಟಾಕ್ ಖಾಲಿಯಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ “ಸ್ಟಾಕ್ ಖಾಲಿಯಾಗಿದೆ”.
  10. ಇಲ್ಲದಿದ್ದರೆ ಕನಿಷ್ಠ ಅಂಶವನ್ನು ಹಿಂತಿರುಗಿಸಿ.

ಕೋಡ್

ಮಿನ್‌ಸ್ಟ್ಯಾಕ್‌ಗಾಗಿ ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#include <bits/stdc++.h> 
using namespace std; 
  
struct newStack{ 
    stack<int> s; 
    int min; 
  
    void getMin(){ 
        if(s.empty()){ 
            cout<<"Stack is empty\n"; 
        }
        else{
            cout<<"Minimum element : "<<min<<"\n"; 
        }    
    } 
  
    void pop(){ 
        if(s.empty()){ 
            cout<<"Stack is empty\n"; 
            return; 
        } 
  
        cout<<"Popped element : "; 
        int t = s.top(); 
        s.pop(); 
  
        if(t<min){ 
            cout<<min<< "\n"; 
            min = 2*min - t; 
        } 
  
        else{
            cout<<t<< "\n";
        }    
    } 
  
    void push(int x){ 
        if(s.empty()){ 
            min = x; 
            s.push(x); 
            return; 
        } 
  
        if(x < min){ 
            s.push(2*x - min); 
            min = x; 
        } 
  
        else{
           s.push(x);
        }   
    } 
}; 
 
int main(){
    newStack s; 
    
    s.push(30);
    s.push(20);
    s.push(10);
    s.getMin();
    s.pop();
    s.getMin();
  
    return 0; 
}
Minimum element : 10
Popped element : 10
Minimum element : 20

ಮಿನ್‌ಸ್ಟ್ಯಾಕ್‌ಗಾಗಿ ಜಾವಾ ಪ್ರೋಗ್ರಾಂ

import java.util.*; 
  
class newStack{ 
    Stack<Integer> s; 
    Integer min; 
  
    newStack(){ 
        s = new Stack<Integer>(); 
    } 
  
    void getMin(){ 
        if(s.isEmpty()) 
            System.out.println("Stack is empty"); 
  
        else{
            System.out.println("Minimum element : " + min);
        }    
    } 
  
    void pop(){ 
        if (s.isEmpty()){ 
            System.out.println("Stack is empty"); 
            return; 
        } 
  
        System.out.print("Popped element : "); 
        Integer t = s.pop(); 
  
        if(t<min){ 
            System.out.println(min); 
            min = 2*min - t; 
        } 
  
        else{
            System.out.println(t);
        }    
    } 
  
    void push(Integer x){ 
        if(s.isEmpty()){ 
            min = x; 
            s.push(x); 
            return; 
        } 
  
        if(x<min){ 
            s.push(2*x - min); 
            min = x; 
        } 
  
        else{
            s.push(x); 
        }    
    } 
}; 
  
public class Main{ 
    public static void main(String[] args){ 
        newStack s = new newStack(); 
        
        s.push(30);
        s.push(20);
        s.push(10);
        s.getMin();
        s.pop();
        s.getMin();
        
    } 
}
Minimum element : 10
Popped element : 10
Minimum element : 20

ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (1) ಪ್ರತಿ ಕಾರ್ಯಾಚರಣೆಗೆ, ಎಲ್ಲಾ ಕಾರ್ಯಾಚರಣೆಗಳನ್ನು ಸ್ಥಿರ ಸಮಯದಲ್ಲಿ ಮಾಡಲಾಗುತ್ತಿದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (1) ಏಕೆಂದರೆ ನಾವು ನಿರಂತರ ಸಹಾಯಕ ಸ್ಥಳವನ್ನು ಬಳಸುತ್ತಿದ್ದೇವೆ. ಇನ್ಪುಟ್ ಸಂಗ್ರಹಿಸಲು ಬೇಕಾದ ಸ್ಥಳವು ಅಲ್ಗಾರಿದಮ್ನ ಸ್ಥಳ ಸಂಕೀರ್ಣತೆಗೆ ಎಣಿಸುವುದಿಲ್ಲ.