Növbəni geri qaytarmaq

Çətinlik səviyyəsi Asan
Tez-tez soruşulur Akkolit Coursera Çatdırılma Məlumat dəsti Boz Portağal Zoho
Larsen & Toubro Queue QalaqBaxılıb 56

Bir növbə problemini geri qaytararkən bir queue, yaz alqoritm növbəni tərs etmək.

Nümunələr

Input
növbə = 10 -> 8 -> 4 -> 23
Buraxılış
növbə = 23-> 4-> 8-> 10

Input
növbə = 11 -> 98 -> 31 -> 42 -> 73 -> 6
Buraxılış
növbə = 6 -> 73 -> 42 -> 31 -> 98 -> 11

Input
növbə = 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
Buraxılış
növbə = 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1

Bir növbəni geri çevirmək üçün alqoritm

Bir sıra istifadə edilə bilər qalaq,

  1. Bütün elementləri növbədən çıxarın və onları yığına itələyin.
  2. Yığandan bütün elementləri açın və onları sıraya qaytarın.
  3. Növbə hörmət edilir, növbə elementlərini yazdırın.

Növbənin tərsinə salınmasına dair izahat

Bir nümunəyə baxaq,
növbə = 10 -> 8 -> 4 -> 23

Step 1

Elementləri bir-bir növbədən çıxarın və yığına itələyin.
növbə = 10 -> 8 -> 4 -> 23 və yığın = boş
Təkrarlama 1
növbə = 8 -> 4 -> 23 və yığın = 10
Təkrarlama 2
növbə = 4 -> 23 və yığın = 8 -> 10
Təkrarlama 3
növbə = 23 və yığın = 4 -> 8 -> 23
Təkrarlama 4
sıra = boş və yığın = 23-> 4-> 8-> 23

Step 2

Yığandan bütün elementləri çıxarın və onları sıraya qaytarın.
növbə = boş və yığın = 23 -> 4 -> 8 -> 10
Təkrarlama 1
növbə = 23 və yığın = 4 -> 8 -> 10
Təkrarlama 2
növbə = 23 -> 4 və yığın = 8 -> 10
Təkrarlama 3
növbə = 23 -> 4 -> 8 və yığın = 10
Təkrarlama 4
növbə = 23 -> 4 -> 8 -> 10 və yığın = boş

Növbə tərsinə çevrildi. Aydınlaşdırmaq üçün aşağıdakı şəkilə baxın.

Növbəni geri qaytarmaqPin

Bir növbəni geri çevirmək üçün JAVA kodu

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

public class ReversingAQueue {
    private static void reverseQueue(Queue<Integer> queue) {
        int n = queue.size();

        Stack<Integer> stack = new Stack<>();
        // Remove all the elements from queue and push them to stack
        for (int i = 0; i < n; i++) {
            int curr = queue.poll();
            stack.push(curr);
        }

        // Pop out elements from the stack and push them back to queue
        for (int i = 0; i < n; i++) {
            int curr = stack.pop();
            queue.add(curr);
        }

        // Print the reversed 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<>();
        q1.add(10);
        q1.add(8);
        q1.add(4);
        q1.add(23);
        reverseQueue(q1);

        // Example 2
        Queue<Integer> q2 = new LinkedList<>();
        q2.add(11);
        q2.add(98);
        q2.add(31);
        q2.add(42);
        q2.add(73);
        q2.add(6);
        reverseQueue(q2);
    }
}
23 4 8 10 
6 73 42 31 98 11

Bir növbəni geri çevirmək üçün C ++ kodu

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

void reverseQueue(queue<int> &queue) {
    int n = queue.size();
    
    stack<int> st;
    // Remove all the elements from queue and push them to stack
    for (int i = 0; i < n; i++) {
        int curr = queue.front();
        queue.pop();
        st.push(curr);
    }
    
    // Pop out elements from the stack and push them back to queue
    for (int i = 0; i < n; i++) {
        int curr = st.top();
        st.pop();
        queue.push(curr);
    }
    
    // Print the reversed 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(8);
    q1.push(4);
    q1.push(23);
    reverseQueue(q1);

    // Example 2
    queue<int> q2;
    int k2 = 2;
    q2.push(11);
    q2.push(98);
    q2.push(31);
    q2.push(42);
    q2.push(73);
    q2.push(6);
    reverseQueue(q2);
}
23 4 8 10 
6 73 42 31 98 11

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi = O (n)
Kosmik Mürəkkəblik = O (n) 
burada n növbədəki qovşaq sayıdır.

References

Translate »