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


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది అమెజాన్ గోల్డ్మన్ సాచ్స్ IBM కులిజా యాహూ
సార్టింగ్ స్టాక్

సమస్యల నివేదిక

“స్టాక్‌లను ఉపయోగించి శ్రేణిని క్రమబద్ధీకరించడం” సమస్య మీకు డేటా నిర్మాణాన్ని ఇచ్చిందని పేర్కొంది అమరిక a [] పరిమాణం n. క్రమీకరించు ఉపయోగించి ఇచ్చిన శ్రేణి యొక్క అంశాలు స్టాక్ డేటా నిర్మాణం.

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

ఉదాహరణ

2 30 -5 43 100
-5 2 30 43 100

వివరణ: మూలకాలు ఆరోహణ క్రమంలో క్రమబద్ధీకరించబడతాయి.

2 3 1 8 6
1 2 3 6 8

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

ఇచ్చిన ఇన్పుట్ శ్రేణి యొక్క అన్ని అంశాలను నిల్వ చేయడానికి స్టాక్ డేటా నిర్మాణాన్ని సృష్టించండి []. ఆ తరువాత, అసలుదాన్ని క్రమబద్ధీకరించడానికి మరొక తాత్కాలిక స్టాక్‌ను సృష్టించండి. అసలు స్టాక్ ద్వారా మళ్ళించండి మరియు ప్రతి మూలకం పైభాగాన్ని పాప్ చేసి తాత్కాలిక వేరియబుల్‌లో నిల్వ చేయండి. అదేవిధంగా, తాత్కాలిక స్టాక్ ద్వారా మళ్ళించండి, అయితే తాత్కాలిక స్టాక్ పైభాగంలో ఉన్న మూలకం అసలు స్టాక్ యొక్క పాప్డ్ టాప్ కంటే తక్కువగా ఉంటుంది. అసలు స్టాక్‌లో తాత్కాలిక స్టాక్ యొక్క పై మూలకాన్ని చొప్పించి, తాత్కాలిక స్టాక్ నుండి తీసివేయండి. తాత్కాలిక స్టాక్‌లో అసలు స్టాక్ యొక్క పాప్డ్ టాప్‌ను నొక్కండి. చివరికి, తాత్కాలిక స్టాక్ క్రమబద్ధీకరించిన క్రమంలో అంశాలను కలిగి ఉంటుంది. ఈ సమస్య క్రమబద్ధీకరణపై స్వల్ప మార్పు తాత్కాలిక స్టాక్ ఉపయోగించి స్టాక్.

అల్గారిథం

  1. పరిమాణం n యొక్క [] శ్రేణిని ప్రారంభించండి.
  2. స్టాక్ డేటా నిర్మాణాన్ని సృష్టించండి. శ్రేణి ద్వారా ప్రయాణించండి [] మరియు శ్రేణిలోని అన్ని అంశాలను స్టాక్‌లో [[] నెట్టండి.
  3. అదేవిధంగా, మరొక తాత్కాలిక స్టాక్‌ను సృష్టించండి.
  4. అసలు స్టాక్ యొక్క పరిమాణం 0 కానప్పుడు ప్రయాణించండి. వేరియబుల్ టిఎమ్‌పిని సృష్టించి, మూలకాన్ని దానిలోని అసలు స్టాక్ పైభాగంలో నిల్వ చేసి, అసలు స్టాక్ నుండి పాప్ చేయండి.
  5. తాత్కాలిక స్టాక్ ఖాళీగా లేనప్పుడు మళ్ళీ ప్రయాణించి, వేరియబుల్ టిఎంపీ కంటే తక్కువగా ఉండే వరకు తాత్కాలిక స్టాక్ పైభాగంలో ఉన్న మూలకాన్ని పాప్ చేయండి. తాత్కాలిక స్టాక్ నుండి పాపింగ్ చేస్తున్నప్పుడు, అసలు స్టాక్‌లోని తాత్కాలిక స్టాక్ యొక్క పై మూలకాన్ని నెట్టండి.
  6. వేరియబుల్ tmp ని తాత్కాలిక స్టాక్‌లో నెట్టండి.
  7. 0 నుండి n-1 వరకు ప్రయాణించి, తాత్కాలిక స్టాక్ యొక్క ఎగువ మూలకాన్ని ప్రస్తుత సూచిక వద్ద శ్రేణి [] లో నిల్వ చేయండి మరియు తాత్కాలిక స్టాక్ నుండి మూలకాన్ని పాప్ / తొలగించండి.
  8. చివరగా, 0 నుండి n-1 వరకు ప్రయాణించి, శ్రేణిని ముద్రించండి [].

కోడ్

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

#include <iostream>
#include <stack> 
using namespace std; 
  
stack<int> sortStack(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; 
} 
  
void sortUsingStack(int arr[], int n){ 
     
    stack<int> input; 
    for(int i=0; i<n; i++){ 
       input.push(arr[i]); 
    }
  
    stack<int> tmpStack = sortStack(input); 
  
    for(int i=0; i<n; i++){ 
        arr[i] = tmpStack.top(); 
        tmpStack.pop(); 
    } 
} 
  
int main(){ 
    int a[] = {2, 30, -5, 43, 100}; 
    int n = sizeof(a)/sizeof(a[0]); 
  
    sortUsingStack(a, n); 
  
    for(int i=0; i<n; i++) 
       cout << a[i] << " "; 
  
    return 0; 
}
-5 2 30 43 100

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

import java.io.*; 
import java.util.*; 
  
class SortArrayWithStack{ 
    
    static Stack<Integer> sortStack(Stack<Integer> input){ 
        Stack<Integer> tmpStack = new Stack<Integer>(); 
      
        while(!input.empty()){ 
            int tmp = input.peek(); 
            input.pop(); 
      
            while(!tmpStack.empty() && tmpStack.peek() < tmp){ 
                input.push(tmpStack.peek()); 
                tmpStack.pop(); 
            } 
      
            tmpStack.push(tmp); 
        } 
        return tmpStack; 
    } 
      
    static void sortUsingStack(int []arr, int n){ 
        
        Stack<Integer> input = new Stack<Integer>(); 
        
        for(int i = 0; i < n; i++){ 
            input.push(arr[i]); 
        }
      
        Stack<Integer> tmpStack = sortStack(input); 
      
        for(int i = 0; i < n; i++){ 
            arr[i] = tmpStack.peek(); 
            tmpStack.pop(); 
        } 
    } 
      
    public static void main(String args[]){
        
        int []a = {2, 30, -5, 43, 100};
        int n = a.length; 
      
        sortUsingStack(a, n); 
      
        for(int i = 0; i < n; i++){ 
            System.out.print(a[i] + " "); 
        }    
    } 
}
-5 2 30 43 100

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

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

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

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

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