സ്റ്റാക്കുകൾ ഉപയോഗിക്കുന്ന ക്യൂ


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു അക്കോലൈറ്റ് അഡോബി ആമസോൺ ഡി.ഇ.ഷാ ഫ്ലിപ്പ്കാർട്ട് ഗോൾഡ്മാൻ സാക്സ് വിവരം 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 ന്റെ അടിയിലേക്ക് x തള്ളുന്നതിന് തുല്യമാണ്.

  1. St1 ൽ നിന്ന് എല്ലാ ഘടകങ്ങളും നീക്കംചെയ്‌ത് അവയെ st2 ലേക്ക് തള്ളുക.
  2. X നെ st2 ലേക്ക് പുഷ് ചെയ്യുക.
  3. St2 ൽ നിന്ന് എല്ലാ ഘടകങ്ങളും നീക്കംചെയ്‌ത് അവയെ st1 ലേക്ക് തിരികെ തള്ളുക.

സമയ സങ്കീർണ്ണത = O (n) A.

സ്റ്റാക്കുകൾ ഉപയോഗിക്കുന്ന ക്യൂ

Dequeue ()

ക്യൂവിന്റെ മുൻവശത്ത് നിന്ന് ഒരു ഘടകം നീക്കംചെയ്യുന്നത് സ്റ്റാക്ക് st1 ന്റെ മുകളിൽ നീക്കംചെയ്യുന്നതിന് സമാനമാണ്. അതിനാൽ st1 ശൂന്യമല്ലെങ്കിൽ st1 ന്റെ മുകളിൽ പോപ്പ് ചെയ്ത് മടങ്ങുക.

സമയ സങ്കീർണ്ണത = O (1)

രീതിയുടെ മൊത്തത്തിലുള്ള ബഹിരാകാശ സങ്കീർണ്ണത 1 = O (n)

സ്റ്റാക്കുകൾ ഉപയോഗിക്കുന്ന ക്യൂവിനായുള്ള ജാവ കോഡ്

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

സി ++ കോഡ്

#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- നെ ക്യൂവിന്റെ പിൻഭാഗത്തേക്ക് തള്ളുന്നത് x നെ stack_st1 ന്റെ മുകളിലേക്ക് തള്ളുന്നതിന് സമാനമാണ്. അതിനാൽ x നെ st1 ന്റെ മുകളിലേക്ക് തള്ളുക.

സമയ സങ്കീർണ്ണത = O (1)

Dequeue ()

ക്യൂവിന്റെ മുൻവശത്ത് നിന്ന് ഒരു ഘടകം നീക്കംചെയ്യുന്നത് stack_st1 ന്റെ അടിയിൽ നിന്ന് ഒരു ഘടകം നീക്കംചെയ്യുന്നതിന് സമാനമാണ്. അതിനാൽ, st1 ശൂന്യമല്ലെങ്കിൽ,

  1. St1 ൽ നിന്ന് എല്ലാ ഘടകങ്ങളും നീക്കംചെയ്‌ത് അവയെ st2 ലേക്ക് തള്ളുക.
  2. St2 ന്റെ മുകളിൽ പോപ്പ് ചെയ്ത് വേരിയബിൾ ടോപ്പിൽ സംഭരിക്കുക.
  3. St2 ൽ നിന്ന് എല്ലാ ഘടകങ്ങളും നീക്കംചെയ്‌ത് അവയെ st1 ലേക്ക് തിരികെ തള്ളുക.
  4. മുകളിലേക്ക് മടങ്ങുക

സമയ സങ്കീർണ്ണത = O (n)

സ്റ്റാക്കുകൾ ഉപയോഗിക്കുന്ന ക്യൂ

രീതിയുടെ മൊത്തത്തിലുള്ള ബഹിരാകാശ സങ്കീർണ്ണത 2 = O (n)

ജാവ കോഡ്

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

സി ++ കോഡ്

#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     റഫറൻസ് 2