மறுநிகழ்வைப் பயன்படுத்தி ஒரு அடுக்கை வரிசைப்படுத்தவும்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் கோல்ட்மேன் சாக்ஸ் ஐபிஎம் குலிசா யாகூ
மறுசுழற்சி ஸ்டேக்

சிக்கல் அறிக்கை

“மறுநிகழ்வைப் பயன்படுத்தி ஒரு அடுக்கை வரிசைப்படுத்து” என்ற சிக்கல் உங்களுக்கு வழங்கப்படுகிறது என்று கூறுகிறது ஸ்டாக் தரவு அமைப்பு. வரிசைப்படுத்த மறுநிகழ்வைப் பயன்படுத்தி அதன் கூறுகள். அடுக்கின் கீழே பட்டியலிடப்பட்ட செயல்பாடுகளை மட்டுமே பயன்படுத்த முடியும் -

  • மிகுதி (உறுப்பு) - அடுக்கில் உறுப்பைச் செருக.
  • பாப் () - பாப் () - கொடுக்கப்பட்ட அடுக்கின் மேலே உள்ள உறுப்பை நீக்க / நீக்க.
  • 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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (என் ^ 2) n என்பது அடுக்கில் உள்ள உறுப்புகளின் எண்ணிக்கை. ஏனென்றால், அடுக்கில் உள்ள உறுப்பை நாம் தள்ளும்போது, ​​தற்போது அடுக்கில் உள்ள அனைத்து உறுப்புகளையும் அகற்றிவிட்டு அதை செருகலாம். உள்ளீடு குறைந்து கொண்டே இருந்தால் இந்த வழக்கு ஏற்படுகிறது.

விண்வெளி சிக்கலானது

ஓ (என்) ஏனென்றால் n உறுப்புகளுக்கு ஸ்டேக் இடத்தைப் பயன்படுத்தினோம். எங்கள் தற்போதைய உறுப்பை வைக்க உறுப்புகளை அகற்றும் போது. அகற்றப்பட்ட கூறுகளை நாங்கள் சேமிக்க வேண்டியிருந்தது, இது எங்களுக்கு ஒரு நேரியல் இட சிக்கலைக் கொடுக்கிறது.