സ്റ്റാക്കുകൾ ഉപയോഗിച്ച് അറേ അടുക്കുന്നു


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

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

“സ്റ്റാക്കുകൾ ഉപയോഗിച്ച് അറേ അടുക്കുന്നു” എന്ന പ്രശ്നം നിങ്ങൾക്ക് ഒരു ഡാറ്റ ഘടന നൽകുന്നുവെന്ന് പറയുന്നു ശ്രേണി 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. ഒരു സ്റ്റാക്ക് ഡാറ്റ ഘടന സൃഷ്ടിക്കുക. അറേ a [] ലൂടെ സഞ്ചരിച്ച് അറേയുടെ എല്ലാ ഘടകങ്ങളും a [] സ്റ്റാക്കിലേക്ക് നീക്കുക.
  3. അതുപോലെ, മറ്റൊരു താൽക്കാലിക സ്റ്റാക്ക് സൃഷ്ടിക്കുക.
  4. യഥാർത്ഥ സ്റ്റാക്കിന്റെ വലുപ്പം 0 അല്ലാത്തപ്പോൾ സഞ്ചരിക്കുക. ഒരു വേരിയബിൾ ടി‌എം‌പി സൃഷ്‌ടിച്ച് മൂലകം ഒറിജിനൽ സ്റ്റാക്കിന്റെ മുകളിൽ സംഭരിച്ച് യഥാർത്ഥ സ്റ്റാക്കിൽ നിന്ന് പോപ്പ് ചെയ്യുക.
  5. താൽ‌ക്കാലിക സ്റ്റാക്ക് ശൂന്യമല്ലാത്തപ്പോൾ‌ വീണ്ടും സഞ്ചരിച്ച് താൽ‌ക്കാലിക സ്റ്റാക്കിന്റെ മുകളിൽ‌ ഘടകം വേരിയബിൾ‌ ടി‌എം‌പിയേക്കാൾ‌ കുറയുന്നതുവരെ പോപ്പ് ചെയ്യുക. താൽക്കാലിക സ്റ്റാക്കിൽ നിന്ന് പോപ്പ് ചെയ്യുമ്പോൾ, യഥാർത്ഥ സ്റ്റാക്കിലെ താൽക്കാലിക സ്റ്റാക്കിന്റെ മുകളിലെ ഘടകം പുഷ് ചെയ്യുക.
  6. വേരിയബിൾ ടി‌എം‌പി ഒരു താൽ‌ക്കാലിക സ്റ്റാക്കിൽ‌ പുഷ് ചെയ്യുക.
  7. 0 മുതൽ n-1 വരെ സഞ്ചരിച്ച് താൽ‌ക്കാലിക സ്റ്റാക്കിന്റെ മുകളിലെ ഘടകം നിലവിലെ സൂചികയിൽ ഒരു [] അറേയിൽ സംഭരിക്കുകയും താൽ‌ക്കാലിക സ്റ്റാക്കിൽ‌ നിന്നും ഘടകം പോപ്പ് / ഇല്ലാതാക്കുകയും ചെയ്യുക.
  8. അവസാനമായി, 0 മുതൽ n-1 വരെ സഞ്ചരിച്ച് അറേ a [] പ്രിന്റുചെയ്യുക.

കോഡ്

സ്റ്റാക്കുകൾ ഉപയോഗിച്ച് അറേ അടുക്കുന്നതിനുള്ള സി ++ പ്രോഗ്രാം

#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 എന്നത് സ്റ്റാക്കിലെ ഘടകങ്ങളുടെ എണ്ണം. താൽക്കാലിക സ്റ്റാക്കിന്റെ മുകൾഭാഗം തള്ളേണ്ട ഘടകത്തേക്കാൾ കുറവാണെങ്കിൽ ഞങ്ങൾ താൽക്കാലിക സ്റ്റാക്കിൽ നിന്ന് യഥാർത്ഥ സ്റ്റാക്കിലേക്ക് മൂലകങ്ങളെ പിന്നോട്ട് തള്ളുന്നു. മികച്ച ഗ്രാഹ്യത്തിനായി, ഒരു അവരോഹണ ക്രമം പരിഗണിച്ച് അൽഗോരിതം പ്രവർത്തിപ്പിക്കാൻ ശ്രമിക്കുക.

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

O (n) കാരണം n ഘടകങ്ങൾക്കായി ഞങ്ങൾ താൽക്കാലിക സ്റ്റാക്ക് സ്പേസ് ഉപയോഗിച്ചു. യഥാർത്ഥ സ്റ്റാക്ക് ഉപയോഗിക്കുന്ന ഇടം അൽ‌ഗോരിതം കണക്കാക്കില്ല.