O (n) ൽ അധിക ഇടം ഉപയോഗിക്കാതെ ഒരു സ്റ്റാക്ക് വിപരീതമാക്കുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ഫാക്റ്റ്സെറ്റ് ഇൻഫോസിസ് MAQ
ലിങ്ക്ഡ്-ലിസ്റ്റ് കൂനകൂട്ടുക

പ്രശ്നം പ്രസ്താവന

“O (n) ൽ അധിക ഇടം ഉപയോഗിക്കാതെ ഒരു സ്റ്റാക്ക് റിവേഴ്സ് ചെയ്യുക” എന്ന പ്രശ്നം നിങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു സ്റ്റാക്ക് ഡാറ്റ ഘടന. അധിക 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 അപ്‌ഡേറ്റുചെയ്യുക.

കോഡ്

O (n) ൽ അധിക ഇടം ഉപയോഗിക്കാതെ ഒരു സ്റ്റാക്ക് റിവേഴ്സ് ചെയ്യുന്നതിനുള്ള സി ++ പ്രോഗ്രാം

#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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n) ഇവിടെ n എന്നത് ഡാറ്റാ സ്ട്രക്ചർ സ്റ്റാക്കിലെ ഘടകങ്ങളുടെ എണ്ണം. സ്റ്റാക്കിന്റെ ഘടകങ്ങളെ മറികടക്കാൻ ഞങ്ങൾ ഒരൊറ്റ ലൂപ്പ് ഉപയോഗിച്ചതിനാൽ. സമയ സങ്കീർണ്ണത രേഖീയമാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (1) കാരണം ഞങ്ങൾ സ്ഥിരമായ അധിക ഇടം ഉപയോഗിക്കുന്നു. ഇൻ‌പുട്ട് സംഭരിക്കുന്നതിന് എടുത്ത ഇടം അൽ‌ഗോരിതം കണക്കാക്കില്ല. അങ്ങനെ സ്ഥല സങ്കീർണ്ണത സ്ഥിരമാണ്. പക്ഷേ പ്രോഗ്രാമിന് മൊത്തത്തിൽ ലീനിയർ സ്പേസ് സങ്കീർണ്ണത ആവശ്യമാണ്.