स्टॅकचे मध्यम घटक हटवा


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन
पुनरावृत्ती स्टॅक

समस्या विधान

डेटा स्ट्रक्चर (स्टॅक) दिले. स्टॅकच्या मूलभूत कार्ये वापरून दिलेल्या स्टॅकचे मध्यम घटक हटविण्यासाठी प्रोग्राम लिहा -

  • (पुश) - स्टॅकमध्ये घटक समाविष्ट करण्यासाठी.
  • पॉप () - स्टॅकमधून शीर्ष घटक काढणे / हटविणे.
  • रिक्त () - स्टॅकचा आकार 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. यानंतर, स्टॅकचा आकार ० च्या समान नसताना ट्रॅव्हर्स करा. एक व्हेरिएबल पी तयार करा आणि त्यामध्ये स्टॅकची सुरवातीला ठेवा, स्टॅकच्या शीर्षस्थानी पॉप करा आणि सर्व पुनरावृत्तीसाठी व्हेरिएबल पी मुद्रित करा.

हे कार्य करते कारण आम्ही व्हेरिएबलमध्ये संग्रहित केलेल्या स्टॅकच्या सुरवातीला ठेवण्यासाठी पुनरावृत्तीची मदत घेत आहोत x संग्रहित ठेवण्यासाठी. आम्ही मूळ स्टॅकमधून घटक काढून टाकत आहोत आणि व्हेरिएबलमध्ये संचयित करत राहतो जे येथे तात्पुरते स्टॅक म्हणून कार्य करते. आणि विद्यमान = 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 आहे कारण आम्ही सर्व घटक स्टॅकमधून काढले आहेत आणि नंतर त्यांना पुन्हा स्टॅकमध्ये समाविष्ट केले आहेत. स्टॅकमधून घटक समाविष्ट करणे आणि काढणे ओ (1) वेळ घेते. अशा प्रकारे अल्गोरिदमची वेळ अवघड असते.

स्पेस कॉम्प्लेक्सिटी

ओ (एन) कारण आम्ही रिकर्जन वापरत आहोत जे काढलेल्या घटकांच्या साठवणीसाठी जागा वापरतील.