క్యూ యొక్క మొదటి K మూలకాలను తిప్పికొట్టడం


కఠినత స్థాయి సులువు
తరచుగా అడుగుతుంది నలుపు రాయి జెపి మోర్గాన్ రాబిన్ హుడ్ స్ప్రింక్లర్ వూకర్ ZScaler
క్యూ స్టాక్

క్యూ సమస్య యొక్క మొదటి K మూలకాలను తిప్పికొట్టడంలో మేము a క్యూ మరియు ఒక సంఖ్య k, క్యూ యొక్క ప్రామాణిక కార్యకలాపాలను ఉపయోగించి క్యూ యొక్క మొదటి k మూలకాలను రివర్స్ చేయండి.

ఉదాహరణలు

ఇన్పుట్:
క్యూ = 10 -> 15 -> 31 -> 17 -> 12 -> 19 -> 2
k = 3
అవుట్పుట్:
క్యూ = 31 -> 15 -> 10 -> 17 -> 12 -> 19 -> 2

ఇన్పుట్:
క్యూ = 12 -> 14 -> 16 -> 7 -> 9
k = 2
అవుట్పుట్:
క్యూ = 14 -> 12 -> 16 -> 7 -> 9

క్యూ యొక్క మొదటి K అంశాలను తిప్పికొట్టడానికి అల్గోరిథం

క్యూ యొక్క మొదటి k మూలకాలను తిప్పికొట్టడానికి మనం స్టాక్‌ను ఉపయోగించవచ్చు.

  1. క్యూ యొక్క మొదటి k మూలకాలను తీసివేసి వాటిని స్టాక్‌లోకి నెట్టండి.
  2. స్టాక్ యొక్క అన్ని అంశాలను పాప్ చేసి, వాటిని క్యూ చివరికి నెట్టండి.
  3. క్యూ ముందు నుండి పాప్-అవుట్ (n - k) మూలకాలు మరియు వాటిని క్యూ చివరికి నెట్టండి, ఇక్కడ n అనేది క్యూలోని మొత్తం మూలకాల సంఖ్య.
  4. మొదట, క్యూ యొక్క k మూలకాలు తారుమారు చేయబడతాయి, క్యూ యొక్క మూలకాలను ముద్రించండి.

క్యూ యొక్క మొదటి K అంశాలను తిప్పికొట్టడానికి వివరణ

ఒక ఉదాహరణను పరిశీలించండి,
క్యూ = 10 -> 7 -> 4 -> 3
k = 2

దశ 1

క్యూ యొక్క మొదటి k మూలకాలను తీసివేసి వాటిని స్టాక్‌లోకి నెట్టండి.
క్యూ = 10 -> 7 -> 4 -> 3 మరియు స్టాక్ = శూన్య
పునరావృతం 1
క్యూ = 7 -> 4 -> 3 మరియు స్టాక్ = 10
పునరావృతం 2
క్యూ = 4 -> 3 మరియు స్టాక్ = 7 -> 10

దశ 2

స్టాక్ యొక్క అన్ని అంశాలను పాప్ చేసి, వాటిని క్యూ చివరికి నెట్టండి.
క్యూ = 4 -> 3 మరియు స్టాక్ = 7 -> 10
పునరావృతం 1
క్యూ = 4 -> 3 -> 7 మరియు స్టాక్ = 10
పునరావృతం 2
క్యూ = 4 -> 3 -> 7 -> 10 మరియు స్టాక్ = శూన్య

దశ 3

క్యూ ముందు నుండి (n - k) మూలకాలను పాప్ అవుట్ చేసి, వాటిని క్యూ చివరికి నెట్టండి
క్యూ = 4 -> 3 -> 7 -> 10
పునరావృతం 1
క్యూ = 3 -> 7 -> 10 -> 4
పునరావృతం 2
క్యూ = 7 -> 10 -> 4 -> 3

క్యూ యొక్క మొదటి K మూలకాలను తిప్పికొట్టడం

జావా కోడ్

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class ReversingTheFirstKElementsOfAQueue {
    private static void reverseKElements(Queue<Integer> queue, int k) {
        if (k < 0 || k >= queue.size() || queue.isEmpty()) {
            System.out.println("Invalid Input");
            return;
        }

        int n = queue.size();

        // remove first k elements of queue and push in stack
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < k; i++) {
            int curr = queue.poll();
            stack.push(curr);
        }
        
        // Pop out elements from stack and add to the end of the queue
        while (!stack.isEmpty()) {
            int curr = stack.pop();
            queue.add(curr);
        }

        // Remove first (n - k) elements of the queue and add them to the end
        for (int i = 0; i < n - k; i++) {
            int curr = queue.poll();
            queue.add(curr);
        }

        // Print the elements of the queue
        for (Integer i : queue) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Example 1
        Queue<Integer> q1 = new LinkedList<>();
        int k1 = 3;
        q1.add(10);
        q1.add(15);
        q1.add(31);
        q1.add(17);
        q1.add(12);
        q1.add(19);
        q1.add(2);
        reverseKElements(q1, k1);

        // Example 2
        Queue<Integer> q2 = new LinkedList<>();
        int k2 = 2;
        q2.add(12);
        q2.add(14);
        q2.add(16);
        q2.add(7);
        q2.add(9);
        reverseKElements(q2, k2);
    }
}
31 15 10 17 12 19 2 
14 12 16 7 9

సి ++ కోడ్

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

void reverseKElements(queue<int> &queue, int k) {
    if (k < 0 || k >= queue.size() || queue.empty()) {
        cout<<"Invalid Input"<<endl;
        return;
    }
    
    int n = queue.size();
    
    // remove first k elements of queue and push in stack
    stack<int> st;
    for (int i = 0; i < k; i++) {
        int curr = queue.front();
        queue.pop();
        st.push(curr);
    }
    
    // Pop out elements from stack and add to the end of the queue
    for (int i = 0; i < k; i++) {
        int curr = st.top();
        st.pop();
        queue.push(curr);
    }
    
    // Remove first (n - k) elements of the queue and add them to the end
    for (int i = 0; i < n - k; i++) {
        int curr = queue.front();
        queue.pop();
        queue.push(curr);
    }
    
    // Print the elements of the queue
    for (int i = 0; i < n; i++) {
        int curr = queue.front();
        queue.pop();
        cout<<curr<<" ";
        queue.push(curr);
    }
    cout<<endl;
}

int main() {
    // Example 1
    queue<int> q1;
    int k1 = 3;
    q1.push(10);
    q1.push(15);
    q1.push(31);
    q1.push(17);
    q1.push(12);
    q1.push(19);
    q1.push(2);
    reverseKElements(q1, k1);

    // Example 2
    queue<int> q2;
    int k2 = 2;
    q2.push(12);
    q2.push(14);
    q2.push(16);
    q2.push(7);
    q2.push(9);
    reverseKElements(q2, k2);
}
31 15 10 17 12 19 2 
14 12 16 7 9

క్యూ యొక్క మొదటి K అంశాలను తిప్పికొట్టడానికి సంక్లిష్టత విశ్లేషణ

సమయ సంక్లిష్టత = O (n + k)
అంతరిక్ష సంక్లిష్టత = అలాగే) 
ఇక్కడ n అనేది క్యూలోని మూలకాల సంఖ్య.

ప్రస్తావనలు