एकल रांग वापरून स्टॅकची अंमलबजावणी करा


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन फोरकाइट्स Google इन्फोसिस एमक्यू मायक्रोसॉफ्ट
रांग स्टॅक

समस्या विधान

समस्या “एकल रांगेच्या सहाय्याने स्टॅकची अंमलबजावणी करा” आम्हाला रांग (फिफा) डेटा स्ट्रक्चर वापरुन स्टॅक (LIFO) डेटा स्ट्रक्चरची अंमलबजावणी करण्यास सांगते.

येथे लिफो म्हणजे लास्ट इन फर्स्ट आउट तर फिफोचा अर्थ फर्स्ट इन फर्स्ट आउट.

एकल रांग वापरून स्टॅकची अंमलबजावणी करा

उदाहरण

push(10)
push(20)
top()
pop()
push(30)
pop()
top()
Top : 20
Pop : 20
Pop : 30
Top : 10
push(1)
push(2)
top()
pop()
Top : 2
Pop : 2

स्पष्टीकरण

समजा आपल्याकडे रांग आहे आणि आता त्यात घटक समाविष्ट करण्यास सुरवात करू. त्यामध्ये घटक समाविष्ट करण्यासाठी किंवा समाविष्ट करण्यासाठी. आम्ही कॉल करू पुश फंक्शन.

(1) push> रांगेची सद्य स्थिती -> 1 दाबा

(2) push> रांगेची सद्य स्थिती -> 2,1 दाबा

हे करण्यासाठी, आम्ही पूर्वीच्या रांगेत असलेले सर्व घटक काढून टाकू. रिकाम्या रांगेत आपण आपला नवीन घटक समाविष्ट करतो. त्यानंतर आम्ही पुन्हा त्याच क्रमाने काढलेल्या घटकांना ढकलतो.

रांगेच्या वरच्या बाजूस / समोर पहात असता, परिणामी आम्हाला 2 मिळते.

q.top () = 2

वरचा घटक काढून टाकू. तर आम्ही रांगेतून 2 काढत आहोत.

म्हणून काढल्यानंतर, रांगेची सद्यस्थिती = 1.

एकल रांग वापरून स्टॅकची अंमलबजावणी करण्यासाठी अल्गोरिदम

  1. सह क्लास स्टॅक आरंभ करा शेपूट ची डेटा स्ट्रक्चर पूर्णांक खाजगी सभासद म्हणून टाइप करा. आम्ही परिभाषित देखील करतो ढकलणे, पॉप, वर, आणि रिक्त कारण हे सार्वजनिक सदस्यांचे कार्य आहे.
  2. रिक्त कार्य तयार करा (). रांग रिकामी असल्यास सत्य परत करा किंवा चुकीचे परत आले.
  3. पुश () पूर्णांक मूल्य स्वीकारतो. पूर्णांक व्हेरिएबल तयार करा आणि व्हेरिएबलमध्ये रांगेचा आकार साठवा आणि रांगेत पूर्णांक व्हेरिएबल पुश / घाला.
  4. रांगेच्या 0 आकारापूर्वी मागील आकारापर्यंत जा. रांगेचा वर्तमान भाग स्वतःस समाविष्ट करुन तो काढत रहा.
  5. फंक्शन पॉप () तयार करा जे रांगेत कोणतेही घटक नसल्यास ते तपासते नंतर “घटक नाहीत” असे प्रिंट करा आणि -1 परत जा. अन्य पॉप / शीर्ष / पुढचा घटक काढा.
  6. आम्ही फंक्शन टॉप तयार करतो जो रांगेत कोणताही घटक नसल्यास -1 रिटर्न करतो अन्यथा रांगेचा पुढील भाग परत करतो.

कोड

एकल रांग वापरून स्टॅकची अंमलबजावणी करण्यासाठी सी ++ प्रोग्राम

#include<bits/stdc++.h> 
using namespace std; 
  
class Stack{ 
    queue<int>q;
    
public: 
    void push(int val); 
    int pop(); 
    int top(); 
    bool empty(); 
}; 
  
void Stack::push(int val){ 
    int s = q.size(); 
  
    q.push(val); 
  
    for(int i=0; i<s; i++){ 
        q.push(q.front()); 
        q.pop(); 
    } 
} 
  
int Stack::pop(){ 
    if(q.empty()){ 
        cout<<"No elements\n";
        return -1;
    }    
    else{
        int x = q.front();
        q.pop();
        return x;
    }  
} 
  
int  Stack::top(){ 
    return (q.empty())? -1 : q.front(); 
} 
  
bool Stack::empty(){ 
    return (q.empty()); 
} 
  
int main(){ 
    Stack s;
    
    s.push(10); 
    s.push(20); 
    cout<<"Top : "<<s.top()<<endl; 
    cout<<"Pop : "<<s.pop()<<endl; 
    s.push(30); 
    cout<<"Pop : "<<s.pop()<<endl;
    cout<<"Top : "<<s.top()<<endl; 

    return 0; 
}
Top : 20
Pop : 20
Pop : 30
Top : 10

जावा प्रोग्राम सिंगल रांगेत स्टॅकची अंमलबजावणी करण्यासाठी

import java.util.LinkedList; 
import java.util.Queue; 
  
class stack{ 
    Queue<Integer> q = new LinkedList<Integer>(); 
      
    void push(int val){ 
        int size = q.size(); 
          
        q.add(val); 
          
        for(int i=0; i<size; i++){ 
            int x = q.remove(); 
            q.add(x); 
        } 
    } 
      
    int pop(){ 
        if (q.isEmpty()){ 
            System.out.println("No elements"); 
            return -1; 
        } 
        int x = q.remove(); 
        return x; 
    } 
      
    int top(){ 
        if (q.isEmpty()) 
            return -1; 
        return q.peek(); 
    } 
      
    boolean isEmpty(){ 
        return q.isEmpty(); 
    } 
  
    public static void main(String[] args){ 
        stack s = new stack(); 
        
        s.push(10); 
        s.push(20); 
        System.out.println("Top : " + s.top()); 
        System.out.println("Pop : " + s.pop()); 
        s.push(30); 
        System.out.println("Pop : " + s.pop()); 
        System.out.println("Top : " + s.top());
        
    } 
}
Top : 20
Pop : 20
Pop : 30
Top : 10

गुंतागुंत विश्लेषण

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

पुश () फंक्शन घेत आहे O (n) वेळ असताना पॉप () आणि शीर्ष () फंक्शन्ससाठी फक्त स्थिर वेळ आवश्यक असतो ओ (1). कारण एखाद्या घटकास धक्का देण्यासाठी आम्ही त्यात असलेल्या घटकांची संख्या काढून टाकतो आणि जोडतो. हे ऑपरेशन बहुपदीच्या काळात चालते.

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

O (n) कारण आम्ही घटकांची संख्या संचयित करण्यासाठी जागा वापरत आहोत.