Bir yığının orta elementini silin

Problem bəyanat

Bir məlumat strukturu (yığın) verilmişdir. Yığın əsas funksiyalarından istifadə edərək verilmiş yığının orta elementini silmək üçün bir proqram yazın -

• push () - yığına bir element daxil etmək.
• pop () - üst elementi yığından çıxarmaq / silmək üçün.
• empty () - yığının ölçüsünün 0-dan çox olub olmadığını yoxlamaq.

Yenilənmiş yığını, yəni ortadakı elementin silinməsindən sonra yığını çap edin. Başqa bir məlumat strukturunun istifadəsinə icazə verilmir.

Pin

misal

1 2 3 4 5

1 2 4 5

10 20 30 40 50 60

10 20 40 50 60

Alqoritm

1. Başlanğıc a qalaq məlumat quruluşu və içindəki elementləri itələyin.
2. Bir funksiya yaradın Sil Orta yığını qəbul edən, ölçüsü və cari indeksini parametrləri olaraq təmsil edəcək bir dəyişəndir. Cari indeks dəyişəninin standart dəyərini 0 olaraq təyin edin.
3. Yığının boş olub olmadığını və ya cari indeks dəyişəninin yığının ölçüsünə bərabər olduğunu yoxlayın, qayıdın.
4. Dəyişən yaradın x və yığının üst hissəsini içərisində saxlayın. Yığın üst hissəsindəki elementi silin / silin.
5. Yığın, yığının ölçüsü və indikator dəyişəninin parametrləri olduğu kimi + 1 funksiyası ilə özünə rekursiv çağırış edin.
6. Cari indeks dəyişəninin dəyərinin yığının ölçüsünün yarısına bərabər olmadığını yoxlayın, yəni indiki indeks dəyişəninin dəyəri yığının orta indeksinə bərabər deyilsə, x dəyişkənini yığının içərisinə geri çəkin.
7. Bundan sonra yığının ölçüsü 0-a bərabər olmadıqda keçin, dəyişən p yaradın və yığının üst hissəsini orada saxlayın, yığının üst hissəsini açın və bütün təkrarlamalar üçün p dəyişənini çap edin.

Bu, işlədiyimiz üçün işləyir, çünki yığdığımız yığının üst hissəsini dəyişkən saxlayırıq x saxlamağa davam etmək. Elementləri orijinal yığından çıxartmağa davam edirik və dəyişən daxilində saxlamağa davam edirik x burada müvəqqəti yığın rolunu oynayır. Və cari dəyəri = n / 2 olan element xaricində bütün elementləri yenidən orijinal yığına əlavə edirik.

Kodu

Bir yığının orta elementini silmək üçün C ++ proqramı

#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

Bir yığının orta elementini silmək üçün Java Proqramı

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N) burada n yığındakı elementlərin sayıdır. Çünki bütün elementləri yığından çıxardıq və sonra yığına yenidən daxil etdik. Bir elementin yığından yığılması və yığışdırılması O (1) vaxt aparır. Beləliklə, alqoritm üçün zaman mürəkkəbliyi xətti olur.

Kosmik Mürəkkəblik

O (N) çünki silinmiş elementlərin saxlanması üçün yer istifadə edəcək rekursiyadan istifadə edirik.