O (n) में अतिरिक्त स्थान का उपयोग किए बिना एक स्टैक को उल्टा करें


कठिनाई स्तर आसान
में अक्सर पूछा FactSet इंफोसिस 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. पूर्णांक चर और अगला पॉइंटर वाला एक वर्ग नोड बनाएं। एक वर्ग निर्माता बनाएँ जो स्वीकार करता है a पूर्णांक पैरामीटर के रूप में। पूर्णांक चर के लिए पैरामीटर मान असाइन करें और अगले पॉइंटर को निर्माता के रूप में शून्य सेट करें।
  2. इसके बाद क्लास बनाएं धुआँरा और इसमें एक पॉइंटर प्रकार का नोड प्रारंभ करें।
  3. एक फ़ंक्शन पुश () बनाएं जो एक पूर्णांक को पैरामीटर के रूप में स्वीकार करता है। जांचें कि क्या शीर्ष डेटा के रूप में दिए गए पूर्णांक के साथ एक नया नोड बनाने के लिए शून्य के बराबर है और शीर्ष और वापसी में नए नोड को संग्रहीत करें।
  4. एल्स एक नया नोड बनाते हैं s डेटा के रूप में पूर्णांक दिया गया है। एस के बगल में अपडेट करें क्योंकि शीर्ष और शीर्ष एस के बराबर है।
  5. इसी तरह, एक फ़ंक्शन पॉप () बनाएं। एक नया नोड बनाएं और उसमें शीर्ष स्टोर करें। शीर्ष के रूप में शीर्ष अपडेट करें और नया नोड एस वापस करें।
  6. उसके बाद, फ़ंक्शन को रिवर्स बनाएं ()। पिछले, वर्तमान और सफल होने का प्रतिनिधित्व करने वाले तीन नोड बनाएं। वर्तमान और पिछले नोड को शीर्ष नोड के रूप में अपडेट करें।
  7. वर्तमान नोड के रूप में और नोड के रूप में पिछले नोड के अगले के रूप में वर्तमान नोड अपडेट करें।
  8. जबकि वर्तमान नोड शून्य नहीं है, वर्तमान नोड के अगले के रूप में सफल नोड को अपडेट करें, पूर्व नोड के रूप में वर्तमान नोड के बगल में, वर्तमान नोड को वर्तमान नोड के रूप में और वर्तमान नोड को सफल नोड के रूप में।
  9. पिछले नोड के रूप में शीर्ष नोड अपडेट करें।
  10. अंत में उलटे हुए स्टैक को प्रदर्शित करने के लिए एक फंक्शन डिस्प्ले () बनाएं। एक नया नोड बनाएं और उसमें शीर्ष स्टोर करें। जबकि s, n के बराबर नहीं है, s का डेटा प्रिंट करें और s के अगले के रूप में अपडेट करें।

कोड

C ++ 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

जटिलता विश्लेषण

समय जटिलता

पर) जहाँ n डेटा संरचना स्टैक में तत्वों की संख्या है। चूंकि हमने स्टैक के तत्वों पर चलने के लिए एक ही लूप का उपयोग किया है। समय जटिलता रैखिक है।

अंतरिक्ष जटिलता

ओ (1) क्योंकि हम निरंतर अतिरिक्त स्थान का उपयोग कर रहे हैं। चूंकि इनपुट को संग्रहीत करने के लिए लिया गया स्थान एल्गोरिथ्म के लिए नहीं गिना जाएगा। इस प्रकार अंतरिक्ष जटिलता स्थिर है। लेकिन एक पूरे के रूप में कार्यक्रम को रैखिक अंतरिक्ष जटिलता की आवश्यकता होती है।