عارضي اسٽيڪ استعمال ڪندي اسٽيڪ جي ترتيب ڏيو


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon Goldman سيچ IBM ڪليزا ياهو
ترتيب ڏيڻ چتي

مسئلي جو بيان

مسئلو ”عارضي اسٽيڪ استعمال ڪندي اسٽيڪ کي ترتيب ڏيو” بيان ڪري ٿو ته توهان کي هڪ ڏني وئي آهي اسٽيڪ ڊيٽا جو structureانچو. عارضي اسٽيڪ جي استعمال سان ڏنل اسٽيڪ جي عناصر ترتيب ڏيو.

عارضي اسٽيڪ استعمال ڪندي اسٽيڪ جي ترتيب ڏيو

مثال

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. ان بعد ٺاھيو فعل ٺاھيو () جيڪو اسٽيڪ کي قبول ڪري ٿو جئين اهو پيرا ميٽر هوندو آهي. ان ۾ ٻي عارضي / معاون اسٽيڪ ٽي ايم پي کي پيل ڪريو
  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

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (ن ^ 2) جتي n اسٽوري ۾ عنصرن جو تعداد آهي. جئين اسان عناصر کي عارضي اسٽيڪ کان اصلي اسٽيڪ تائين پوئتي ڌڪي رهيا آهيون ته ان صورت ۾ عارضي اسٽيڪ جي مٿانئن عنصر کي ڌڪڻ کان گهٽ آهي. بهتر سمجھڻ لاءِ ، ھڪڙي ترتيب واري ترتيب تي غور ڪريو ۽ الگورتھم کي هلائڻ جي ڪوشش ڪريو.

خلائي پيچيدگي

اي (ن) ڇاڪاڻ ته اسان اين عنصرن لاءِ عارضي اسٽيڪ جاءِ استعمال ڪئي هئي. اصلي اسٽيڪ طرفان استعمال ڪيل جڳهه الورورٿم جي شمار نه ڪئي وئي آهي.