JS - kolejka 2 stosy

Za pomocą dwóch stosów można łatwo zaimplementować kolejkę, czyli inny typ danych. Zaczynajmy!

Po pierwsze, co to jest stos:

class Stack {
 
    constructor(){  
        this.elements = []; 
    }
    push(element){ 
        this.elements.push(element) 
    }
    pop(){ 
        if(this.elements.length > 0)
            return this.elements.pop();
    }
    isEmpty(){ 
        return this.elements.length === 0;
    }
}

Działanie stosu:

to co wpadło jako pierwsze (push) wyleci jako ostatnie (pop)
to co wpadło jako ostatnie (push) wyleci jako pierwsze (pop)

Z kolejką jest odwrotnie, czyli:

to co stanęło (enqueue) pierwsze w kolejce stoi w niej jako pierwsze do obsłużenia (deque)
to co staje następne w kolejce (enqueue) będzie kolejne do obsłużenia

Znalazłem ciekawy kod w internecie na githubie, w dodatku inny bo nie korzysta z klas ES6+. Kolejka używając 2 stosów:

function Queue() {
    var inStack = [];
    var outStack = [];

    this.enqueue = function(num) {
        inStack.push(num);
    }

    this.dequeue = function() {
        if (outStack.length > 0) {
            return outStack.pop();
        }

        while(inStack.length > 1) {
            outStack.push(inStack.pop());
        }

        return inStack.pop();
    }
}

To działa tak:

enqueue to dodanie do inStack, czyli stos
pierwsze co wleci do instack wyleci z niego ostatnie
dequeue sprawdza czy outstack ma elementy i je wyrzuca
jeżeli outstack nie ma elementów to zrzucamy z instack i dodajemy do outstack
zrzucamy z outstack

Czyli na zdrowy rozum: pierwszy stos będzie zrzucał elementy w kolejności odwrotnej od tej, której chcemy (najpierw przyjmuje ostatniego klienta). Wystarczy przepuścić przez kolejny stos i już kolejność jest odwrotna, taka jakiej oczekujemy od kolejki.

JS – kolejka 2 stosy