ഒരു സ്റ്റാക്കിന്റെ മധ്യ ഘടകം ഇല്ലാതാക്കുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ
റിക്കറിഷൻ കൂനകൂട്ടുക

പ്രശ്നം പ്രസ്താവന

ഒരു ഡാറ്റ ഘടന (സ്റ്റാക്ക്) നൽകി. സ്റ്റാക്കിന്റെ അടിസ്ഥാന പ്രവർത്തനങ്ങൾ ഉപയോഗിച്ച് തന്നിരിക്കുന്ന സ്റ്റാക്കിന്റെ മധ്യ ഘടകം ഇല്ലാതാക്കാൻ ഒരു പ്രോഗ്രാം എഴുതുക -

  • push () - സ്റ്റാക്കിൽ ഒരു ഘടകം ചേർക്കുന്നതിന്.
  • പോപ്പ് () - സ്റ്റാക്കിൽ നിന്ന് മുകളിലെ ഘടകം നീക്കംചെയ്യാൻ / ഇല്ലാതാക്കാൻ.
  • ശൂന്യമാണ് () - സ്റ്റാക്കിന്റെ വലുപ്പം 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. നിലവിലെ സൂചിക വേരിയബിളിന്റെ മൂല്യം സ്റ്റാക്കിന്റെ വലുപ്പത്തിന്റെ പകുതിയോട് തുല്യമല്ലേ എന്ന് പരിശോധിക്കുക, അതായത് നിലവിലെ സൂചിക വേരിയബിളിന്റെ മൂല്യം സ്റ്റാക്കിന്റെ മധ്യ സൂചികയ്ക്ക് തുല്യമല്ലെങ്കിൽ, വേരിയബിളിനെ സ്റ്റാക്കിലേക്ക് പിന്നിലേക്ക് തള്ളുക.
  7. അതിനുശേഷം, സ്റ്റാക്കിന്റെ വലുപ്പം 0 ന് തുല്യമല്ലാത്തപ്പോൾ സഞ്ചരിക്കുക. ഒരു വേരിയബിൾ പി സൃഷ്ടിച്ച് അതിൽ സ്റ്റാക്കിന്റെ മുകളിൽ സംഭരിക്കുക, സ്റ്റാക്കിന്റെ മുകളിൽ പോപ്പ് ചെയ്ത് എല്ലാ ആവർത്തനങ്ങൾക്കും വേരിയബിൾ പി പ്രിന്റുചെയ്യുക.

ഞങ്ങൾ വേരിയബിളിൽ സംഭരിച്ചിരിക്കുന്ന സ്റ്റാക്കിന്റെ മുകളിൽ സൂക്ഷിക്കാൻ ഞങ്ങൾ ആവർത്തനത്തിന്റെ സഹായം സ്വീകരിക്കുന്നതിനാലാണ് ഇത് പ്രവർത്തിക്കുന്നത് 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

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (N) ഇവിടെ n എന്നത് സ്റ്റാക്കിലെ ഘടകങ്ങളുടെ എണ്ണം. കാരണം ഞങ്ങൾ എല്ലാ ഘടകങ്ങളും സ്റ്റാക്കിൽ നിന്ന് നീക്കംചെയ്ത് വീണ്ടും സ്റ്റാക്കിലേക്ക് ചേർത്തു. സ്റ്റാക്കിൽ നിന്ന് ഒരു മൂലകത്തിന്റെ ഉൾപ്പെടുത്തലും നീക്കംചെയ്യലും O (1) സമയമെടുക്കും. അങ്ങനെ അൽഗോരിത്തിന്റെ സമയ സങ്കീർണ്ണത രേഖീയമാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (N) കാരണം ഞങ്ങൾ നീക്കംചെയ്ത ഘടകങ്ങൾ സംഭരിക്കുന്നതിന് ഇടം ഉപയോഗിക്കുന്ന ആവർത്തനമാണ് ഉപയോഗിക്കുന്നത്.