અસ્થાયી સ્ટેકનો ઉપયોગ કરીને સ્ટેકને સortર્ટ કરો


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એમેઝોન ગોલ્ડમૅન સૅશ IBM કુલીઝા યાહૂ
સોર્ટિંગ સ્ટેક

સમસ્યા નિવેદન

સમસ્યા "હંગામી સ્ટેકની મદદથી સ્ટેકને સortર્ટ કરો" કહે છે કે તમને એ સ્ટેક ડેટા સ્ટ્રક્ચર. અસ્થાયી સ્ટેકનો ઉપયોગ કરીને આપેલા સ્ટેકના તત્વોને સortર્ટ કરો.

અસ્થાયી સ્ટેકનો ઉપયોગ કરીને સ્ટેકને સortર્ટ કરો

ઉદાહરણ

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]

સ્ટેક ખાલી હોવાને કારણે અને અસ્થાયી સ્ટેક સortedર્ટ કરવામાં આવે છે, તે ટોચથી શરૂ થતાં અસ્થાયી સ્ટેકને છાપો.

તેથી, આઉટપુટ: 20 9 6 4 2 -1

અસ્થાયી સ્ટેકનો ઉપયોગ કરીને સ્ટેકને સortર્ટ કરવા માટે અલ્ગોરિધમ

  1. સ્ટેક ડેટા સ્ટ્રક્ચરનો પ્રારંભ કરો અને તેમાં તત્વો શામેલ કરો / દબાણ કરો.
  2. તે પછી ફંકશન સ sortર્ટ બનાવો () જે સ્ટેકને પેરામીટર હોવાથી સ્વીકારે છે. તેમાં અન્ય અસ્થાયી / સહાયક સ્ટેક tmpStack પ્રારંભ કરો.
  3. અસલ સ્ટેક ખાલી ન હોય ત્યારે આડઅસર કરો, એક ચલ tmp બનાવો અને તેમાં મૂળ સ્ટેકની ટોચ સ્ટોર કરો. તે પછી મૂળ સ્ટેકની ટોચ પ popપ કરો.
  4. ફરીથી ટ્રverseવર્સ જ્યારે tmpStack ખાલી નથી અને tmpStack ની ટોચનો એટલે કે અસ્થાયી સ્ટેક ચલ tmp કરતા ઓછું અથવા તેના કરતા બરાબર નથી, મૂળ સ્ટેકમાં અસ્થાયી સ્ટેકની ટોચને દબાણ કરો અને અસ્થાયી સ્ટેકની ટોચને પ popપ કરો.
  5. અસ્થાયી સ્ટackકમાં ચલ tmp ને દબાણ કરો.
  6. જ્યારે અસ્થાયી સ્ટેક ખાલી નથી, તે ટોચ પર છાપો અને ટોચ પર પ popપ કરો.

કોડ

રિકર્ઝનનો ઉપયોગ કરીને સ્ટેકને સ sortર્ટ કરવા માટે સી ++ પ્રોગ્રામ

#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

રિકર્ઝનનો ઉપયોગ કરીને સ્ટેકને સ sortર્ટ કરવા માટે જાવા પ્રોગ્રામ

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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (n ^ 2) જ્યાં n એ સ્ટેકમાં તત્વોની સંખ્યા છે. અસ્થાયી સ્ટેકથી જ્યારે મૂળ તત્વોને દબાણમાં લાવવામાં આવે છે તેના કરતા ઓછી હોય તો આપણે અસ્થાયી સ્ટેકથી મૂળ સ્ટેક તરફ દબાણ કરી રહ્યા છીએ. સારી સમજણ માટે, ઉતરતા ક્રમમાં ક્રમ ધ્યાનમાં લો અને અલ્ગોરિધમનો ચલાવવાનો પ્રયાસ કરો.

અવકાશ જટિલતા

ઓ (એન) કારણ કે અમે n તત્વો માટે કામચલાઉ સ્ટેક સ્પેસનો ઉપયોગ કર્યો છે. મૂળ સ્ટેક દ્વારા ઉપયોગમાં લેવાતી જગ્યા અલ્ગોરિધમ માટે ગણતરીમાં નથી.