Убакытты колдонуп, стекти иреттөө


Кыйынчылык деңгээли орто
Көп суралган Amazon 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. Андан кийин функцияны түзүңүз sort (), ал стекти параметр катары кабыл алат. Андагы дагы бир убактылуу / жардамчы стекти баштаңыз.
  3. Түпнуска стек бош болбостон өтүңүз, өзгөрүлмө tmp түзүңүз жана анда баштапкы стектин үстүн сактаңыз. Андан кийин баштапкы стектин үстү жагын ачыңыз.
  4. Дагы бир жолу Travers 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 элементтер үчүн убактылуу стек мейкиндигин колдондук. Алгоритм үчүн баштапкы стек колдонулган мейкиндик эсептелбейт.