Избришете го средниот елемент на оџакот


Ниво на тешкотија Лесно
Често прашувано во Амазон
Рекурзија Магацинот

Изјава за проблем

Со оглед на структурата на податоците (стек). Напишете програма за бришење на средниот елемент на дадениот оџак користејќи ги основните функции на оџакот -

  • push () - за да вметнете елемент во оџакот.
  • pop () - за отстранување / бришење на горниот елемент од оџакот.
  • празно () - за да проверите дали големината на оџакот е поголема од 0 или не.

Печатете го ажурираниот оџак, односно оџакот по бришењето на елементот во средината. Употребата на која било друга структура на податоци не е дозволена.

Избришете го средниот елемент на оџакот

пример

1 2 3 4 5
1 2 4 5
10 20 30 40 50 60
10 20 40 50 60

Алгоритам

  1. Иницијализира а магацинот структура на податоци и туркање на елементите во неа.
  2. Создадете функција избришете го Средниот што го прифаќа оџакот, неговата големина е и променлива за да го претстави тековниот индекс како негови параметри. Поставете ја стандардната вредност на тековната променлива на индексот како 0.
  3. Проверете дали оџакот е празен или моменталната променлива на индексот е еднаква на големината на оџакот, вратете се.
  4. Создадете променлива x и чувајте го горниот дел од оџакот во него. Отстранете го / избришете го елементот на горниот дел од оџакот.
  5. Направете рекурзивен повик кон самата функција со оџакот, големината на оџакот и вредноста на променливата на тековниот индекс + 1, бидејќи се параметри.
  6. Проверете дали вредноста на променливата на тековниот индекс не е еднаква на половина од големината на оџакот, т.е. ако вредноста на променливата на тековниот индекс не е еднаква на средниот индекс на оџакот, турнете ја променливата x назад во оџакот.
  7. После тоа, поминете низ, додека големината на оџакот не е еднаква на 0. Создадете променлива p и зачувајте го горниот дел од оџакот во него, попувајте го горниот дел од оџакот и отпечатете ја променливата p за сите повторувања.

Ова функционира затоа што бараме помош за повторување за да го задржиме горниот дел од оџакот што го зачувавме во променлива x да се чува складиран. Продолжуваме да ги отстрануваме елементите од оригиналниот оџак и продолжуваме да ги чуваме внатре во променливата кој овде делува како привремен оџак. И, повторно ги вметнуваме сите елементи во оригиналниот оџак, освен елементот за кој вредност на струјата = n / 2.

Код

Програма C ++ за бришење на средниот елемент на оџакот

#include<iostream>
#include<stack> 
using namespace std; 

void deleteMiddle(stack<char> &s, int n, int current=0){ 
    if(s.empty() || current == n){ 
        return; 
    }
    int x = s.top(); 
    s.pop();
    
    deleteMiddle(s, n, current+1); 
    
    if(current != n/2){ 
        s.push(x); 
    }
}

int main(){ 
    stack<char> st; 
    
    st.push('5'); 
    st.push('4'); 
    st.push('3'); 
    st.push('2'); 
    st.push('1'); 
    
    deleteMiddle(st, st.size()); 
    
    while(!st.empty()){ 
        char p=st.top(); 
        st.pop(); 
        cout << p << " "; 
    } 
    
    return 0; 
}
1 2 4 5

Java програма за бришење на средниот елемент на оџакот

import java.io.*; 
import java.util.*; 
  
class delMiddle{ 
  
    static void deleteMiddle(Stack<Character> st, int n, int curr){ 
          
        if(st.empty() || curr == n){ 
            return; 
        }
          
        char x = st.pop(); 
          
        deleteMiddle(st, n, curr+1); 
          
        if(curr != n/2){ 
            st.push(x); 
        }
    } 
      
    public static void main(String args[]){
        
        Stack<Character> st = new Stack<Character>(); 
      
        st.push('5'); 
        st.push('4'); 
        st.push('3'); 
        st.push('2'); 
        st.push('1'); 
        
        deleteMiddle(st, st.size(), 0); 
      
        while(!st.empty()){ 
            char p=st.pop(); 
            System.out.print(p + " "); 
        } 
    } 
}
1 2 4 5

Анализа на сложеност

Временска комплексност

НА) каде n е бројот на елементи во магацинот. Бидејќи ги отстранивме сите елементи од оџакот и потоа повторно ги вметнавме во оџакот. Вметнувањето и отстранувањето на елемент од магацинот трае O (1) време. Така, временската сложеност за алгоритмот е линеарна.

Комплексноста на просторот

НА) затоа што користиме рекурзија која ќе користи простор за складирање на отстранетите елементи.