ढेर का उपयोग कर कतार


कठिनाई स्तर आसान
में अक्सर पूछा एकोलाइट एडोब वीरांगना डीई शॉ फ्लिपकार्ट गोल्डमैन सैक्स जानकारी InMobi MakeMyTrip MAQ माइक्रोसॉफ्ट मॉर्गन स्टेनली ओरेकल वॉलमार्ट लैब्स
पंक्ति धुआँरा

एक का उपयोग कर कतार में धुआँरा समस्या, हमें स्टैक डेटा संरचना के मानक कार्यों का उपयोग करके एक कतार के निम्नलिखित कार्यों को लागू करना होगा,

  1. एन्क्यू: कतार के अंत में एक तत्व जोड़ें
  2. Dequeue: कतार की शुरुआत से एक तत्व निकालें

उदाहरण

इनपुट:
एनक्यू (5)
एनक्यू (11)
एनक्यू (39)
Dequeue () // रिटर्न 5
एनक्यू (12)
Dequeue () // रिटर्न 11
Dequeue () // रिटर्न 39
आउटपुट:
5
11
39

कलन विधि

दो स्टैक्स का उपयोग करके एक कतार को लागू किया जा सकता है, स्टैक का उपयोग करके एक कतार को लागू करने के दो तरीके हैं, पहला एन्क्यू ऑपरेशन को महंगा बनाना और दूसरा डीक्यू ऑपरेशन को महंगा बनाकर।

विधि 1 (स्टैक का उपयोग करके कतार के लिए महंगा एनक्यू ऑपरेशन)

दो स्टैक st1 और st2 बनाएँ। कल्पना कीजिए पंक्ति st1 में, st1 का शीर्ष कतार के सामने है, और st1 में नीचे की ओर बढ़ना कतार में आगे बढ़ने के समान है।

एन्क्यू (x)

कतार के पीछे x को स्टैक st1 के निचले भाग में धकेलने के समान है।

  1. सभी तत्वों को st1 से निकालें और उन्हें st2 पर धकेलें।
  2. St2 को x पुश करें।
  3. St2 से सभी तत्वों को निकालें और उन्हें st1 पर वापस धकेलें।

समय जटिलता = एक पर

ढेर का उपयोग कर कतार

Dequeue ()

कतार के सामने से एक तत्व निकालना स्टैक st1 के शीर्ष को हटाने के समान है। इसलिए यदि st1, st1 के शीर्ष को खाली न करे और वापस लौटे।

समय जटिलता = ओ (1)

विधि 1 की कुल मिलाकर अंतरिक्ष जटिलता = पर)

ढेर का उपयोग कर कतार के लिए जावा कोड

import java.util.Stack;

public class QueueUsingStacks {
    // Costly Enqueue Operation
    private static Stack<Integer> st1;
    private static Stack<Integer> st2;

    private static void enqueue(int x) {
        // remove all the elements from st1 and push them to st2
        while (!st1.isEmpty()) {
            st2.push(st1.pop());
        }

        // push x to st2
        st2.push(x);

        // remove all the elements from st2 and push them back to st1
        while (!st2.isEmpty()) {
            st1.push(st2.pop());
        }
    }

    private static int dequeue() {
        if (st1.isEmpty()) {
            return -1;
        }

        // if st1 is not empty return and remove the top of st1
        return st1.pop();
    }

    public static void main(String[] args) {
        st1 = new Stack<>();
        st2 = new Stack<>();
        
        // Example
        enqueue(5);
        enqueue(11);
        enqueue(39);
        System.out.println(dequeue());
        enqueue(12);
        System.out.println(dequeue());
        System.out.println(dequeue());
    }
}
5
11
39

C ++ कोड

#include<bits/stdc++.h> 
using namespace std;

// Costly Enqueue Operation

stack<int> st1;
stack<int> st2;

void enqueue(int x) {
    // remove all the elements from st1 and push them to st2
    while (!st1.empty()) {
        int curr = st1.top();
        st1.pop();
        st2.push(curr);
    }
    
    // push x to st2
    st2.push(x);
    
    // remove all the elements from st2 and push them back to st1
    while (!st2.empty()) {
        int curr = st2.top();
        st2.pop();
        st1.push(curr);
    }
}

int dequeue() {
    if (st1.empty()) {
        return -1;
    }
    
    // if st1 is not empty return and remove the top of st1
    int top = st1.top();
    st1.pop();
    return top;
}

int main() {
    // Example
    enqueue(5);
    enqueue(11);
    enqueue(39);
    cout<<dequeue()<<endl;
    enqueue(12);
    cout<<dequeue()<<endl;
    cout<<dequeue()<<endl;
    
    return 0;
}
5
11
39

विधि 2 (स्टेक का उपयोग करके कतार के लिए महंगा ऑपरेशन)

दो स्टैक बनाएं st1 और st2। St1 में विज़ुअलाइज़ कतार, st1 का शीर्ष कतार के पीछे का प्रतिनिधित्व करता है, st1 में ऊपर की ओर बढ़ना कतार में आगे बढ़ने के समान है।

एन्क्यू (x)

कतार के पीछे x को पुश करना, stack_st1 के शीर्ष पर x को धकेलने के समान है। तो st1 के शीर्ष पर x पुश करें।

समय जटिलता = ओ (1)

Dequeue ()

कतार के सामने से एक तत्व को निकालना, stack_st1 के नीचे से एक तत्व को हटाने के समान है। तो, अगर st1 खाली नहीं है,

  1. सभी तत्वों को st1 से निकालें और उन्हें st2 पर धकेलें।
  2. St2 के शीर्ष को पॉप करें और इसे एक वेरिएबल टॉप में स्टोर करें।
  3. St2 से सभी तत्वों को निकालें और उन्हें st1 पर वापस धकेलें।
  4. शीर्ष पर लौटें

समय जटिलता = पर)

ढेर का उपयोग कर कतार

विधि 2 की कुल मिलाकर अंतरिक्ष जटिलता = पर)

जावा कोड

import java.util.Stack;

public class QueueUsingStacks {
    // Costly Dequeue Operation
    private static Stack<Integer> st1;
    private static Stack<Integer> st2;

    private static void enqueue(int x) {
        // push x to top of st1
        st1.push(x);
    }

    private static int dequeue() {
        if (st1.isEmpty()) {
            return -1;
        }

        // if st1 is not empty
        // remove all the elements from st1 and push them to st2
        while (!st1.isEmpty()) {
            st2.push(st1.pop());
        }

        // pop the top of st2 and store it in a variable top
        int top = st2.pop();

        // remove all the elements from st2 and push them back to st1
        while (!st2.isEmpty()) {
            st1.push(st2.pop());
        }
        
        // return top
        return top;
    }

    public static void main(String[] args) {
        st1 = new Stack<>();
        st2 = new Stack<>();

        // Example
        enqueue(5);
        enqueue(11);
        enqueue(39);
        System.out.println(dequeue());
        enqueue(12);
        System.out.println(dequeue());
        System.out.println(dequeue());
    }
}
5
11
39

C ++ कोड

#include<bits/stdc++.h> 
using namespace std;

// Costly Dequeue Operation

stack<int> st1;
stack<int> st2;

void enqueue(int x) {
    // push x to top of st1
    st1.push(x);
}

int dequeue() {
    if (st1.empty()) {
        return -1;
    }
    
    // if st1 is not empty
    // remove all the elements from st1 and push them to st2
    while (!st1.empty()) {
        int curr = st1.top();
        st1.pop();
        st2.push(curr);
    }
    
    // pop the top of st2 and store it in a variable top
    int top = st2.top();
    st2.pop();
    
    // remove all the elements from st2 and push them back to st1
    while (!st2.empty()) {
        int curr = st2.top();
        st2.pop();
        st1.push(curr);
    }
    
    // return top
    return top;
}

int main() {
    // Example
    enqueue(5);
    enqueue(11);
    enqueue(39);
    cout<<dequeue()<<endl;
    enqueue(12);
    cout<<dequeue()<<endl;
    cout<<dequeue()<<endl;
    
    return 0;
}
5
11
39

संदर्भ 1     संदर्भ २