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


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

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

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

  • пусх () - за уметање елемента у стек.
  • поп () - за уклањање / брисање горњег елемента из стека.
  • емпти () - да бисте проверили да ли је величина стека већа од 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. Проверите да ли вредност тренутне променљиве индекса није једнака половини величине стека, тј. Ако вредност тренутне променљиве индекса није једнака средњем индексу стека, гурните променљиву к назад у стек.
  7. После тога пређите док величина стека није једнака 0. Направите променљиву п и у њу сместите врх стека, искочите врх стека и одштампајте променљиву п за све итерације.

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

код

Ц ++ програм за брисање средњег елемента стека

#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

Јава програм за брисање средњег елемента стека

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

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

Сложеност времена

НА) где је н број елемената у стеку. Зато што смо уклонили све елементе из стека, а затим их поново убацили у стек. Уметање и уклањање елемента из стека траје О (1) време. Стога је временска сложеност алгоритма линеарна.

Сложеност простора

НА) јер користимо рекурзију која ће користити простор за чување уклоњених елемената.