तात्पुरता स्टॅक वापरुन स्टॅकची क्रमवारी लावा


अडचण पातळी मध्यम
वारंवार विचारले ऍमेझॉन गोल्डमन Sachs IBM कुलिझा याहू
वर्गीकरण स्टॅक

समस्या विधान

“तात्पुरती स्टॅक वापरुन स्टॅकची क्रमवारी लावा” ही समस्या सांगते की आपल्याला ए स्टॅक डेटा रचना तात्पुरते स्टॅक वापरुन दिलेल्या स्टॅकच्या घटकांची क्रमवारी लावा.

तात्पुरता स्टॅक वापरुन स्टॅकची क्रमवारी लावा

उदाहरण

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. यानंतर एखादा फंक्शन सॉर्ट () तयार करा जो स्टॅकला पॅरामीटर म्हणून स्वीकारतो. त्यात आणखी एक तात्पुरते / सहाय्यक स्टॅक tmpStack प्रारंभ करा.
  3. मूळ स्टॅक रिक्त नसताना ट्रॅव्हर्स करा, एक व्हेरिएबल tmp तयार करा आणि त्यामध्ये मूळ स्टॅकचा वरचा भाग ठेवा. यानंतर मूळ स्टॅकच्या शीर्षस्थानी पॉप करा.
  4. पुन्हा ट्रॅव्हर्स करताना tmpStack रिकामे नाही आणि tmpStack चा वरचा भाग म्हणजे तात्पुरता स्टॅक व्हेरिएबल tmp च्या तुलनेत कमी किंवा त्यापेक्षा कमी नसावा, मूळ स्टॅकमध्ये तात्पुरते स्टॅकच्या वरच्या बाजूस दाबा आणि तात्पुरते स्टॅकच्या शीर्षस्थानी पॉप करा.
  5. तात्पुरत्या स्टॅकमध्ये व्हेरिएबल टीएमपी पुश करा.
  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 आहे जर घटक तात्पुरते स्टॅकपासून वरच्या भागाला जोरदार धक्का लावण्यापेक्षा तात्पुरते स्टॅकपासून मूळ स्टॅककडे आणत असतात. चांगल्या प्रकारे समजण्यासाठी, उतरत्या क्रमा क्रमांकावर विचार करा आणि अल्गोरिदम चालवण्याचा प्रयत्न करा.

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

O (n) कारण आम्ही n घटकांसाठी तात्पुरते स्टॅक स्पेस वापरली आहे. मूळ स्टॅकद्वारे वापरलेली जागा अल्गोरिदमसाठी मोजली जात नाही.