තොගයක මැද අංගය මකන්න


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇමේසන්
රචනය අඩුක්කුව

ගැටළු ප්රකාශය

දත්ත ව්‍යුහයක් (තොගයක්) ලබා දී ඇත. තොගයේ මූලික කාර්යයන් භාවිතා කර දී ඇති තොගයේ මැද අංගය මකා දැමීමට වැඩසටහනක් ලියන්න -

  • push () - තොගයේ මූලද්‍රව්‍යයක් ඇතුළු කිරීමට.
  • pop () - තොගයේ ඉහළ අංගය ඉවත් කිරීමට / මකා දැමීමට.
  • හිස් () - තොගයේ ප්‍රමාණය 0 ට වඩා වැඩි ද නැද්ද යන්න පරීක්ෂා කිරීම.

යාවත්කාලීන කරන ලද තොගය මුද්‍රණය කරන්න, එනම් මැද ඇති මූලද්‍රව්‍යය මකා දැමීමෙන් පසු තොගය. වෙනත් දත්ත ව්‍යුහයක් භාවිතා කිරීමට අවසර නැත.

තොගයක මැද අංගය මකන්න

උදාහරණයක්

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

ඇල්ගොරිතම

  1. ආරම්භ කරන්න a අඩුයි දත්ත ව්‍යුහය සහ එහි ඇති මූලද්‍රව්‍ය තල්ලු කරන්න.
  2. ශ්‍රිතයක් සාදන්න deleteMiddle එය තොගය පිළිගන්නා අතර, එහි පරාමිතීන් ලෙස වත්මන් දර්ශකය නිරූපණය කිරීමට එහි ප්‍රමාණය සහ විචල්‍යය. වත්මන් දර්ශක විචල්‍යයේ පෙරනිමි අගය 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

තොගයක මැද අංගය මකා දැමීමට ජාවා වැඩසටහන

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) කාලය ගතවේ. මේ අනුව ඇල්ගොරිතම සඳහා කාල සංකීර්ණතාව රේඛීය වේ.

අභ්‍යවකාශ සංකීර්ණතාව

මත) අප විසින් පුනරාවර්තනය භාවිතා කරන බැවින් ඉවත් කරන ලද මූලද්‍රව්‍ය ගබඩා කිරීම සඳහා ඉඩ භාවිතා කරනු ඇත.