ການຈັດລຽງການຈັດລຽງໂດຍໃຊ້ Stacks


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

ບັນຫາບັນຫາ

ບັນຫາ“ ການຈັດລຽງການ ນຳ ໃຊ້ Stacks” ລະບຸວ່າທ່ານໄດ້ຮັບໂຄງສ້າງຂໍ້ມູນ array a [] ຂອງຂະ ໜາດ n. ການຈັດລຽງ ອົງປະກອບຂອງອາເລທີ່ໃຫ້ໂດຍໃຊ້ stack ໂຄງສ້າງຂໍ້ມູນ.

ການຈັດລຽງການຈັດລຽງໂດຍໃຊ້ Stacks

ຍົກຕົວຢ່າງ

2 30 -5 43 100
-5 2 30 43 100

ຄໍາອະທິບາຍ: ອົງປະກອບຕ່າງໆຖືກຈັດຮຽງຕາມລໍາດັບຕັ້ງຊັນຂຶ້ນ.

2 3 1 8 6
1 2 3 6 8

ວິທີການ ສຳ ລັບການຈັດລຽງການ ນຳ ໃຊ້ Stacks

ສ້າງໂຄງສ້າງຂໍ້ມູນແບບ stack ເພື່ອເກັບຮັກສາອົງປະກອບທັງ ໝົດ ຂອງເຄື່ອງປ້ອນຂໍ້ມູນທີ່ໃຫ້ໄວ້ເປັນ a []. ຫລັງຈາກນັ້ນ, ສ້າງຄັງຊົ່ວຄາວອີກອັນ ໜຶ່ງ ສຳ ລັບການຈັດຮຽງແບບເດີມ. Iterate ຜ່ານ stack ຕົ້ນສະບັບແລະສໍາລັບແຕ່ລະອົງປະກອບກົດເທິງແລະເກັບມັນໄວ້ໃນຕົວແປຊົ່ວຄາວ. ເຊັ່ນດຽວກັນ, iterate ຜ່ານ stack ຊົ່ວຄາວໃນຂະນະທີ່ອົງປະກອບທີ່ຢູ່ເທິງສຸດຂອງ stack ຊົ່ວຄາວແມ່ນຫນ້ອຍກ່ວາຊັ້ນເທິງຂອງ stack ເດີມ. ໃສ່ສ່ວນປະກອບຊັ້ນສູງສຸດຂອງ stack ຊົ່ວຄາວໃນ stack ເດີມແລະເອົາມັນອອກຈາກ stack ຊົ່ວຄາວ. ຍູ້ເບື້ອງເທິງຂອງ stack ເດີມໃນ stack ຊົ່ວຄາວ. ໃນທີ່ສຸດ, ຄອກຊົ່ວຄາວຈະມີສ່ວນປະກອບໃນການຈັດຮຽງຕາມ ລຳ ດັບ. ບັນຫານີ້ແມ່ນການດັດແກ້ເລັກນ້ອຍໃນການຈັດຮຽງ a stack ໂດຍໃຊ້ stack ຊົ່ວຄາວ.

ລະບົບວິເຄາະ

  1. ເລີ່ມຕົ້ນຂບວນ a [] ຂອງຂະ ໜາດ n.
  2. ສ້າງໂຄງສ້າງຂໍ້ມູນສະເຕກ. ຂ້າມຜ່ານອາເລ a [] ແລະຍູ້ສ່ວນປະກອບທັງ ໝົດ ຂອງອາເລ a [] ລົງໃນກະດານ.
  3. ເຊັ່ນດຽວກັນ, ສ້າງ stack ຊົ່ວຄາວອື່ນ.
  4. Traverse ໃນຂະນະທີ່ຂະ ໜາດ ຂອງ stack ເດີມບໍ່ແມ່ນ 0. ສ້າງຕົວປ່ຽນແປງ tmp ແລະເກັບຮັກສາອົງປະກອບທີ່ຢູ່ເທິງສຸດຂອງ stack ເດີມໃນນັ້ນແລະກົດມັນຈາກ stack ເດີມ.
  5. ຕິດຕາມອີກຄັ້ງໃນຂະນະທີ່ stack ຊົ່ວຄາວບໍ່ຫວ່າງແລະປ້ອນອົງປະກອບທີ່ຢູ່ເທິງສຸດຂອງ stack ຊົ່ວຄາວຈົນກວ່າມັນຈະນ້ອຍກວ່າຕົວແປ tmp. ໃນຂະນະທີ່ popping ຈາກ stack ຊົ່ວຄາວ, ຍູ້ອົງປະກອບດ້ານເທິງຂອງ stack ຊົ່ວຄາວໃນ stack ເດີມ.
  6. ຍູ້ຕົວແປ tmp ຕົວແປໄວ້ໃນ stack ຊົ່ວຄາວ.
  7. Traverse ຈາກ 0 ເຖິງ n-1 ແລະເກັບຮັກສາອົງປະກອບຊັ້ນເທິງຂອງ stack ຊົ່ວຄາວໃນ array a [] ທີ່ດັດສະນີປັດຈຸບັນແລະປ/ອບ / ລຶບອົງປະກອບອອກຈາກ stack ຊົ່ວຄາວ.
  8. ສຸດທ້າຍ, Traverse ຈາກ 0 ເຖິງ n-1 ແລະພິມແຖວແຖວ [].

ລະຫັດ

ໂປຣແກຣມ C ++ ສຳ ລັບຈັດລຽງການຈັດລຽງໂດຍໃຊ້ Stacks

#include <iostream>
#include <stack> 
using namespace std; 
  
stack<int> sortStack(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; 
} 
  
void sortUsingStack(int arr[], int n){ 
     
    stack<int> input; 
    for(int i=0; i<n; i++){ 
       input.push(arr[i]); 
    }
  
    stack<int> tmpStack = sortStack(input); 
  
    for(int i=0; i<n; i++){ 
        arr[i] = tmpStack.top(); 
        tmpStack.pop(); 
    } 
} 
  
int main(){ 
    int a[] = {2, 30, -5, 43, 100}; 
    int n = sizeof(a)/sizeof(a[0]); 
  
    sortUsingStack(a, n); 
  
    for(int i=0; i<n; i++) 
       cout << a[i] << " "; 
  
    return 0; 
}
-5 2 30 43 100

Java Program for sorting array ໂດຍໃຊ້ Stacks

import java.io.*; 
import java.util.*; 
  
class SortArrayWithStack{ 
    
    static Stack<Integer> sortStack(Stack<Integer> input){ 
        Stack<Integer> tmpStack = new Stack<Integer>(); 
      
        while(!input.empty()){ 
            int tmp = input.peek(); 
            input.pop(); 
      
            while(!tmpStack.empty() && tmpStack.peek() < tmp){ 
                input.push(tmpStack.peek()); 
                tmpStack.pop(); 
            } 
      
            tmpStack.push(tmp); 
        } 
        return tmpStack; 
    } 
      
    static void sortUsingStack(int []arr, int n){ 
        
        Stack<Integer> input = new Stack<Integer>(); 
        
        for(int i = 0; i < n; i++){ 
            input.push(arr[i]); 
        }
      
        Stack<Integer> tmpStack = sortStack(input); 
      
        for(int i = 0; i < n; i++){ 
            arr[i] = tmpStack.peek(); 
            tmpStack.pop(); 
        } 
    } 
      
    public static void main(String args[]){
        
        int []a = {2, 30, -5, 43, 100};
        int n = a.length; 
      
        sortUsingStack(a, n); 
      
        for(int i = 0; i < n; i++){ 
            System.out.print(a[i] + " "); 
        }    
    } 
}
-5 2 30 43 100

ການວິເຄາະຄວາມສັບສົນ

ຄວາມສັບສົນເວລາ

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

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

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