Cofanie kolejki

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

W problemie z odwracaniem kolejki daliśmy kolejka, Napisać algorytm odwrócić kolejkę.

Przykłady

Wkład
queue = 10 -> 8 -> 4 -> 23
Wydajność
queue = 23-> 4-> 8-> 10

Wkład
queue = 11 -> 98 -> 31 -> 42 -> 73 -> 6
Wydajność
queue = 6 -> 73 -> 42 -> 31 -> 98 -> 11

Wkład
kolejka = 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9
Wydajność
kolejka = 9 -> 8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1

Algorytm odwracania kolejki

Kolejkę można odwrócić za pomocą pliku stos,

1. Usuń wszystkie elementy z kolejki i umieść je w stosie.
2. Wyjmij wszystkie elementy ze stosu i odłóż je z powrotem do kolejki.
3. Kolejka jest szanowana, drukuj elementy kolejki.

Wyjaśnienie cofania kolejki

Rozważ przykład,
queue = 10 -> 8 -> 4 -> 23

Krok 1

Po kolei usuwaj elementy z kolejki i wsuwaj je do stosu.
queue = 10 -> 8 -> 4 -> 23 i stack = null
iteracja 1
queue = 8 -> 4 -> 23 i stack = 10
iteracja 2
queue = 4 -> 23 i stack = 8 -> 10
iteracja 3
queue = 23 i stack = 4 -> 8 -> 23
iteracja 4
queue = null i stack = 23-> 4-> 8-> 23

Krok 2

Wyjmij wszystkie elementy ze stosu i odłóż je z powrotem do kolejki.
queue = null i stack = 23 -> 4 -> 8 -> 10
iteracja 1
queue = 23 i stack = 4 -> 8 -> 10
iteracja 2
queue = 23 -> 4 i stack = 8 -> 10
iteracja 3
queue = 23 -> 4 -> 8 i stack = 10
iteracja 4
queue = 23 -> 4 -> 8 -> 10 i stack = null

Kolejka jest odwrócona. Zobacz obrazek poniżej dla wyjaśnienia.

szpilka

Kod JAVA do cofania kolejki

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

Kod C ++ do cofania kolejki

#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

Analiza złożoności

Złożoność czasowa = Na)
Złożoność przestrzeni = Na) 
gdzie n to liczba węzłów w kolejce.

Referencje