পুনরাবৃত্তি ব্যবহার করে একটি স্ট্যাক সাজান


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক গোল্ডম্যান শ্যাস আইবিএম কুলিজা নরপশু
recursion গাদা

সমস্যা বিবৃতি

সমস্যা "পুনরাবৃত্তি ব্যবহার করে একটি স্ট্যাক বাছাই করুন" বলে যে আপনাকে একটি দেওয়া হয় গাদা তথ্য কাঠামো. বাছাই করা এর উপাদানগুলি পুনরাবৃত্তি ব্যবহার করে। স্ট্যাকের কেবল নীচের তালিকাভুক্ত ফাংশনগুলি ব্যবহার করা যেতে পারে -

  • চাপ (উপাদান) - স্ট্যাক মধ্যে উপাদান সন্নিবেশ।
  • পপ () - পপ () - প্রদত্ত স্ট্যাকের শীর্ষে উপাদানটি সরিয়ে / মুছতে।
  • isEmpty () - স্ট্যাকের কোনও উপাদান রয়েছে কিনা তা পরীক্ষা করতে।
  • শীর্ষ () - প্রদত্ত স্ট্যাকের শীর্ষে উপাদানটি উঁকি দেওয়া / দেখার জন্য।

পুনরাবৃত্তি ব্যবহার করে একটি স্ট্যাক সাজান

উদাহরণ

9 4 2 -1 6 20
20 9 6 4 2 -1

ব্যাখ্যা: যেহেতু স্ট্যাকটি ক্রমবর্ধমান ক্রমে সাজানো হয়েছে। সর্বাধিক উপাদান শীর্ষে আসে। স্ট্যাকটি LIFO ডেটা স্ট্রাকচার হওয়ায় আউটপুটটি ক্রমবর্ধমান ক্রমে মনে হয়।

2 1 4 3 6 5
6 5 4 3 2 1

অ্যালগরিদম

  1. সূচনা a গাদা এবং এতে উপাদানগুলিকে চাপ দিন।
  2. স্ট্যাকটিতে সাজানো ক্রমে উপাদানগুলি সন্নিবেশ করতে একটি ফাংশন তৈরি করুন যা একটি স্ট্যাক এবং একটি উপাদানকে প্যারামিটার হিসাবে গ্রহণ করে। স্ট্যাকটি খালি আছে কিনা তা পরীক্ষা করুন বা প্রদত্ত উপাদানটি স্ট্যাকের শীর্ষে থাকা উপাদানের চেয়ে বড় কিনা, উপাদানটিকে স্ট্যাকের মধ্যে চাপুন এবং ফিরে আসুন।
  3. একটি অস্থায়ী পরিবর্তনশীল তৈরি করুন এবং এতে স্ট্যাকের শীর্ষটি সংরক্ষণ করুন। স্ট্যাকের শীর্ষে উপাদানটি পপ করুন এবং ফাংশনে নিজেই পুনরাবৃত্ত কল করুন call স্ট্যাকের মধ্যে অস্থায়ী পরিবর্তনশীল টিপুন।
  4. একইভাবে, একটি ফাংশন সাজান () তৈরি করুন যা স্ট্যাকটিকে প্যারামিটার হিসাবে গ্রহণ করে। স্ট্যাকটি খালি নেই কিনা তা পরীক্ষা করুন, একটি ভেরিয়েবল এক্স তৈরি করুন এবং এতে স্ট্যাকের শীর্ষটি সংরক্ষণ করুন। স্ট্যাকের শীর্ষে উপাদানটি পপ করুন। ফাংশনে নিজেই একটি পুনরাবৃত্ত কল করুন। স্ট্যাকের মধ্যে সাজানো ক্রমে উপাদানগুলি সন্নিবেশ করতে ফাংশনটি কল করুন।
  5. মূল () এ বাছাই ফাংশন কল করুন।
  6. বাছাই করা স্ট্যাক মুদ্রণের জন্য একটি ফাংশন তৈরি করুন যা স্ট্যাকটিকে প্যারামিটার হিসাবে গ্রহণ করে। স্ট্যাক খালি না থাকাকালীন ট্র্যাভার্স করুন, স্ট্যাকের ডেটা প্রিন্ট করুন এবং পরবর্তী উপাদানটিতে যান।

কোড

পুনরাবৃত্তি ব্যবহার করে একটি স্ট্যাককে সাজানোর জন্য সি ++ প্রোগ্রাম

#include <iostream> 
using namespace std; 
  
struct stack{  
    int data;  
    struct stack *next;  
};  
  
void initStack(struct stack **s){  
    *s = NULL;  
}  
  
int isEmpty(struct stack *s){  
    if(s == NULL){  
        return 1;  
    }    
    return 0;  
}  
  
void push(struct stack **s, int x){
    
    struct stack *p = (struct stack *)malloc(sizeof(*p));  
  
    if(p == NULL){  
        return;  
    }  
  
    p->data = x;  
    p->next = *s;  
    *s = p;  
}  
  
int pop(struct stack **s){  
    int x;  
    struct stack *temp;  
  
    x = (*s)->data;  
    temp = *s;  
    (*s) = (*s)->next;  
    free(temp);  
  
    return x;  
}  
  
int top(struct stack *s){  
    return (s->data);  
}  
  
void InsertWithSort(struct stack **s, int x){  
    
    if(isEmpty(*s) or x > top(*s)){  
        push(s, x);  
        return;  
    }  
  
    int temp = pop(s);  
    InsertWithSort(s, x);  
  
    push(s, temp);  
}  
  
void sort(struct stack **s){  
    
    if(!isEmpty(*s)){  
        int x = pop(s);  
  
        sort(s);  
  
        InsertWithSort(s, x);  
    }  
}  
  
void print(struct stack *s){  
    while(s){  
        cout<<s->data<<" "; 
        s = s->next;  
    }  
}  
  
int main(){  
    struct stack *top;  
  
    initStack(&top);
    
    push(&top, 9);  
    push(&top, 4);  
    push(&top, 2);  
    push(&top, -1);  
    push(&top, 6);
    push(&top, 20);
  
    sort(&top);  
    
    print(top);  
  
    return 0;  
}
20 9 6 4 2 -1

পুনরাবৃত্তি ব্যবহার করে একটি স্ট্যাক সাজানোর জন্য জাভা প্রোগ্রাম

import java.util.ListIterator; 
import java.util.Stack; 
  
class SortStack{ 
    
    static void InsertWithSort(Stack<Integer> s, int x){ 
        if (s.isEmpty() || x > s.peek()){ 
            s.push(x); 
            return; 
        } 
       
        int temp = s.pop(); 
        InsertWithSort(s, x); 
       
        s.push(temp); 
    } 
       
    static void sort(Stack<Integer> s){ 
        if(!s.isEmpty()){ 
            int x = s.pop(); 
       
            sort(s); 
       
            InsertWithSort(s, x); 
        } 
    } 
      
    static void print(Stack<Integer> s){ 
       ListIterator<Integer> lt = s.listIterator(); 
         
        while(lt.hasNext()){ 
            lt.next(); 
        }       
         
        while(lt.hasPrevious()){ 
           System.out.print(lt.previous()+" ");
        }   
    } 
    
    public static void main(String[] args){
        Stack<Integer> s = new Stack<>(); 
        
        s.push(9);  
        s.push(4);  
        s.push(2);  
        s.push(-1);  
        s.push(6);
        s.push(20); 
       
        sort(s); 
       
        print(s); 
       
    } 
}
20 9 6 4 2 -1

জটিলতা বিশ্লেষণ

সময় জটিলতা

ও (এন ^ 2) যেখানে n হল স্ট্যাকের উপাদানগুলির সংখ্যা। কারণ যখন আমরা স্ট্যাকের উপাদানটিকে চাপ দিই তখন আমরা স্ট্যাকের মধ্যে উপস্থিত সমস্ত উপাদানগুলি সরিয়ে শেষ করে সন্নিবেশ করতে পারি। ইনপুট হ্রাস ক্রমে থাকলে এই কেসটি ঘটে।

স্পেস জটিলতা ity

চালু) কারণ আমরা এন উপাদানগুলির জন্য স্ট্যাক স্পেস ব্যবহার করেছি। আমাদের বর্তমান উপাদানটি রাখার জন্য উপাদানগুলি সরানোর সময়। আমাদের মুছে ফেলা উপাদানগুলি সংরক্ষণ করতে হয়েছিল, যা আমাদের একটি রৈখিক স্থান জটিলতা দেয়।