O (n) ನಲ್ಲಿ ಹೆಚ್ಚುವರಿ ಸ್ಥಳವನ್ನು ಬಳಸದೆ ಸ್ಟಾಕ್ ಅನ್ನು ಹಿಮ್ಮುಖಗೊಳಿಸಿ


ತೊಂದರೆ ಮಟ್ಟ ಸುಲಭ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಫ್ಯಾಕ್ಟ್‌ಸೆಟ್ ಇನ್ಫೋಸಿಸ್ MAQ
ಲಿಂಕ್ಡ್-ಲಿಸ್ಟ್ ಸ್ಟಾಕ್

ಸಮಸ್ಯೆ ಹೇಳಿಕೆ

“O (n) ನಲ್ಲಿ ಹೆಚ್ಚುವರಿ ಜಾಗವನ್ನು ಬಳಸದೆ ಸ್ಟಾಕ್ ಅನ್ನು ಹಿಮ್ಮುಖಗೊಳಿಸಿ” ಎಂಬ ಸಮಸ್ಯೆ ನಿಮಗೆ ನೀಡಲಾಗಿದೆ ಎಂದು ಹೇಳುತ್ತದೆ ಸ್ಟಾಕ್ ಡೇಟಾ ರಚನೆ. ಹೆಚ್ಚುವರಿ ಒ (ಎನ್) ಜಾಗವನ್ನು ಬಳಸದೆ ಕೊಟ್ಟಿರುವ ಸ್ಟ್ಯಾಕ್ ಅನ್ನು ಹಿಮ್ಮುಖಗೊಳಿಸಿ.

O (n) ನಲ್ಲಿ ಹೆಚ್ಚುವರಿ ಸ್ಥಳವನ್ನು ಬಳಸದೆ ಸ್ಟಾಕ್ ಅನ್ನು ಹಿಮ್ಮುಖಗೊಳಿಸಿ

ಉದಾಹರಣೆ

5 4 3 2 1
1 2 3 4 5
80 60 10 20
20 10 60 80

O (n) ನಲ್ಲಿ ಹೆಚ್ಚುವರಿ ಜಾಗವನ್ನು ಬಳಸದೆ ಸ್ಟಾಕ್ ಅನ್ನು ಹಿಮ್ಮುಖಗೊಳಿಸುವ ಅಲ್ಗಾರಿದಮ್

  1. ಪೂರ್ಣಾಂಕ ವೇರಿಯಬಲ್ ಮತ್ತು ಮುಂದಿನ ಪಾಯಿಂಟರ್ ಹೊಂದಿರುವ ವರ್ಗ ನೋಡ್ ಅನ್ನು ರಚಿಸಿ. ಸ್ವೀಕರಿಸುವ ವರ್ಗ ಕನ್‌ಸ್ಟ್ರಕ್ಟರ್ ಅನ್ನು ರಚಿಸಿ ಪೂರ್ಣಾಂಕ ನಿಯತಾಂಕವಾಗಿ. ಪ್ಯಾರಾಮೀಟರ್ ಮೌಲ್ಯವನ್ನು ಪೂರ್ಣಾಂಕ ವೇರಿಯೇಬಲ್‌ಗೆ ನಿಗದಿಪಡಿಸಿ ಮತ್ತು ಮುಂದಿನ ಪಾಯಿಂಟರ್ ಅನ್ನು ಕನ್‌ಸ್ಟ್ರಕ್ಟರ್‌ನಲ್ಲಿ ಶೂನ್ಯ ಎಂದು ಹೊಂದಿಸಿ.
  2. ಅದರ ನಂತರ, ವರ್ಗವನ್ನು ರಚಿಸಿ ಸ್ಟಾಕ್ ಮತ್ತು ಅದರಲ್ಲಿ ಟೈಪ್ ನೋಡ್‌ನ ಪಾಯಿಂಟರ್ ಟಾಪ್ ಅನ್ನು ಪ್ರಾರಂಭಿಸಿ.
  3. ಒಂದು ಪೂರ್ಣಾಂಕವನ್ನು ನಿಯತಾಂಕವಾಗಿ ಸ್ವೀಕರಿಸುವ ಕಾರ್ಯ ಪುಶ್ () ಅನ್ನು ರಚಿಸಿ. ಮೇಲ್ಭಾಗವು ಶೂನ್ಯಕ್ಕೆ ಸಮವಾಗಿದೆಯೇ ಎಂದು ಪರಿಶೀಲಿಸಿ, ನಿರ್ದಿಷ್ಟ ಪೂರ್ಣಾಂಕದೊಂದಿಗೆ ಡೇಟಾದಂತೆ ಹೊಸ ನೋಡ್ ಅನ್ನು ರಚಿಸಿ ಮತ್ತು ಹೊಸ ನೋಡ್ ಅನ್ನು ಮೇಲ್ಭಾಗದಲ್ಲಿ ಸಂಗ್ರಹಿಸಿ ಮತ್ತು ಹಿಂತಿರುಗಿ.
  4. ಇಲ್ಲದಿದ್ದರೆ ಹೊಸ ನೋಡ್ ರಚಿಸಿ s ನಿರ್ದಿಷ್ಟ ಪೂರ್ಣಾಂಕದೊಂದಿಗೆ ಡೇಟಾದೊಂದಿಗೆ. S ನ ಮುಂದಿನದನ್ನು ಮೇಲ್ಭಾಗ ಮತ್ತು ಮೇಲ್ಭಾಗವು s ​​ಗೆ ಸಮನಾಗಿ ನವೀಕರಿಸಿ.
  5. ಅಂತೆಯೇ, ಪಾಪ್ () ಎಂಬ ಕಾರ್ಯವನ್ನು ರಚಿಸಿ. ಹೊಸ ನೋಡ್ ಗಳನ್ನು ರಚಿಸಿ ಮತ್ತು ಅದರ ಮೇಲ್ಭಾಗವನ್ನು ಸಂಗ್ರಹಿಸಿ. ಮೇಲ್ಭಾಗವನ್ನು ಮುಂದಿನ ಮೇಲ್ಭಾಗದಲ್ಲಿ ನವೀಕರಿಸಿ ಮತ್ತು ಹೊಸ ನೋಡ್ ಗಳನ್ನು ಹಿಂತಿರುಗಿ.
  6. ಅದರ ನಂತರ, ರಿವರ್ಸ್ () ಕಾರ್ಯವನ್ನು ರಚಿಸಿ. ಹಿಂದಿನ, ಪ್ರಸ್ತುತ ಮತ್ತು ಯಶಸ್ವಿಯಾಗಿ ಪ್ರತಿನಿಧಿಸುವ ಮೂರು ನೋಡ್‌ಗಳನ್ನು ರಚಿಸಿ. ಪ್ರಸ್ತುತ ಮತ್ತು ಹಿಂದಿನ ನೋಡ್ ಅನ್ನು ಟಾಪ್ ನೋಡ್ ಆಗಿ ನವೀಕರಿಸಿ.
  7. ಪ್ರಸ್ತುತ ನೋಡ್ ಅನ್ನು ಪ್ರಸ್ತುತ ನೋಡ್ನ ಮುಂದಿನ ಮತ್ತು ಹಿಂದಿನ ನೋಡ್ನ ಮುಂದಿನದನ್ನು ಶೂನ್ಯವಾಗಿ ನವೀಕರಿಸಿ.
  8. ಪ್ರಸ್ತುತ ನೋಡ್ ಶೂನ್ಯವಾಗಿಲ್ಲದಿದ್ದರೂ, ನಂತರದ ನೋಡ್ ಅನ್ನು ಮುಂದಿನ ನೋಡ್‌ನಂತೆ, ಪ್ರಸ್ತುತ ನೋಡ್‌ನ ಮುಂದಿನದನ್ನು ಪ್ರಿವಿಯೋಸ್ ನೋಡ್‌ನಂತೆ, ಹಿಂದಿನ ನೋಡ್ ಅನ್ನು ಪ್ರಸ್ತುತ ನೋಡ್‌ನಂತೆ ಮತ್ತು ಪ್ರಸ್ತುತ ನೋಡ್ ಅನ್ನು ಮುಂದಿನ ನೋಡ್‌ನಂತೆ ನವೀಕರಿಸಿ.
  9. ಮೇಲಿನ ನೋಡ್ ಅನ್ನು ಹಿಂದಿನ ನೋಡ್‌ನಂತೆ ನವೀಕರಿಸಿ.
  10. ರಿವರ್ಸ್ಡ್ ಸ್ಟ್ಯಾಕ್ ಅನ್ನು ಪ್ರದರ್ಶಿಸಲು ಅಂತಿಮವಾಗಿ ಫಂಕ್ಷನ್ ಡಿಸ್ಪ್ಲೇ () ಅನ್ನು ರಚಿಸಿ. ಹೊಸ ನೋಡ್ ಗಳನ್ನು ರಚಿಸಿ ಮತ್ತು ಅದರ ಮೇಲ್ಭಾಗವನ್ನು ಸಂಗ್ರಹಿಸಿ. S ಶೂನ್ಯಕ್ಕೆ ಸಮನಾಗಿರದಿದ್ದರೂ, s ನ ಡೇಟಾವನ್ನು ಮುದ್ರಿಸಿ ಮತ್ತು s ನ ಮುಂದಿನದನ್ನು s ನಂತೆ ನವೀಕರಿಸಿ.

ಕೋಡ್

ಒ (ಎನ್) ನಲ್ಲಿ ಹೆಚ್ಚುವರಿ ಜಾಗವನ್ನು ಬಳಸದೆ ಸ್ಟಾಕ್ ಅನ್ನು ಹಿಮ್ಮುಖಗೊಳಿಸಲು ಸಿ ++ ಪ್ರೋಗ್ರಾಂ

#include<bits/stdc++.h> 
using namespace std; 
  
class Node { 
    public: 
        int data; 
        Node *next; 
          
        Node(int data){ 
            this->data = data; 
            this->next = NULL; 
        } 
}; 
  
class Stack{ 
      
    Node *top; 
      
    public: 
      
        void push(int data){ 
            if (top == NULL) { 
                top = new Node(data); 
                return; 
            } 
            Node *s = new Node(data); 
            s->next = top; 
            top = s; 
        } 
          
        Node* pop(){ 
            Node *s = top; 
            top = top->next; 
            return s; 
        } 
      
        void display(){ 
            Node *s = top; 
            while (s != NULL) { 
                cout << s->data << " "; 
                s = s->next; 
            } 
            cout << endl; 
        } 
      
        void reverse(){ 
            Node *prev, *cur, *succ; 
            cur = prev = top; 
            cur = cur->next; 
            prev->next = NULL; 
            while (cur != NULL) { 
                succ = cur->next; 
                cur->next = prev; 
                prev = cur; 
                cur = succ; 
            } 
            top = prev; 
        } 
}; 
  
int main(){ 
    Stack *s = new Stack(); 
    
    s->push(1); 
    s->push(2); 
    s->push(3); 
    s->push(4);
    s->push(5);
    
    s->reverse(); 
  
    s->display(); 
      
    return 0; 
}
1 2 3 4 5

O (n) ನಲ್ಲಿ ಹೆಚ್ಚುವರಿ ಸ್ಥಳವನ್ನು ಬಳಸದೆ ಸ್ಟಾಕ್ ಅನ್ನು ಹಿಮ್ಮುಖಗೊಳಿಸಲು ಜಾವಾ ಪ್ರೋಗ್ರಾಂ

class Node{ 
    int data; 
    Node next; 
    
    public Node(int data){ 
        this.data = data; 
        this.next = null; 
    } 
} 
  
class Stack{ 
    Node top; 
  
    public void push(int data){ 
        if (this.top == null){ 
            top = new Node(data); 
            return; 
        } 
        
        Node s = new Node(data); 
        s.next = this.top; 
        this.top = s; 
    } 
    
    public Node pop(){ 
        Node s = this.top; 
        this.top = this.top.next; 
        return s; 
    } 
  
    public void display(){ 
        Node s = this.top; 
        
        while (s != null){ 
            System.out.print(s.data + " "); 
            s = s.next; 
        } 
        
    } 
  
    public void reverse(){
        
        Node prev, cur, succ; 
        
        cur = prev = this.top; 
        cur = cur.next; 
        prev.next = null; 
        
        while(cur != null){ 
            succ = cur.next; 
            cur.next = prev; 
            prev = cur; 
            cur = succ; 
        } 
        
        this.top = prev; 
    } 
} 
  
class reverseStack{ 
    
    public static void main(String[] args){ 
        
        Stack s = new Stack(); 
        
        s.push(1); 
        s.push(2); 
        s.push(3); 
        s.push(4);
        s.push(5);
        
        s.reverse(); 
  
        s.display(); 
    } 
}
1 2 3 4 5

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

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

ಓ (ಎನ್) ಇಲ್ಲಿ n ಎನ್ನುವುದು ಡೇಟಾ ರಚನೆ ಸ್ಟ್ಯಾಕ್‌ನಲ್ಲಿರುವ ಅಂಶಗಳ ಸಂಖ್ಯೆ. ಸ್ಟಾಕ್ನ ಅಂಶಗಳ ಮೇಲೆ ಚಲಿಸಲು ನಾವು ಒಂದೇ ಲೂಪ್ ಅನ್ನು ಬಳಸಿದ್ದೇವೆ. ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ರೇಖೀಯವಾಗಿದೆ.

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

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