بدون استفاده از فضای اضافی در O (n) یک پشته را معکوس کنید


سطح دشواری ساده
اغلب در واقعیت Infosys در MAQ
لینک شده پشته

بیان مسأله

مسئله "یک پشته را معکوس کنید بدون استفاده از فضای اضافی در O (n)" بیان می کند که به شما a داده می شود پشته ساختار داده ها. پشته داده شده را بدون استفاده از فضای اضافی 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. یک تابع push () ایجاد کنید که یک عدد صحیح را به عنوان پارامتر بپذیرد. بررسی کنید که آیا top برابر است با null ، یک گره جدید با عدد صحیح داده شده ایجاد کرده و گره جدید را در بالا ذخیره کرده و برمی گردانید.
  4. در غیر اینصورت یک گره جدید ایجاد کنید s با عدد صحیح داده شده به روزرسانی بعدی s به عنوان بالا و بالا برابر است با s.
  5. به همین ترتیب ، یک تابع pop () ایجاد کنید. یک گره جدید ایجاد کنید و قسمت بالای آن را در آن ذخیره کنید. بالا را به عنوان بعدی از بالا به روز کنید و گره های جدید را برگردانید.
  6. بعد از آن ، تابع reverse () ایجاد کنید. سه گره به ترتیب نمایانگر قبلی ، فعلی و موفق ایجاد کنید. گره فعلی و قبلی را به عنوان گره بالایی به روز کنید.
  7. گره فعلی را به عنوان گره بعدی و گره بعدی بعدی را به عنوان null به روز کنید.
  8. گرچه گره فعلی خالی نیست ، گره بعدی را به عنوان گره بعدی ، بعدی گره فعلی را به عنوان گره previos ، گره قبلی را به عنوان گره فعلی و گره فعلی را به عنوان گره بعدی به روز کنید.
  9. گره بالا را به عنوان گره قبلی به روز کنید.
  10. در آخر یک نمایش عملکرد () ایجاد کنید تا پشته معکوس نمایش داده شود. یک گره جدید ایجاد کنید و قسمت بالای آن را در آن ذخیره کنید. در حالی که s برابر با null نیست ، داده های s را چاپ کنید و 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

تحلیل پیچیدگی

پیچیدگی زمان

O (N) که n تعداد عناصر موجود در پشته ساختار داده است. از آنجا که ما برای اجرای عناصر پشته از یک حلقه استفاده کرده ایم. پیچیدگی زمان خطی است.

پیچیدگی فضا

O (1) زیرا ما از فضای اضافی ثابت استفاده می کنیم. از آنجا که فضای ذخیره شده ورودی برای الگوریتم محاسبه نمی شود. بنابراین پیچیدگی فضا ثابت است. اما این برنامه به طور کلی به پیچیدگی فضای خطی نیاز دارد.