ຮຽງລໍາດັບໂດຍໃຊ້ stack ຊົ່ວຄາວ


ລະດັບຄວາມຫຍຸ້ງຍາກ ຂະຫນາດກາງ
ຖາມເລື້ອຍໆໃນ Amazon Goldman Sachs IBM ກຸລະກິ Yahoo
ຮຽງລໍາດັບ Stack

ຖະແຫຼງການບັນຫາ

ບັນຫາ "ຈັດຮຽງໂດຍໃຊ້ stack ຊົ່ວຄາວ" ລະບຸວ່າທ່ານຖືກກ stack ໂຄງສ້າງຂໍ້ມູນ. ຈັດແຈງອົງປະກອບຂອງ stack ທີ່ໃຫ້ໂດຍໃຊ້ stack ຊົ່ວຄາວ.

ຮຽງລໍາດັບໂດຍໃຊ້ stack ຊົ່ວຄາວ

ຍົກຕົວຢ່າງ

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

ຕົວຢ່າງເຊັ່ນ

ໃຫ້ Stack = [9 4 2 -1 6 20] ແລະ stack ຊົ່ວຄາວ = []

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]

ເນື່ອງຈາກວ່າ Stack ແມ່ນຫວ່າງແລະ stack ຊົ່ວຄາວຢູ່ໃນການຈັດຮຽງ, ພິມ stack ຊົ່ວຄາວເລີ່ມຈາກມັນຢູ່ເທິງສຸດ.

ສະນັ້ນ, ຜົນໄດ້ຮັບ: 20 9 6 4 2 -1

ສູດການຄິດໄລ່ເພື່ອຈັດຮຽງ stack ໂດຍໃຊ້ stack ຊົ່ວຄາວ

  1. ເລີ່ມຕົ້ນໂຄງສ້າງຂໍ້ມູນ stack ແລະໃສ່ / ຍູ້ອົງປະກອບຕ່າງໆໃນນັ້ນ.
  2. ຫລັງຈາກນັ້ນສ້າງການຈັດລຽງການເຮັດວຽກ () ທີ່ຍອມຮັບເອົາ stack ເປັນພາລາມິເຕີຂອງມັນ. ເລີ່ມຕົ້ນ tmpStack ຊົ່ວຄາວ / ໜ່ວຍ ຊ່ວຍອື່ນໃນມັນ.
  3. Traverse ໃນຂະນະທີ່ stack ເດີມບໍ່ແມ່ນຫວ່າງ, ສ້າງ tmp ຕົວແປແລະເກັບຮັກສາຊັ້ນເທິງຂອງ stack ເດີມໃນນັ້ນ. ຫລັງຈາກນັ້ນຂື້ນເທິງສຸດຂອງ stack ເດີມ.
  4. ອີກເທື່ອ ໜຶ່ງ Traverse ໃນຂະນະທີ່ tmpStack ບໍ່ຫວ່າງແລະດ້ານເທິງຂອງ tmpStack ໝາຍ ຄວາມວ່າ stack ຊົ່ວຄາວໃຫຍ່ກວ່າບໍ່ຕໍ່າກ່ວາຫລືເທົ່າກັບຕົວແປ tmp ຕົວປ່ຽນແປງ, ຍູ້ດ້ານເທິງຂອງ stack ຊົ່ວຄາວໃນ stack ເດີມແລະກົດເທິງສຸດຂອງ stack ຊົ່ວຄາວ.
  5. ຍູ້ tmp ຕົວແປໃນ stack ຊົ່ວຄາວ.
  6. ໃນຂະນະທີ່ການຈັດວາງຊົ່ວຄາວບໍ່ແມ່ນວ່າງ, ພິມມັນຢູ່ເທິງແລະປ້ ຳ ມັນຢູ່ເທິງສຸດ.

ລະຫັດ

C ++ Program ຈັດລຽງ ລຳ ດັບໂດຍໃຊ້ການເອີ້ນຄືນ

#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 Program ຈັດລຽງ ລຳ ດັບໂດຍໃຊ້ການເອີ້ນຄືນ

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 ແມ່ນຈໍານວນຂອງອົງປະກອບໃນ stack ໄດ້. ເນື່ອງຈາກວ່າພວກເຮົາ ກຳ ລັງຍູ້ອົງປະກອບດັ່ງກ່າວກັບມາຈາກ stack ຊົ່ວຄາວໄປຫາ stack ເດີມໃນກໍລະນີສ່ວນເທິງຂອງ stack ຊົ່ວຄາວຈະນ້ອຍກວ່າອົງປະກອບທີ່ຈະຖືກຍູ້. ເພື່ອໃຫ້ມີຄວາມເຂົ້າໃຈດີຂື້ນ, ໃຫ້ພິຈາລະນາ ລຳ ດັບທີ່ ກຳ ລັງລົງແລະພະຍາຍາມ ດຳ ເນີນການຄິດໄລ່.

ຄວາມສັບສົນໃນອະວະກາດ

O (n) ເນື່ອງຈາກວ່າພວກເຮົາໃຊ້ພື້ນທີ່ stack ຊົ່ວຄາວ ສຳ ລັບອົງປະກອບ n. ພື້ນທີ່ທີ່ໃຊ້ໂດຍ stack ເດີມບໍ່ໄດ້ຖືກຄິດໄລ່ ສຳ ລັບສູດການຄິດໄລ່.