एकल कतार का उपयोग करके एक स्टैक लागू करें


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना चौपाई गूगल इंफोसिस MAQ माइक्रोसॉफ्ट
पंक्ति धुआँरा

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

समस्या "एकल कतार का उपयोग करके एक स्टैक लागू करें" हमें एक स्टैक (LIFO) डेटा संरचना का उपयोग करके कतार (FIFO) डेटा संरचना का उपयोग करने के लिए कहता है।

यहां LIFO का मतलब Last In First Out है जबकि FIFO का मतलब First In First Out है।

एकल कतार का उपयोग करके एक स्टैक लागू करें

उदाहरण

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) ————>> कतार की वर्तमान स्थिति -> 1

धक्का (2) ————>> कतार की वर्तमान स्थिति -> 2,1

ऐसा करने के लिए, हम उन सभी तत्वों को हटा देंगे जो पहले कतार में थे। फिर हम खाली कतार में अपना नया तत्व सम्मिलित करते हैं। बाद में हम फिर से उसी क्रम में हटाए गए तत्वों को धक्का देते हैं।

कतार के शीर्ष / सामने को देखते हुए, इस प्रकार परिणाम के रूप में हमें 2 मिलता है।

q.top () = 2

शीर्ष तत्व को हटा दें। इसलिए हम कतार से 2 निकाल रहे हैं।

इसलिए हटाने के बाद, कतार की वर्तमान स्थिति = 1।

एकल कतार का उपयोग करके एक स्टैक को लागू करने के लिए एल्गोरिदम

  1. एक के साथ एक वर्ग ढेर को प्रारंभ करें पंक्ति की डेटा संरचना पूर्णांक एक निजी सदस्य के रूप में टाइप करें। हम भी परिभाषित करते हैं धक्का, पॉप, शीर्ष, और खाली क्योंकि यह सार्वजनिक सदस्य कार्य है।
  2. फ़ंक्शन खाली () बनाएँ। अगर कतार खाली है, तो सही लौटें और असत्य वापस करें।
  3. धक्का () एक पूर्णांक मान को स्वीकार करता है। एक पूर्णांक चर बनाएं और कतार के आकार को चर में संग्रहीत करें और कतार में पूर्णांक चर डालें / डालें।
  4. कतार के पिछले आकार से 0 से पीछे। कतार के वर्तमान मोर्चे को स्वयं में सम्मिलित करने और उसे निकालने में लगे रहें।
  5. फ़ंक्शन पॉप () बनाएं जो चेक करता है कि कतार में कोई तत्व नहीं है तो "कोई तत्व नहीं" प्रिंट करें और -1 लौटें। आला पॉप / शीर्ष / सामने तत्व को हटा दें।
  6. हम फ़ंक्शन टॉप () बनाते हैं, जो -1 लौटता है यदि कतार में कोई तत्व नहीं है तो कतार के सामने वापस लौटें।

कोड

C ++ एकल कतार का उपयोग करके स्टैक को लागू करने का कार्यक्रम

#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

जटिलता विश्लेषण

समय जटिलता

धक्का () फ़ंक्शन ले रहा है पर) समय जबकि पॉप () और शीर्ष () कार्यों को निरंतर समय की आवश्यकता होती है अर्थात ओ (1)। क्योंकि एक तत्व को आगे बढ़ाने के लिए हम उन तत्वों की संख्या को हटाते हैं और जोड़ते हैं जो इसमें पहले से मौजूद थे। यह ऑपरेशन को बहुपद समय में चलाने के लिए बनाता है।

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

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