Ταξινόμηση μιας στοίβας χρησιμοποιώντας μια προσωρινή στοίβα


Επίπεδο δυσκολίας Μέσον
Συχνές ερωτήσεις αμαζόνα Goldman Sachs IBM Κουλίζα Yahoo
Ταξινόμηση Στοίβα

Δήλωση προβλήματος

Το πρόβλημα "Ταξινόμηση μιας στοίβας χρησιμοποιώντας μια προσωρινή στοίβα" δηλώνει ότι σας έχει δοθεί ένα σωρός δομή δεδομένων. Ταξινόμηση των στοιχείων της δεδομένης στοίβας χρησιμοποιώντας μια προσωρινή στοίβα.

Ταξινόμηση μιας στοίβας χρησιμοποιώντας μια προσωρινή στοίβα

Παράδειγμα

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. Ενώ η προσωρινή στοίβα δεν είναι κενή, εκτυπώστε την κορυφή και ανοίξτε την κορυφή.

Κώδικας

Πρόγραμμα C ++ για ταξινόμηση μιας στοίβας χρησιμοποιώντας αναδρομή

#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

Πρόγραμμα Java για ταξινόμηση μιας στοίβας χρησιμοποιώντας αναδρομή

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. Ο χώρος που χρησιμοποιείται από την αρχική στοίβα δεν μετράται για τον αλγόριθμο.