ഒരു താൽക്കാലിക സ്റ്റാക്ക് ഉപയോഗിച്ച് ഒരു സ്റ്റാക്ക് അടുക്കുക


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

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

“ഒരു താൽക്കാലിക സ്റ്റാക്ക് ഉപയോഗിച്ച് ഒരു സ്റ്റാക്ക് അടുക്കുക” എന്ന പ്രശ്നം നിങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ടെന്ന് പറയുന്നു സ്റ്റാക്ക് ഡാറ്റ ഘടന. തന്നിരിക്കുന്ന സ്റ്റാക്കിന്റെ ഘടകങ്ങൾ ഒരു താൽക്കാലിക സ്റ്റാക്ക് ഉപയോഗിച്ച് അടുക്കുക.

ഒരു താൽക്കാലിക സ്റ്റാക്ക് ഉപയോഗിച്ച് ഒരു സ്റ്റാക്ക് അടുക്കുക

ഉദാഹരണം

9 4 2 -1 6 20
20 9 6 4 2 -1
2 1 4 3 6 5
6 5 4 3 2 1

ഉദാഹരണത്തിന്

സ്റ്റാക്ക് = [9 4 2 -1 6 20], താൽക്കാലിക സ്റ്റാക്ക് = []

Steps for sorting -
1.Top of stack = 20
Stack = [9 4 2 -1 6]
Temporary stack = [20]

2. Top of stack = 6
Stack = [9 4 2 -1 20]
Temporary stack = [6]

3. Top of stack = 20
Stack = [9 4 2 -1]
Temporary stack = [6 20]

4. Top of stack = -1
Stack = [9 4 2 20 6]
Temporary stack = [-1]

5. Top of stack = 6
Stack = [9 4 2 20]
Temporary stack = [-1 6]

6. Top of stack = 20
Stack = [9 4 2]
Temporary stack = [-1 6 20]

7. Top of stack = 2
Stack = [9 4 20 6]
Temporary stack = [-1 2]

8. Top of stack = 6
Stack = [9 4 20]
Temporary stack = [-1 2 6]

9. Top of stack = 20
Stack = [9 4]
Temporary stack = [-1 2 6 20]

10. Top of stack = 4
Stack = [9 20 6]
Temporary stack = [-1 2 4]

11. Top of stack = 6
Stack = [9 20]
Temporary stack = [-1 2 4 6]

12. Top of stack = 20
Stack = [9]
Temporary stack = [-1 2 4 6 20]

13. Top of stack = 9
Stack = [20]
Temporary stack = [-1 2 4 6 9]

14. Top of stack = 20
Stack = []
Temporary stack = [-1 2 4 6 9 20]

സ്റ്റാക്ക് ശൂന്യവും താൽ‌ക്കാലിക സ്റ്റാക്ക് അടുക്കിയിരിക്കുന്നതുമായതിനാൽ‌, അതിന്റെ മുകളിൽ‌ നിന്നും ആരംഭിക്കുന്ന താൽ‌ക്കാലിക സ്റ്റാക്ക് പ്രിന്റുചെയ്യുക.

അതിനാൽ, put ട്ട്പുട്ട്: 20 9 6 4 2 -1

ഒരു താൽ‌ക്കാലിക സ്റ്റാക്ക് ഉപയോഗിച്ച് ഒരു സ്റ്റാക്ക് അടുക്കുന്നതിനുള്ള അൽ‌ഗോരിതം

  1. ഒരു സ്റ്റാക്ക് ഡാറ്റ ഘടന സമാരംഭിച്ച് അതിൽ ഘടകങ്ങൾ ചേർക്കുക / പുഷ് ചെയ്യുക.
  2. അതിനുശേഷം ഒരു ഫംഗ്ഷൻ സോർട്ട് () സൃഷ്ടിക്കുക, അത് ഒരു സ്റ്റാക്ക് പാരാമീറ്ററായി സ്വീകരിക്കുന്നു. അതിൽ മറ്റൊരു താൽക്കാലിക / സഹായ സ്റ്റാക്ക് tmpStack സമാരംഭിക്കുക.
  3. യഥാർത്ഥ സ്റ്റാക്ക് ശൂന്യമല്ലാത്തപ്പോൾ സഞ്ചരിക്കുക, ഒരു വേരിയബിൾ ടി‌എം‌പി സൃഷ്‌ടിച്ച് അതിൽ യഥാർത്ഥ സ്റ്റാക്കിന്റെ മുകളിൽ സംഭരിക്കുക. അതിനുശേഷം യഥാർത്ഥ സ്റ്റാക്കിന്റെ മുകളിൽ പോപ്പ് ചെയ്യുക.
  4. പിന്നെയും ട്ര്യാവര്സ് ത്ംപ്സ്തച്ക് ശൂന്യമായിടാനായില്ല ആണ് ത്ംപ്സ്തച്ക് മുകളിൽ താൽക്കാലിക സ്റ്റാക്ക് അതായത് കുറവ് വലിയവൻ അല്ല അല്ലെങ്കിൽ വേരിയബിൾ tmp തുല്യമോ യഥാർത്ഥ സ്റ്റാക്ക് താൽക്കാലിക സ്റ്റാക്ക് മുകളിൽ മതിൽക്കെട്ടുകൾ താൽക്കാലിക സ്റ്റാക്ക് മുകളിൽ പോപ്പ്. അതേസമയം
  5. താൽ‌ക്കാലിക സ്റ്റാക്കിൽ‌ വേരിയബിൾ‌ ടി‌എം‌പി പുഷ് ചെയ്യുക.
  6. താൽ‌ക്കാലിക സ്റ്റാക്ക് ശൂന്യമല്ലെങ്കിലും, മുകളിൽ‌ അച്ചടിച്ച് ടോപ്പ് ടോപ്പ് ചെയ്യുക.

കോഡ്

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

#include <iostream> 
#include <stack>
using namespace std; 
  
stack<int> sort(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; 
} 
  
int main(){ 
    stack<int> input; 
    
    input.push(20); 
    input.push(6); 
    input.push(-1); 
    input.push(2); 
    input.push(4); 
    input.push(9); 
  
    stack<int> tmpStack = sort(input); 
    
    while (!tmpStack.empty()){ 
        cout << tmpStack.top()<< " "; 
        tmpStack.pop(); 
    } 
}
20 9 6 4 2 -1

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

import java.util.*; 
  
class SortStack{ 
    
    public static Stack<Integer> sort(Stack<Integer> input){
        
        Stack<Integer> tmpStack = new Stack<Integer>(); 
        
        while(!input.isEmpty()){ 
            int tmp = input.pop(); 
          
            while(!tmpStack.isEmpty() && tmpStack.peek() > tmp){ 
                input.push(tmpStack.pop()); 
            } 
              
            tmpStack.push(tmp); 
        } 
        return tmpStack; 
    } 
      
    public static void main(String args[]){
        
        Stack<Integer> input = new Stack<Integer>(); 
        
        input.add(20); 
        input.add(6); 
        input.add(-1); 
        input.add(2); 
        input.add(4); 
        input.add(9); 
      
        Stack<Integer> tmpStack=sort(input); 
        
        while (!tmpStack.empty()){ 
            System.out.print(tmpStack.pop()+" "); 
        }  
    } 
}
20 9 6 4 2 -1

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n ^ 2) ഇവിടെ n എന്നത് സ്റ്റാക്കിലെ ഘടകങ്ങളുടെ എണ്ണം. താൽക്കാലിക സ്റ്റാക്കിന്റെ മുകൾഭാഗം തള്ളേണ്ട ഘടകത്തേക്കാൾ കുറവാണെങ്കിൽ ഞങ്ങൾ താൽക്കാലിക സ്റ്റാക്കിൽ നിന്ന് യഥാർത്ഥ സ്റ്റാക്കിലേക്ക് മൂലകങ്ങളെ പിന്നോട്ട് തള്ളുന്നു. മികച്ച ഗ്രാഹ്യത്തിനായി, ഒരു അവരോഹണ ക്രമം പരിഗണിച്ച് അൽഗോരിതം പ്രവർത്തിപ്പിക്കാൻ ശ്രമിക്കുക.

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

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