एक स्टैक के मध्य तत्व को हटा दें


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना
Recursion धुआँरा

समस्या का विवरण

एक डेटा संरचना (स्टैक) को देखते हुए। स्टैक के मूल कार्यों का उपयोग करके दिए गए स्टैक के मध्य तत्व को हटाने के लिए एक प्रोग्राम लिखें -

  • push () - स्टैक में एक तत्व सम्मिलित करने के लिए।
  • पॉप () - स्टैक से शीर्ष तत्व को हटाने / हटाने के लिए।
  • खाली () - यह जांचने के लिए कि स्टैक का आकार 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. उसके बाद, ट्रैवस करें जबकि स्टैक का आकार 0. के बराबर नहीं है। एक वेरिएबल पी बनाएं और उसमें स्टैक के शीर्ष को स्टोर करें, स्टैक के शीर्ष को पॉप करें और सभी पुनरावृत्तियों के लिए वेरिएबल पी को प्रिंट करें।

यह काम करता है क्योंकि हम स्टैक के शीर्ष को रखने के लिए पुनरावृत्ति की मदद ले रहे हैं जिसे हमने चर में संग्रहीत किया है 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) समय लगता है। इस प्रकार एल्गोरिथ्म के लिए समय जटिलता रैखिक है।

अंतरिक्ष जटिलता

पर) क्योंकि हम पुनरावर्तन का उपयोग कर रहे हैं जो हटाए गए तत्वों को संग्रहीत करने के लिए स्थान का उपयोग करेगा।