הפוך ערימה מבלי להשתמש בשטח נוסף ב- O (n)


רמת קושי קַל
נשאל לעתים קרובות סט עובדות אינפוסיס מאק
רשימה מקושרת לערום

הצהרת בעיה

הבעיה "הפוך ערימה מבלי להשתמש בשטח נוסף ב- 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. צור צומת מחלקה המכילה משתנה שלם ומצביע הבא. צור בונה כיתות המקבל מספר שלם כפרמטר. הקצה את ערך הפרמטר למשתנה שלם והגדר את המצביע הבא כ- null בבונה.
  2. לאחר מכן, צור מעמד לערום ואתחל ראש מצביע של צומת סוג בו.
  3. צור דחיפת פונקציה () המקבלת מספר שלם כפרמטר. בדוק אם החלק העליון שווה ל- null צור צומת חדש עם מספר שלם נתון כנתונים ואחסן את הצומת החדש בראשו והחזירו.
  4. אחרת צור צומת חדש s עם נתון שלם נתון כנתונים. עדכן הבא של s כטופ העליון ו שווה ל- s.
  5. באופן דומה, צור פונקציית פופ (). צור צומת חדש ושמור את החלק העליון בתוכו. עדכן את החלק העליון כמו הבא של החלק העליון והחזיר את הצומת החדש.
  6. לאחר מכן, צור את הפונקציה הפוך (). צור שלושה צמתים המייצגים קודמים, נוכחיים ומצליחים בהתאמה. עדכן את הצומת הנוכחי והקודם כצומת העליון.
  7. עדכן את הצומת הנוכחי כמו הבא של הצומת הנוכחי ואת הבא של הצומת הקודם כ- null.
  8. בעוד שהצומת הנוכחי אינו אפס, עדכן את הצומת הבא כצומת הנוכחי, הבא של הצומת הנוכחי כצומת הקודם, הצומת הקודם כצומת הנוכחי והצומת הנוכחי כצומת הבא.
  9. עדכן את הצומת העליון כצומת הקודם.
  10. לבסוף צור תצוגת פונקציה () להצגת הערימה ההפוכה. צור צומת חדש ושמור את החלק העליון בתוכו. בעוד ש- אינו שווה ל- null, הדפיסו נתונים של s ועדכן את s כ- next של 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

תוכנית Java כדי להפוך ערימה מבלי להשתמש בשטח נוסף ב- 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) כי אנחנו משתמשים במרחב נוסף קבוע. מכיוון שהשטח שנדרש לאחסון הקלט לא ייספר לאלגוריתם. כך מורכבות החלל קבועה. אך התוכנית כולה דורשת מורכבות שטח לינארית.