ആവർത്തനം ഉപയോഗിച്ച് ഒരു സ്റ്റാക്ക് അടുക്കുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ ഗോൾഡ്മാൻ സാക്സ് ഐബിഎം കുലിസ യാഹൂ
റിക്കറിഷൻ കൂനകൂട്ടുക

പ്രശ്നം പ്രസ്താവന

“ആവർത്തനം ഉപയോഗിച്ച് ഒരു സ്റ്റാക്ക് അടുക്കുക” എന്ന പ്രശ്നം നിങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു സ്റ്റാക്ക് ഡാറ്റ ഘടന. അടുക്കുക ആവർത്തന ഉപയോഗിച്ച് അതിന്റെ ഘടകങ്ങൾ. സ്റ്റാക്കിന്റെ ചുവടെ ലിസ്റ്റുചെയ്ത ഫംഗ്ഷനുകൾ മാത്രമേ ഉപയോഗിക്കാൻ കഴിയൂ -

  • പുഷ് (ഘടകം) - സ്റ്റാക്കിൽ ഘടകം ചേർക്കുന്നതിന്.
  • pop () - pop () - തന്നിരിക്കുന്ന സ്റ്റാക്കിന്റെ മുകളിലുള്ള ഘടകം നീക്കംചെയ്യാൻ / ഇല്ലാതാക്കാൻ.
  • isEmpty () - സ്റ്റാക്കിൽ എന്തെങ്കിലും ഘടകമുണ്ടോ ഇല്ലയോ എന്ന് പരിശോധിക്കാൻ.
  • മുകളിൽ () - തന്നിരിക്കുന്ന സ്റ്റാക്കിന്റെ മുകളിലുള്ള ഘടകം നോക്കുക / കാണുക.

ആവർത്തനം ഉപയോഗിച്ച് ഒരു സ്റ്റാക്ക് അടുക്കുക

ഉദാഹരണം

9 4 2 -1 6 20
20 9 6 4 2 -1

വിശദീകരണം: സ്റ്റാക്ക് ആരോഹണ ക്രമത്തിൽ അടുക്കിയിരിക്കുന്നതിനാൽ. പരമാവധി ഘടകം മുകളിൽ വരുന്നു. സ്റ്റാക്ക് LIFO ഡാറ്റാ ഘടനയായതിനാൽ, output ട്ട്‌പുട്ട് അവരോഹണ ക്രമത്തിലാണെന്ന് തോന്നുന്നു.

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 എന്നത് സ്റ്റാക്കിലെ ഘടകങ്ങളുടെ എണ്ണം. കാരണം ഞങ്ങൾ സ്റ്റാക്കിലെ എലമെൻറ് പുഷ് ചെയ്യുമ്പോൾ, സ്റ്റാക്കിൽ നിലവിലുള്ള എല്ലാ ഘടകങ്ങളും നീക്കംചെയ്ത് അത് തിരുകിയേക്കാം. ഇൻപുട്ട് ക്രമത്തിൽ കുറയുകയാണെങ്കിൽ ഈ കേസ് സംഭവിക്കുന്നു.

ബഹിരാകാശ സങ്കീർണ്ണത

O (N) കാരണം n ഘടകങ്ങൾക്കായി ഞങ്ങൾ സ്റ്റാക്ക് സ്പേസ് ഉപയോഗിച്ചു. ഞങ്ങളുടെ നിലവിലെ ഘടകം സ്ഥാപിക്കുന്നതിന് ഘടകങ്ങൾ നീക്കംചെയ്യുമ്പോൾ. നീക്കംചെയ്ത ഘടകങ്ങൾ ഞങ്ങൾ സംഭരിക്കേണ്ടതുണ്ട്, അത് ഞങ്ങൾക്ക് ഒരു രേഖീയ സ്ഥല സങ്കീർണ്ണത നൽകുന്നു.