एकल प que्क्ति प्रयोग गरेर स्ट्याक लागू गर्नुहोस्


कठिनाई तह सजिलो
बारम्बार सोधिन्छ अमेजन फोरकाइट्स गुगल infosys MAQ माइक्रोसफ्ट
लाम थाक

समस्या वक्तव्य

समस्या "एकल प que्क्ति प्रयोग गरेर स्ट्याक कार्यान्वयन गर्नुहोस्" हामीलाई स्ट्याक (LIFO) डाटा संरचना लाई कतार (FIFO) डेटा संरचना प्रयोग गरेर कार्यान्वयन गर्न सोध्छ।

यहाँ LIFO को अर्थ लास्ट इन फर्स्ट आउट भने FIFO को अर्थ फर्स्ट इन फर्स्ट आउट

एकल प que्क्ति प्रयोग गरेर स्ट्याक लागू गर्नुहोस्

उदाहरणका

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

स्पष्टीकरण

मानौं हामीसँग कतार छ, र अब हामी यसमा एलिमेन्टहरू थप्न थाल्छौं। यसमा तत्वहरू थप्न वा सम्मिलित गर्नका लागि। हामी कल गर्नेछौं पुश समारोह।

(१) push> कतारको वर्तमान स्थिति -> १

(१) push> कतारको वर्तमान स्थिति -> १

यो गर्नको लागि, हामी सबै तत्वहरू हटाउनेछौं जुन पहिले कतारमा थिए। त्यसो भए हामीले खाली पue्क्तिमा नयाँ तत्व घुसाउँछौं। पछि हामी फेरि हटाइएका तत्वहरूलाई समान क्रममा धकेल्दछौं।

लामको शीर्ष / अगाडि हेर्दै, यसले हामीलाई परिणाम स्वरूप २ दिन्छ।

q.top () = २

शीर्ष तत्व हटाउनुहोस्। त्यसैले हामी कतारबाट २ हटाइरहेका छौं।

त्यसो भए हटाएपछि, कतारको वर्तमान स्थिति = १।

एकल पue्क्ति प्रयोग गरेर स्ट्याक कार्यान्वयन गर्न एल्गोरिथ्म

  1. एक साथ एक वर्ग स्ट्याक शुरू गर्नुहोस् लाम को डेटा संरचना पूर्णांक निजी सदस्यको रूपमा टाइप गर्नुहोस्। हामी पनि परिभाषित गर्दछौं पुश, पप, माथि, खाली यो सार्वजनिक सदस्य कार्य हो रूपमा।
  2. खाली प्रकार्य सिर्जना गर्नुहोस् ()। सही फिर्ती गर्नुहोस् यदि पue्क्ति खाली छ अन्यथा गलत फिर्ता।
  3. पुश () ले पूर्णांक मान स्वीकार गर्दछ। इन्टिजर भेरियबल बनाउँनुहोस् र भ्यारीएबलमा कतारको साइज भण्डार गर्नुहोस् र लाममा इन्टिजर भ्यारीएबललाई प push्क्तिमा घुसाउँनुहोस्।
  4. 0 बाट प XNUMX्क्तिको अघिल्लो आकारमा। प to्क्तिको वर्तमान अगाडि आफैंमा घुसाउनुहोस् र यसलाई हटाउनुहोस्।
  5. प्रकार्य पप () सिर्जना गर्नुहोस् जसले लाममा कुनै एलिमेन्ट छैन भने जाँच गर्दछ त्यसपछि “एलिमेन्ट छैन” र फिर्ता -१ प्रिन्ट गर्नुहोस्। अन्य पप / शीर्ष / फ्रन्ट तत्व हटाउनुहोस्।
  6. हामी प्रकार्य शीर्ष () सिर्जना गर्छौं जुन -१ फर्काउँछ यदि लाममा कुनै एलिमेन्ट छैन भने लामको अगाडि फर्काउँछ।

कोड

C ++ कार्यक्रम एकल पue्क्ति प्रयोग गरेर स्ट्याक कार्यान्वयन गर्न

#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

जाभा कार्यक्रम एकल पue्क्ति प्रयोग गरेर स्ट्याक कार्यान्वयन गर्न

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 (१)। किनकि कुनै एलिमेन्ट धकेल्नका लागि हामी हटाउँछौं र त्यसमा अवस्थित रहेका एलिमेन्ट्सको संख्या थप्दछौं। यसले बहुपद समयमा अपरेशनलाई चलाउँदछ।

ठाउँ जटिलता

ऊ) किनकि हामी खाली ठाउँहरू प्रयोग गर्दै छौं संख्याको एन संख्याहरू भण्डार गर्न।