एक कतार के पहले K तत्वों को उलट देना  


कठिनाई स्तर आसान
में अक्सर पूछा ब्लैकरॉक जेपी मॉर्गन रॉबिन हुड Sprinklr वुकर ZScaler
पंक्ति धुआँरा

एक पंक्ति समस्या के पहले K तत्वों को उलटने में हमने एक दिया है पंक्ति और एक संख्या k, कतार के मानक संचालन का उपयोग करके एक कतार के पहले k तत्वों को उल्टा करता है।

उदाहरण  

इनपुट:
कतार = 10 -> 15 -> 31 -> 17 -> 12 -> 19 -> 2
के = एक्सएनएनएक्स
आउटपुट:
कतार = 31 -> 15 -> 10 -> 17 -> 12 -> 19 -> 2

इनपुट:
कतार = 12 -> 14 -> 16 -> 7 -> 9
के = एक्सएनएनएक्स
आउटपुट:
कतार = 14 -> 12 -> 16 -> 7 -> 9

कतार के पहले K तत्वों को उलटने के लिए एल्गोरिथ्म  

कतार के पहले k तत्वों को उलटने के लिए हम एक स्टैक का उपयोग कर सकते हैं।

  1. कतार के पहले k तत्वों को निकालें और उन्हें एक स्टैक में धकेलें।
  2. स्टैक के सभी तत्वों को पॉप करें और उन्हें कतार के अंत तक धक्का दें।
  3. पॉप-आउट (n - k) तत्वों को कतार के सामने से और उन्हें कतार के अंत तक धकेलें, जहाँ n कतार में तत्वों की कुल संख्या है।
  4. सबसे पहले, कतार के तत्वों को उलट दिया जाता है, कतार के तत्वों को प्रिंट किया जाता है।

एक कतार के पहले कश्मीर तत्वों को उलटने के लिए स्पष्टीकरण  

एक उदाहरण पर विचार करें,
कतार = 10 -> 7 -> 4 -> 3
के = एक्सएनएनएक्स

चरण 1

कतार के पहले k तत्वों को निकालें और उन्हें एक स्टैक में धकेलें।
कतार = 10 -> 7 -> 4 -> 3 और ढेर = अशक्त
चलना 1
कतार = 7 -> 4 -> 3 और स्टैक = 10
चलना 2
कतार = 4 -> 3 और स्टैक = 7 -> 10

यह भी देखें
अच्छे जोड़े Leetcode Solution की संख्या

चरण 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

C ++ कोड

#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

एक कतार के पहले कश्मीर तत्वों को उलटने के लिए जटिलता विश्लेषण  

समय जटिलता = ओ (एन + के)
अंतरिक्ष जटिलता = ठीक) 
जहां n कतार में तत्वों की संख्या है।

यह भी देखें
जाँच करें कि क्या एक कतार को एक स्टैक का उपयोग करके दूसरी कतार में क्रमबद्ध किया जा सकता है

संदर्भ