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


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

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

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

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

உதாரணமாக

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]

அடுக்கு காலியாக இருப்பதால், தற்காலிக அடுக்கு வரிசைப்படுத்தப்பட்டிருப்பதால், தற்காலிக அடுக்கை அதன் மேலிருந்து அச்சிடுக.

எனவே, வெளியீடு: 20 9 6 4 2 -1

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

  1. ஒரு அடுக்கு தரவு கட்டமைப்பைத் துவக்கி, அதில் உள்ள உறுப்புகளைச் செருகவும் / தள்ளவும்.
  2. அதன் பிறகு ஒரு செயல்பாட்டு வரிசையை உருவாக்கவும் () இது ஒரு அடுக்கை அளவுருவாக ஏற்றுக்கொள்கிறது. அதில் மற்றொரு தற்காலிக / துணை அடுக்கு tmpStack ஐத் தொடங்கவும்.
  3. அசல் அடுக்கு காலியாக இல்லாதபோது பயணிக்கவும், ஒரு மாறி tmp ஐ உருவாக்கி, அசல் அடுக்கின் மேற்புறத்தை அதில் சேமிக்கவும். அதன் பிறகு அசல் அடுக்கின் மேல் பாப்.
  4. TmpStack காலியாக இல்லாதபோது மீண்டும் பயணிக்கவும், tmpStack இன் மேற்பகுதி அதாவது தற்காலிக அடுக்கு மாறி tmp ஐ விட குறைவாகவோ அல்லது சமமாகவோ இல்லை, அசல் அடுக்கில் தற்காலிக அடுக்கின் மேற்புறத்தை தள்ளி தற்காலிக அடுக்கின் மேற்புறத்தை பாப் செய்யவும்.
  5. தற்காலிக அடுக்கில் மாறி tmp ஐ அழுத்தவும்.
  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 என்பது அடுக்கில் உள்ள உறுப்புகளின் எண்ணிக்கை. தற்காலிக அடுக்கின் மேற்பகுதி தள்ளப்பட வேண்டிய உறுப்பை விட குறைவாக இருந்தால், தற்காலிக அடுக்கிலிருந்து அசல் அடுக்கிற்கு உறுப்புகளை பின்னுக்குத் தள்ளுகிறோம். சிறந்த புரிதலுக்கு, ஒரு இறங்கு வரிசை வரிசையைக் கருத்தில் கொண்டு வழிமுறையை இயக்க முயற்சிக்கவும்.

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

ஓ (n) n உறுப்புகளுக்கு தற்காலிக அடுக்கு இடத்தைப் பயன்படுத்தினோம். அசல் அடுக்கினால் பயன்படுத்தப்படும் இடம் வழிமுறைக்கு கணக்கிடப்படவில்லை.