Kolejka za pomocą stosów

Poziom trudności Łatwo
Często zadawane pytania Accolita Adobe Amazonka DE Shaw Flipkart Goldman Sachs InfoEdge InMobi MakeMyTrip MAQ Microsoft Morgan Stanley wyrocznia Laboratoria Walmart
kolejka Stosodwiedzajacy 79

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 kolejce za pomocą pliku stos problem, musimy zaimplementować następujące funkcje kolejki przy użyciu standardowych funkcji struktury danych stosu,

  1. Enqueue: Dodaj element na końcu kolejki
  2. Dequeue: Usuń element z początku kolejki

Przykład

Wejście:
Dodaj do kolejki (5)
Dodaj do kolejki (11)
Dodaj do kolejki (39)
Dequeue () // Zwraca 5
Dodaj do kolejki (12)
Dequeue () // Zwraca 11
Dequeue () // Zwraca 39
Wyjście:
5
11
39

Algorytm

Kolejkę można zaimplementować przy użyciu dwóch stosów. Istnieją dwa sposoby zaimplementowania kolejki przy użyciu stosów, po pierwsze, powodując, że operacja kolejkowania jest kosztowna, a po drugie, powodując, że operacja usuwania z kolejki jest kosztowna.

Metoda 1 (kosztowna operacja dodawania do kolejki) dla kolejki przy użyciu stosów

Utwórz dwa stosy st1 i st2. Wizualizuj kolejka w st1 wierzchołek st1 znajduje się przed kolejką, a poruszanie się w dół w st1 jest podobne do poruszania się do przodu w kolejce.

Umieść w kolejce (x)

Przesunięcie x na koniec kolejki jest tym samym, co wypchnięcie x na dół stosu st1.

  1. Usuń wszystkie elementy z st1 i wepchnij je do st2.
  2. Wciśnij x do st2.
  3. Usuń wszystkie elementy z st2 i wsuń je z powrotem do st1.

Złożoność czasowa = Na

Kolejka za pomocą stosówszpilka

Usuń z kolejki ()

Usunięcie elementu z przodu kolejki jest podobne do usunięcia szczytu stosu st1. Więc jeśli st1 nie jest puste, zdejmij górę st1 i wróć.

Złożoność czasowa = O (1)

Ogólna złożoność przestrzenna metody 1 = Na)

Kod JAVA dla kolejki używającej stosów

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

Kod C ++

#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

Metoda 2 (kosztowna operacja usuwania z kolejki) dla kolejki przy użyciu stosów

Utwórz dwa stosy st1 i st2. Wizualizuj kolejkę w st1, górna część st1 reprezentuje koniec kolejki, poruszanie się w górę w st1 jest podobne do poruszania się do przodu w kolejce.

Umieść w kolejce (x)

Wciśnięcie x na koniec kolejki jest podobne do wypchnięcia x na początek stack_st1. Więc popchnij x na górę st1.

Złożoność czasowa = O (1)

Usuń z kolejki ()

Usunięcie elementu z początku kolejki jest podobne do usunięcia elementu z dołu pliku stack_st1. Tak więc, jeśli st1 nie jest puste,

  1. Usuń wszystkie elementy z st1 i wepchnij je do st2.
  2. Zdejmij górę st2 i umieść ją w zmiennej górze.
  3. Usuń wszystkie elementy z st2 i wsuń je z powrotem do st1.
  4. Powrót do góry

Złożoność czasowa = Na)

Kolejka za pomocą stosówszpilka

Ogólna złożoność przestrzenna metody 2 = Na)

Kod JAVA

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

Kod C ++

#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

Referencja 1     odniesienie 2

Wywiady dotyczące projektowania systemu pękania
Translate »