একটি স্ট্যাকের মাঝারি উপাদান মুছুন


কাঠিন্য মাত্রা সহজ
প্রায়শই জিজ্ঞাসা করা হয় মর্দানী স্ত্রীলোক
recursion গাদা

সমস্যা বিবৃতি

একটি ডেটা স্ট্রাকচার (স্ট্যাক) দেওয়া হয়েছে। স্ট্যাকের প্রাথমিক ফাংশনগুলি ব্যবহার করে প্রদত্ত স্ট্যাকের মাঝারি উপাদানটি মুছতে একটি প্রোগ্রাম লিখুন -

  • চাপ () - স্ট্যাকের মধ্যে একটি উপাদান inোকাতে।
  • পপ () - স্ট্যাক থেকে শীর্ষ উপাদানটি সরিয়ে / মুছতে।
  • খালি () - স্ট্যাকের আকার 0 এর চেয়ে বড় কিনা তা পরীক্ষা করতে।

মাঝখানে উপাদান মোছার পরে আপডেট হওয়া স্ট্যাক অর্থাৎ স্ট্যাকটি প্রিন্ট করুন। অন্য কোনও ডেটা স্ট্রাকচার ব্যবহারের অনুমতি নেই।

একটি স্ট্যাকের মাঝারি উপাদান মুছুন

উদাহরণ

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

অ্যালগরিদম

  1. সূচনা a গাদা ডেটা স্ট্রাকচার এবং এতে থাকা উপাদানগুলিকে পুশ করুন।
  2. একটি ফাংশন তৈরি করুন মুছে ফেলা এটি স্ট্যাক গ্রহণ করে, এটি আকার এবং এটির পরামিতি হিসাবে বর্তমান সূচককে উপস্থাপন করার জন্য একটি পরিবর্তনশীল। বর্তমান সূচক ভেরিয়েবলের ডিফল্ট মান 0 হিসাবে সেট করুন।
  3. স্ট্যাকটি খালি আছে কিনা তা পরীক্ষা করুন বা বর্তমান সূচক ভেরিয়েবল স্ট্যাকের আকারের সমান, ফিরে আসুন।
  4. একটি পরিবর্তনশীল তৈরি করুন x এবং এটিতে স্ট্যাকের শীর্ষটি সঞ্চয় করুন। স্ট্যাকের শীর্ষে উপাদানটি সরান / মুছুন।
  5. স্ট্যাকের আকার, স্ট্যাকের আকার এবং বর্তমান সূচিপত্রের পরিবর্তনশীল +1 এর পরামিতি হিসাবে এটির সাথে ফাংশনে পুনরাবৃত্ত কলটি করুন।
  6. বর্তমান সূচক ভেরিয়েবলের মান স্ট্যাকের আকারের অর্ধেকের সমান নয় কিনা তা পরীক্ষা করুন অর্থাৎ যদি বর্তমান সূচক ভেরিয়েবলের মান স্ট্যাকের মধ্য সূচকের সমান না হয় তবে ভেরিয়েবল এক্সটিকে স্ট্যাকের পিছনে চাপুন।
  7. এর পরে, স্ট্যাকের আকার 0 এর সমান না হয়ে ট্র্যাভার্স করুন একটি ভেরিয়েবল পি তৈরি করুন এবং এতে স্ট্যাকের শীর্ষটি সংরক্ষণ করুন, স্ট্যাকের শীর্ষটি পপ করুন এবং সমস্ত পুনরাবৃত্তির জন্য ভেরিয়েবল পি মুদ্রণ করুন।

এটি কাজ করে কারণ আমরা ভেরিয়েবলের মধ্যে স্ট্যাক করে রেখেছি এমন স্ট্যাকের শীর্ষে রাখতে আমরা পুনরাবৃত্তির সহায়তা নিচ্ছি x সঞ্চিত রাখা। আমরা মূল স্ট্যাক থেকে উপাদানগুলি অপসারণ করি এবং ভেরিয়েবলের ভিতরে সংরক্ষণ করি oring যা এখানে অস্থায়ী স্ট্যাক হিসাবে কাজ করে। এবং আমরা সেই উপাদানটি বাদ দিয়ে সমস্ত উপাদানগুলি মূল স্ট্যাকের মধ্যে আবার সন্নিবেশ করান যার জন্য বর্তমানের মান = n / 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

জটিলতা বিশ্লেষণ

সময় জটিলতা

চালু) যেখানে n হ'ল উপাদানগুলির সংখ্যা। কারণ আমরা স্ট্যাক থেকে সমস্ত উপাদান সরিয়ে ফেলেছি এবং সেগুলি আবার স্ট্যাকের মধ্যে sertedোকিয়েছি serted স্ট্যাক থেকে কোনও উপাদান সন্নিবেশ এবং অপসারণে ও (1) সময় লাগে। সুতরাং অ্যালগরিদমের জন্য সময় জটিলতা লিনিয়ার।

স্পেস জটিলতা ity

চালু) কারণ আমরা পুনরাবৃত্তি ব্যবহার করছি যা সরানো উপাদানগুলি সংরক্ষণের জন্য স্থান ব্যবহার করবে।