Стекро бо истифодаи рекурсия ҷудо кунед


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

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

Масъалаи "Ҷудо кардани стака бо истифодаи рекурсия" мегӯяд, ки ба шумо a яхдон сохтори маълумот. Sort унсурҳои он бо истифодаи рекурсия. Танҳо функсияҳои дар поён овардашудаи стакро истифода бурдан мумкин аст -

  • push (унсур) - ба анбор дохил кардани элемент.
  • pop () - pop () - барои нест кардан / нест кардани элемент дар болои стеки додашуда.
  • isEmpty () - барои санҷидани он, ки дар стек ягон элемент мавҷуд аст ё не.
  • top () - унсурро дар болои стеки додашуда дида баромадан / дидан.

Стекро бо истифодаи рекурсия ҷудо кунед

мисол

9 4 2 -1 6 20
20 9 6 4 2 -1

Шарҳ: Азбаски стака бо тартиби афзоиш мураттаб карда шудааст. Унсури максималӣ дар боло меояд. Азбаски стек сохтори маълумоти LIFO мебошад, натиҷа ба тариқи камшаванда ба назар мерасад.

2 1 4 3 6 5
6 5 4 3 2 1

Алгоритм

  1. Оғози а яхдон ва унсурҳоро дар он тела диҳед.
  2. Барои дохил кардани элементҳо бо тартиби мураттаб дар стак, ки стек ва элементро ҳамчун параметр қабул мекунад, эҷод кунед. Тафтиш кунед, ки анбора холӣ аст ё унсури додашуда аз унсури болои стек калонтар аст, унсурро дар анбор тела диҳед ва баргардед.
  3. Як тағирёбандаи муваққатӣ эҷод кунед ва дар болои он стекро нигоҳ доред. Элементро дар болои стак ҷойгир кунед ва ба функсия худи рекурсивӣ занг занед. Тағирёбандаи муваққатиро дар анбор пахш кунед.
  4. Ба ҳамин монанд, функсияи sort () -ро эҷод кунед, ки стекро ҳамчун параметр қабул кунад. Тафтиш кунед, ки анбора холӣ нест, тағирёбандаи хро эҷод кунед ва қисми болоии онро дар он нигоҳ доред. Элементро дар болои стака гузоред. Ба функсия худи занг занед. Барои ба стек дохил кардани элементҳо бо функсия занг занед.
  5. Функсияи навъро дар main () даъват кунед.
  6. Барои чоп кардани стеки мураттаб функсия эҷод кунед, ки стекро ҳамчун параметр қабул мекунад. Ҳангоме ки стек холӣ нест, гузаред, маълумоти стекро чоп кунед ва ба элементи навбатӣ гузаред.

рамз

C ++ Барнома барои ҷобаҷогузории стака бо истифодаи рекурсия

#include <iostream> 
using namespace std; 
  
struct stack{  
    int data;  
    struct stack *next;  
};  
  
void initStack(struct stack **s){  
    *s = NULL;  
}  
  
int isEmpty(struct stack *s){  
    if(s == NULL){  
        return 1;  
    }    
    return 0;  
}  
  
void push(struct stack **s, int x){
    
    struct stack *p = (struct stack *)malloc(sizeof(*p));  
  
    if(p == NULL){  
        return;  
    }  
  
    p->data = x;  
    p->next = *s;  
    *s = p;  
}  
  
int pop(struct stack **s){  
    int x;  
    struct stack *temp;  
  
    x = (*s)->data;  
    temp = *s;  
    (*s) = (*s)->next;  
    free(temp);  
  
    return x;  
}  
  
int top(struct stack *s){  
    return (s->data);  
}  
  
void InsertWithSort(struct stack **s, int x){  
    
    if(isEmpty(*s) or x > top(*s)){  
        push(s, x);  
        return;  
    }  
  
    int temp = pop(s);  
    InsertWithSort(s, x);  
  
    push(s, temp);  
}  
  
void sort(struct stack **s){  
    
    if(!isEmpty(*s)){  
        int x = pop(s);  
  
        sort(s);  
  
        InsertWithSort(s, x);  
    }  
}  
  
void print(struct stack *s){  
    while(s){  
        cout<<s->data<<" "; 
        s = s->next;  
    }  
}  
  
int main(){  
    struct stack *top;  
  
    initStack(&top);
    
    push(&top, 9);  
    push(&top, 4);  
    push(&top, 2);  
    push(&top, -1);  
    push(&top, 6);
    push(&top, 20);
  
    sort(&top);  
    
    print(top);  
  
    return 0;  
}
20 9 6 4 2 -1

Барномаи Java барои ҷобаҷогузории стака бо истифодаи рекурсия

import java.util.ListIterator; 
import java.util.Stack; 
  
class SortStack{ 
    
    static void InsertWithSort(Stack<Integer> s, int x){ 
        if (s.isEmpty() || x > s.peek()){ 
            s.push(x); 
            return; 
        } 
       
        int temp = s.pop(); 
        InsertWithSort(s, x); 
       
        s.push(temp); 
    } 
       
    static void sort(Stack<Integer> s){ 
        if(!s.isEmpty()){ 
            int x = s.pop(); 
       
            sort(s); 
       
            InsertWithSort(s, x); 
        } 
    } 
      
    static void print(Stack<Integer> s){ 
       ListIterator<Integer> lt = s.listIterator(); 
         
        while(lt.hasNext()){ 
            lt.next(); 
        }       
         
        while(lt.hasPrevious()){ 
           System.out.print(lt.previous()+" ");
        }   
    } 
    
    public static void main(String[] args){
        Stack<Integer> s = new Stack<>(); 
        
        s.push(9);  
        s.push(4);  
        s.push(2);  
        s.push(-1);  
        s.push(6);
        s.push(20); 
       
        sort(s); 
       
        print(s); 
       
    } 
}
20 9 6 4 2 -1

Таҳлили мураккабӣ

Мураккабии вақт

О (N ^ 2) ки дар он n шумораи элементҳо дар стек мебошад. Зеро вақте ки мо элементро дар анбор тела медиҳем, мо метавонем ҳамаи унсурҳои дар стек мавҷудбударо бартараф кунем ва сипас онро гузорем. Ин ҳолат рух медиҳад, агар вуруд бо тартиби камшаванда бошад.

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

О (Н) зеро мо фазои стекро барои n унсур истифода кардем. Ҳангоми хориҷ кардани унсурҳо барои ҷойгир кардани унсури ҷории мо. Мо бояд унсурҳои хориҷшударо нигоҳ медоштем, ки ин ба мо мураккабии фазоии хатиро медиҳад.