Анбораро бо истифодаи стаки муваққатӣ ҷудо кунед


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Amazon Голдман Sachs IBM Кулиза Yahoo
Sorting тӯда

Изҳороти мушкилот

Масъалаи "Ҷудо кардани стака бо истифодаи стаки муваққатӣ" изҳор медорад, ки ба шумо а яхдон сохтори маълумот. Унсурҳои стаки додашударо бо ёрии стаки муваққатӣ ҷудо кунед.

Анбораро бо истифодаи стаки муваққатӣ ҷудо кунед

мисол

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] ва стаки муваққатӣ = []

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 холӣ аст ва стаки муваққатӣ дар навъ аст, стаки муваққатиро аз боло чоп кунед.

Аз ин рӯ, Натиҷа: 20 9 6 4 2 -1

Алгоритми ҷобаҷогузории стака бо истифодаи стаки муваққатӣ

  1. Сохтори стек маълумотро оғоз кунед ва унсурҳои онро дохил кунед / пахш кунед.
  2. Пас аз он функсияи sort () эҷод кунед, ки стекро ҳамчун параметр қабул мекунад. Дар он анбори дигари стек муваққатӣ / ёрирасон tmpStack оғоз кунед.
  3. Дар ҳоле, ки стаки аслӣ холӣ нест, гузаред, як tmp тағирёбанда созед ва болои стаки аслиро дар он нигоҳ доред. Пас аз он поп дар болои анбора аслии.
  4. Боз Traverse while tmpStack холӣ нест ва болои tmpStack яъне стаки муваққатӣ на камтар аз ё ба тағирёбандаи tmp калонтар аст, болои стаки муваққатиро дар стаки аслӣ пахш кунед ва болои стаки муваққатиро кашед.
  5. Тағири тағирёбандаро дар стаки муваққатӣ пахш кунед.
  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 шумораи элементҳо дар стек мебошад. Азбаски мо унсурҳоро аз стаки муваққатӣ ба стаки аслӣ бармегардонем, дар сурате, ки болои стеки муваққатӣ аз унсури телашаванда камтар бошад. Барои фаҳмиши беҳтар, пайдарпаии фармоишро кам кунед ва кӯшиш кунед, ки алгоритмро иҷро кунед.

Мураккабии фазо

Эй (н) зеро мо барои n элемент фазои стакании муваққатиро истифода кардем. Фосилае, ки стаки аслӣ истифода мебарад, барои алгоритм ҳисоб карда намешавад.