অস্থায়ী স্ট্যাক ব্যবহার করে একটি স্ট্যাক সাজান


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

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

"অস্থায়ী স্ট্যাক ব্যবহার করে একটি স্ট্যাক সাজান" সমস্যাটি আপনাকে উল্লেখ করে যে একটি গাদা তথ্য কাঠামো. অস্থায়ী স্ট্যাক ব্যবহার করে প্রদত্ত স্ট্যাকের উপাদানগুলি সাজান।

অস্থায়ী স্ট্যাক ব্যবহার করে একটি স্ট্যাক সাজান

উদাহরণ

9 4 2 -1 6 20
20 9 6 4 2 -1
2 1 4 3 6 5
6 5 4 3 2 1

এই ক্ষেত্রে

স্ট্যাক = [9 4 2 -1 6 20] এবং অস্থায়ী স্ট্যাক = []

Steps for sorting -
1.Top of stack = 20
Stack = [9 4 2 -1 6]
Temporary stack = [20]

2. Top of stack = 6
Stack = [9 4 2 -1 20]
Temporary stack = [6]

3. Top of stack = 20
Stack = [9 4 2 -1]
Temporary stack = [6 20]

4. Top of stack = -1
Stack = [9 4 2 20 6]
Temporary stack = [-1]

5. Top of stack = 6
Stack = [9 4 2 20]
Temporary stack = [-1 6]

6. Top of stack = 20
Stack = [9 4 2]
Temporary stack = [-1 6 20]

7. Top of stack = 2
Stack = [9 4 20 6]
Temporary stack = [-1 2]

8. Top of stack = 6
Stack = [9 4 20]
Temporary stack = [-1 2 6]

9. Top of stack = 20
Stack = [9 4]
Temporary stack = [-1 2 6 20]

10. Top of stack = 4
Stack = [9 20 6]
Temporary stack = [-1 2 4]

11. Top of stack = 6
Stack = [9 20]
Temporary stack = [-1 2 4 6]

12. Top of stack = 20
Stack = [9]
Temporary stack = [-1 2 4 6 20]

13. Top of stack = 9
Stack = [20]
Temporary stack = [-1 2 4 6 9]

14. Top of stack = 20
Stack = []
Temporary stack = [-1 2 4 6 9 20]

স্ট্যাকটি খালি থাকায় এবং অস্থায়ী স্ট্যাকটি সাজানো থাকায় অস্থায়ী স্ট্যাকটি শীর্ষ থেকে শুরু করে মুদ্রণ করুন।

অতএব, আউটপুট: 20 9 6 4 2 -1

অস্থায়ী স্ট্যাক ব্যবহার করে একটি স্ট্যাক বাছাইয়ের জন্য অ্যালগরিদম

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

কোড

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

#include <iostream> 
#include <stack>
using namespace std; 
  
stack<int> sort(stack<int> &input){ 
    stack<int> tmpStack; 
  
    while(!input.empty()){ 
        
        int tmp = input.top(); 
        input.pop(); 
  
        while(!tmpStack.empty() && tmpStack.top() > tmp){ 
            input.push(tmpStack.top()); 
            tmpStack.pop(); 
        } 
  
        tmpStack.push(tmp); 
    } 
  
    return tmpStack; 
} 
  
int main(){ 
    stack<int> input; 
    
    input.push(20); 
    input.push(6); 
    input.push(-1); 
    input.push(2); 
    input.push(4); 
    input.push(9); 
  
    stack<int> tmpStack = sort(input); 
    
    while (!tmpStack.empty()){ 
        cout << tmpStack.top()<< " "; 
        tmpStack.pop(); 
    } 
}
20 9 6 4 2 -1

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

import java.util.*; 
  
class SortStack{ 
    
    public static Stack<Integer> sort(Stack<Integer> input){
        
        Stack<Integer> tmpStack = new Stack<Integer>(); 
        
        while(!input.isEmpty()){ 
            int tmp = input.pop(); 
          
            while(!tmpStack.isEmpty() && tmpStack.peek() > tmp){ 
                input.push(tmpStack.pop()); 
            } 
              
            tmpStack.push(tmp); 
        } 
        return tmpStack; 
    } 
      
    public static void main(String args[]){
        
        Stack<Integer> input = new Stack<Integer>(); 
        
        input.add(20); 
        input.add(6); 
        input.add(-1); 
        input.add(2); 
        input.add(4); 
        input.add(9); 
      
        Stack<Integer> tmpStack=sort(input); 
        
        while (!tmpStack.empty()){ 
            System.out.print(tmpStack.pop()+" "); 
        }  
    } 
}
20 9 6 4 2 -1

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

সময় জটিলতা

ও (এন ^ 2) যেখানে n হল স্ট্যাকের উপাদানগুলির সংখ্যা। যেহেতু আমরা অস্থায়ী স্ট্যাক থেকে মূল স্ট্যাকের দিকে উপাদানগুলিকে পিছনে ঠেলে দিচ্ছি যদি অস্থায়ী স্ট্যাকের শীর্ষটি ধাক্কা দেওয়ার মতো উপাদানটির চেয়ে কম হয়। আরও ভাল বোঝার জন্য, একটি উতরিত অর্ডার ক্রম বিবেচনা করুন এবং অ্যালগরিদম চালানোর চেষ্টা করুন।

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

উপর) কারণ আমরা এন উপাদানগুলির জন্য অস্থায়ী স্ট্যাক স্পেস ব্যবহার করেছি। মূল স্ট্যাক দ্বারা ব্যবহৃত স্থানটি অ্যালগরিদমের জন্য গণনা করা হয় না।