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


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

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

“పునరావృత ఉపయోగించి స్టాక్‌ను క్రమబద్ధీకరించు” సమస్య మీకు ఇవ్వబడింది స్టాక్ డేటా నిర్మాణం. క్రమీకరించు పునరావృత ఉపయోగించి దాని అంశాలు. స్టాక్ యొక్క దిగువ-జాబితా చేయబడిన ఫంక్షన్లను మాత్రమే ఉపయోగించవచ్చు -

  • పుష్ (మూలకం) - స్టాక్‌లో మూలకాన్ని చొప్పించడానికి.
  • పాప్ () - పాప్ () - ఇచ్చిన స్టాక్ పైభాగంలో ఉన్న మూలకాన్ని తొలగించడానికి / తొలగించడానికి.
  • 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. ఒక తాత్కాలిక వేరియబుల్ సృష్టించండి మరియు దానిలో స్టాక్ పైభాగాన్ని నిల్వ చేయండి. స్టాక్ ఎగువన మూలకాన్ని పాప్ చేయండి మరియు ఫంక్షన్‌కు పునరావృత కాల్ చేయండి. తాత్కాలిక వేరియబుల్‌ను స్టాక్‌లో నెట్టండి.
  4. అదేవిధంగా, స్టాక్‌ను పరామితిగా అంగీకరించే ఫంక్షన్ సార్ట్ () ను సృష్టించండి. స్టాక్ ఖాళీగా ఉందో లేదో తనిఖీ చేయండి, వేరియబుల్ x ను సృష్టించండి మరియు స్టాక్ పైభాగాన్ని అందులో నిల్వ చేయండి. స్టాక్ ఎగువన మూలకాన్ని పాప్ చేయండి. ఫంక్షన్‌కు పునరావృత కాల్ చేయండి. మూలకాలను స్టాక్‌లో క్రమబద్ధీకరించిన క్రమంలో చొప్పించడానికి ఫంక్షన్‌కు కాల్ చేయండి.
  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

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

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

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

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

పై) ఎందుకంటే మేము n మూలకాల కోసం స్టాక్ స్థలాన్ని ఉపయోగించాము. మా ప్రస్తుత మూలకాన్ని ఉంచడానికి మూలకాలను తీసివేస్తున్నప్పుడు. మేము తొలగించిన మూలకాలను నిల్వ చేయాల్సి వచ్చింది, ఇది మాకు సరళ స్థల సంక్లిష్టతను ఇస్తుంది.