Jaki jest sens implementowania stosu przy użyciu dwóch kolejek?

Mam następujące pytanie o pracę domową:

Zaimplementuj metody stosu push (x) i pop () przy użyciu dwóch kolejek.

Wydaje mi się to dziwne, ponieważ:

• Stos to kolejka (LIFO)
• Nie rozumiem, dlaczego potrzebujesz dwóch kolejek, aby go zaimplementować

Szukałem w okolicy:

• GeeksForGeeks
• Przepełnienie stosu

i znalazłem kilka rozwiązań. Właśnie z tym skończyłem:

public class Stack<T> {
    LinkedList<T> q1 = new LinkedList<T>();
    LinkedList<T> q2 = new LinkedList<T>();

    public void push(T t) {
        q1.addFirst(t);
    }

    public T pop() {
        if (q1.isEmpty()) {
            throw new RuntimeException(
                "Can't pop from an empty stack!");
        }

        while(q1.size() > 1) {
            q2.addFirst( q1.removeLast() );
        }

        T popped = q1.pop();

        LinkedList<T> tempQ = q1;
        q1 = q2;
        q2 = tempQ;

        return popped;
    }
}

Ale nie rozumiem, na czym polega przewaga nad pojedynczą kolejką; wersja z dwiema kolejkami wydaje się bezcelowo skomplikowana.

Powiedzmy, że wybraliśmy, aby pushy były bardziej wydajne z 2 (jak to zrobiłem powyżej), pushpozostałyby takie same i poppo prostu wymagałyby iteracji do ostatniego elementu i zwrócenia go. W obu przypadkach pushbyłoby O(1)i popbyłoby O(n); ale wersja z pojedynczą kolejką byłaby znacznie prostsza. Powinien wymagać tylko pojedynczej pętli for.

Czy coś brakuje? Każdy wgląd tutaj będzie mile widziany.

Nie ma żadnej korzyści: jest to ćwiczenie czysto akademickie.

Bardzo dawno temu, kiedy byłem studentem pierwszego roku na studiach miałem podobną ćwiczenia ¹ . Celem było nauczenie studentów, jak korzystać z programowania obiektowego do implementacji algorytmów zamiast pisać rozwiązania iteracyjne za pomocą forpętli z licznikami pętli. Zamiast tego łącz i wykorzystuj istniejące struktury danych, aby osiągnąć swoje cele.

Nigdy nie użyjesz tego kodu w Real World ^TM . To, co musisz wziąć z tego ćwiczenia, to jak „myśleć nieszablonowo” i ponownie użyć kodu.

Pamiętaj, że powinieneś używać interfejsu java.util.Queue w kodzie zamiast bezpośredniego wdrożenia:

Queue<T> q1 = new LinkedList<T>();
Queue<T> q2 = new LinkedList<T>();

Dzięki temu możesz w Queuerazie potrzeby użyć innych implementacji, a także ukryć ^{2 dostępne} metody, LinkedListktóre mogą ominąć ducha Queueinterfejsu. Obejmuje to get(int)i pop()(podczas kompilacji kodu występuje błąd logiczny, biorąc pod uwagę ograniczenia twojego przypisania. Zadeklarowanie zmiennych jako Queuezamiast LinkedListujawnia je). Literatura pokrewna: Zrozumienie „programowania do interfejsu” i dlaczego interfejsy są przydatne?

^{1 _{Nadal pamiętam: ćwiczenie polegało na odwróceniu stosu przy użyciu tylko metod interfejsu stosu i bez metod narzędziowych java.util.Collectionslub innych klas narzędzi „tylko statycznych”. Prawidłowe rozwiązanie polega na użyciu innych struktur danych jako tymczasowych obiektów przechowujących: musisz znać różne struktury danych, ich właściwości i sposób ich łączenia. Zakłopotał większość mojej klasy CS101, która nigdy wcześniej nie programowała.}}

^{2 _{Metody są nadal dostępne, ale nie można uzyskać do nich dostępu bez rzutów typu i refleksji. Dlatego nie jest łatwo korzystać z tych metod niekolejkowych.}}

Nie ma przewagi. Prawidłowo zdałeś sobie sprawę, że użycie kolejek do wdrożenia stosu prowadzi do okropnej złożoności czasu. Żaden (kompetentny) programista nigdy nie zrobiłby czegoś takiego w „prawdziwym życiu”.

Ale to możliwe. Możesz użyć jednej abstrakcji, aby zaimplementować inną, i odwrotnie. Stos można zaimplementować w postaci dwóch kolejek, a także można zaimplementować kolejkę w postaci dwóch stosów. Zaletą tego ćwiczenia jest:

• zbierasz stosy
• podsumowujesz kolejki
• przyzwyczajasz się do myślenia algorytmicznego
• uczysz się algorytmów związanych ze stosem
• możesz pomyśleć o kompromisach w algorytmach
• realizując równoważność kolejek i stosów, łączysz różne tematy swojego kursu
• zdobywasz praktyczne doświadczenie programistyczne

W rzeczywistości jest to świetne ćwiczenie. Powinienem to zrobić teraz :)

Zdecydowanie prawdziwym celem jest utworzenie kolejki z dwóch stosów. Jeśli używasz niezmiennych struktur danych z języka funkcjonalnego, możesz wcisnąć do stosu elementów, które można przesuwać, i wyciągnąć z listy elementów, które można wstawiać. Przedmioty z możliwością otwierania są tworzone, gdy wszystkie przedmioty zostały wysunięte, a nowy stos z możliwością wstawiania jest odwrotnością stosu, w którym nowy stos może być pusty. Jest wydajny.

Co do stosu złożonego z dwóch kolejek? Może to mieć sens w kontekście, w którym dostępnych jest kilka dużych i szybkich kolejek. Jest to zdecydowanie bezużyteczne jako tego rodzaju ćwiczenie Java. Ale może to mieć sens, jeśli są to kanały lub kolejki wiadomości. (tj .: N wiadomości w kolejce, z operacją O (1), aby przenieść (N-1) elementy z przodu do nowej kolejki.)

Ćwiczenie jest niepotrzebnie zaprojektowane z praktycznego punktu widzenia. Chodzi o to, aby zmusić cię do użycia interfejsu kolejki w sprytny sposób do wdrożenia stosu. Na przykład rozwiązanie „Jedna kolejka” wymaga iteracji w kolejce, aby uzyskać ostatnią wartość wejściową dla operacji „pop” stosu. Jednak struktura danych w kolejce nie pozwala na iterację po wartościach, masz ograniczony dostęp do nich w trybie „pierwsze weszło, pierwsze wyszło” (FIFO).

Jak już zauważyli inni: nie ma przewagi w świecie rzeczywistym.

W każdym razie jedna odpowiedź na drugą część pytania, dlaczego po prostu nie użyć jednej kolejki, jest poza Javą.

W Javie nawet Queueinterfejs ma size()metodę, a wszystkie standardowe implementacje tej metody to O (1).

Niekoniecznie jest to prawdą w przypadku naiwnej / kanonicznej listy połączonej, którą zaimplementowałby programista C / C ++, który utrzymywałby wskaźniki do pierwszego i ostatniego elementu, a każdy element był wskaźnikiem do następnego elementu.

W takim przypadku size()jest to O (n) i należy tego unikać w pętlach. Lub implementacja jest nieprzejrzysta i zapewnia jedynie absolutne minimum add()i remove().

Przy takiej implementacji musisz najpierw policzyć liczbę elementów, przenosząc je do drugiej kolejki, przenosząc n-1elementy z powrotem do pierwszej kolejki i zwracając pozostały element.

To powiedziawszy, prawdopodobnie nie stworzyłoby czegoś takiego, jeśli mieszkasz w krainie Java.

To prawda, że ​​trudno wyobrazić sobie zastosowanie takiej implementacji. Ale najważniejsze jest udowodnienie, że da się to zrobić .

Pod względem faktycznego wykorzystania tych rzeczy mogę jednak pomyśleć o dwóch. Jednym z zastosowań jest wdrażanie systemów w ograniczonych środowiskach, które nie zostały do ​​tego zaprojektowane : na przykład bloki z czerwonego kamienia Minecraft okazują się reprezentować kompletny system Turinga, którego ludzie używali do wdrażania obwodów logicznych, a nawet całych procesorów. W pierwszych dniach gier opartych na skryptach zaimplementowano również wiele pierwszych botów do gier.

Ale możesz również zastosować tę zasadę w odwrotnej kolejności, upewniając się, że coś nie jest możliwe w systemie, gdy nie chcesz . Może się to zdarzyć w kontekście bezpieczeństwa: na przykład potężne systemy konfiguracyjne mogą być atutem, ale nadal istnieją poziomy mocy, których raczej nie możesz dać użytkownikom. Ogranicza to to, na co możesz pozwolić językowi konfiguracyjnemu, aby nie został on zniszczony przez atakującego, ale w tym przypadku właśnie tego chcesz.