తాత్కాలిక స్టాక్ ఉపయోగించి స్టాక్‌ను క్రమబద్ధీకరించండి


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది అమెజాన్ గోల్డ్మన్ సాచ్స్ 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. అసలు స్టాక్ ఖాళీగా లేనప్పుడు ప్రయాణించండి, వేరియబుల్ టిఎమ్‌పిని సృష్టించండి మరియు అసలు స్టాక్ పైభాగాన్ని అందులో నిల్వ చేయండి. ఆ తరువాత అసలు స్టాక్ పైభాగాన్ని పాప్ చేయండి.
  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

సంక్లిష్టత విశ్లేషణ

సమయం సంక్లిష్టత

O (n ^ 2) ఇక్కడ n అనేది స్టాక్‌లోని మూలకాల సంఖ్య. తాత్కాలిక స్టాక్ యొక్క పైభాగం నెట్టవలసిన మూలకం కంటే తక్కువగా ఉంటే మేము తాత్కాలిక స్టాక్ నుండి అసలు స్టాక్‌కు మూలకాలను వెనక్కి నెట్టడం వలన. మంచి అవగాహన కోసం, అవరోహణ ఆర్డర్ క్రమాన్ని పరిగణించండి మరియు అల్గోరిథంను అమలు చేయడానికి ప్రయత్నించండి.

అంతరిక్ష సంక్లిష్టత

పై) ఎందుకంటే మేము n మూలకాల కోసం తాత్కాలిక స్టాక్ స్థలాన్ని ఉపయోగించాము. అసలు స్టాక్ ఉపయోగించే స్థలం అల్గోరిథం కోసం లెక్కించబడదు.