Сортування стека за допомогою рекурсії


Рівень складності Легко
Часто запитують у Амазонка Goldman Sachs IBM Куліза Yahoo
Рекурсія Стек

Постановка проблеми

У проблемі “Сортування стека за допомогою рекурсії” зазначено, що вам надано a стек структура даних. сортувати її елементи за допомогою рекурсії. Можна використовувати лише перелічені нижче функції стека -

  • 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. Ініціалізуйте a стек і штовхати в ньому елементи.
  2. Створіть функцію для вставки елементів у відсортованому порядку у стек, який приймає стек та елемент як параметр. Перевірте, чи є стек порожнім, або заданий елемент більше, ніж елемент у верхній частині стека, натисніть елемент у стеку і поверніть.
  3. Створіть тимчасову змінну та збережіть у ній верх стека. Попустіть елемент у верхній частині стека та зробіть рекурсивний виклик самої функції. Вставте тимчасову змінну в стек.
  4. Подібним чином створіть функцію sort (), яка приймає стек як параметр. Перевірте, чи стек не порожній, створіть змінну x і збережіть у ній верх стека. Попустіть елемент у верхній частині стопки. Зробіть рекурсивний виклик самої функції. Викличте функцію, щоб вставити елементи у відсортованому порядку в стек.
  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

Аналіз складності

Складність часу

O (N ^ 2) де n - кількість елементів у стосі. Тому що, коли ми штовхаємо елемент у стеку, ми можемо в підсумку видалити всі елементи, які зараз присутні в стеку, а потім вставити його. Цей випадок трапляється, якщо вхідні дані зменшуються.

Складність простору

O (N) тому що ми використовували простір стека для n елементів. Видаляючи елементи, щоб розмістити наш поточний елемент. Нам довелося зберігати вилучені елементи, що надає нам лінійної складності простору.