ओ (एन) मध्ये अतिरिक्त जागा न वापरता स्टॅकला उलट करा.


अडचण पातळी सोपे
वारंवार विचारले फॅक्टसेट इन्फोसिस एमक्यू
दुवा साधलेली यादी स्टॅक

समस्या विधान

“ओ (एन) मध्ये अतिरिक्त जागा न वापरता स्टॅकला उलट करा” ही समस्या सांगते की आपल्याला ए स्टॅक डेटा रचना. अतिरिक्त ओ (एन) जागा न वापरता दिलेला स्टॅक उलट करा.

ओ (एन) मध्ये अतिरिक्त जागा न वापरता स्टॅकला उलट करा.

उदाहरण

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

ओ (एन) मध्ये अतिरिक्त जागा न वापरता स्टॅकला उलट करण्यासाठी अल्गोरिदम

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

ओ (एन) मध्ये अतिरिक्त जागा न वापरता स्टॅक उलटण्यासाठी जावा प्रोग्राम

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) जिथे डेटा स्ट्रक्चर स्टॅक मधील घटकांची संख्या असते. आम्ही स्टॅकच्या घटकांवर कार्य करण्यासाठी एकच लूप वापरला आहे. वेळेची जटिलता रेखीय असते.

स्पेस कॉम्प्लेक्सिटी

ओ (1) कारण आम्ही सतत अतिरिक्त जागा वापरत आहोत. इनपुट संचयित करण्यासाठी घेतलेली जागा अल्गोरिदमसाठी मोजली जाणार नाही. अशा प्रकारे जागेची जटिलता स्थिर आहे. परंतु संपूर्ण प्रोग्रामसाठी रेषात्मक अवकाश जटिलता आवश्यक आहे.