Uma pilha, duas filas

59

fundo

Vários anos atrás, quando eu era graduado, recebíamos uma lição de casa sobre análise amortizada. Não consegui resolver um dos problemas. Eu havia perguntado isso em teoria , mas nenhum resultado satisfatório foi encontrado. Lembro que o curso da TA insistiu em algo que ele não podia provar e disse que esqueceu a prova, e ... [você sabe o que].

Hoje me lembrei do problema. Eu ainda estava ansioso para saber, então aqui está ...

A questão

É possível implementar uma pilha usando duas filas , para que as operações PUSH e POP sejam executadas no tempo amortizado O (1) ? Se sim, você poderia me dizer como?

Nota: A situação é bastante fácil se queremos implementar uma fila com duas pilhas (com as operações correspondentes ENQUEUE & DEQUEUE ). Por favor, observe a diferença.

PS: O problema acima não é o dever de casa em si. A lição de casa não exigia limites inferiores; apenas uma implementação e a análise do tempo de execução.

MS Dousti
fonte
2
Eu acho que você só pode usar uma quantidade limitada de espaço além das duas filas (O (1) ou O (log n)). Parece-me impossível, porque não temos como reverter a ordem de um longo fluxo de entrada. Mas é claro que isso não é prova, a menos que possa ser transformado em uma reivindicação rigorosa….
Tsuyoshi Ito
@ Tsuyoshi: Você está certo sobre a suposição de espaço limitado. E sim, foi o que eu disse a esse TA (teimoso), mas ele recusou :(
MS Dousti 30/10/10
2
@ Tsuyoshi: Eu não acho que você precise assumir um limite no espaço em geral, você só precisa assumir que você não tem permissão para armazenar os objetos empurrados e lançados da pilha em qualquer lugar que não seja as duas filas (e provavelmente um número constante de variáveis).
Kaveh
@SadeqDousti Na minha opinião, a única maneira de isso ser possível é se você usasse uma implementação de lista vinculada de uma fila e usasse alguns ponteiros para sempre apontar para o topo da "pilha"
Charles Addis
2
Parece que o AT poderia realmente querer dizer "Implementar uma fila usando duas pilhas", o que é realmente possível precisamente em "O (1) tempo amortizado".
Thomas Ahle

Respostas:

45

Não tenho uma resposta real, mas aqui estão algumas evidências de que o problema está aberto:

  • Não é mencionado em Ming Li, Luc Longpré e Paul MB Vitányi, "O poder da fila", Structures 1986, que considera várias outras simulações intimamente relacionadas

  • Não é mencionado em Martin Hühne, "Sobre o poder de várias filas", Theor. Comp. Sci. 1993, um artigo subsequente.

  • Não é mencionado em Holger Petersen, "Stacks versus Deques", COCOON 2001.

  • Burton Rosenberg, "Rápido reconhecimento não determinístico de linguagens sem contexto usando duas filas", Inform. Proc. Lett. 1998, fornece um algoritmo O (n log n) de duas filas para reconhecer qualquer CFL usando duas filas. Mas um autômato de empuxo não determinístico pode reconhecer CFLs em tempo linear. Portanto, se houvesse uma simulação de uma pilha com duas filas mais rápidas que O (log n) por operação, Rosenberg e seus árbitros deveriam saber disso.

David Eppstein
fonte
4
+1 para excelentes referências. No entanto, existem alguns aspectos técnicos: alguns dos documentos, como o primeiro, não consideram o problema de simular uma pilha usando duas filas (o que posso dizer do resumo). Outros consideram a análise do pior caso, não o custo amortizado.
MS Dousti 30/10/10
13

A resposta abaixo é 'trapaça', pois, embora não use espaço entre operações, as próprias operações podem usar mais que espaço. Veja em outro lugar neste tópico uma resposta que não tenha esse problema.O(1)

Embora eu não tenha uma resposta para sua pergunta exata, encontrei um algoritmo que funciona em tempo em vez deO(n). Eu acredito que isso é apertado, embora eu não tenha uma prova. De qualquer forma, o algoritmo mostra que tentar provar um limite inferior deO(n)é inútil, portanto, pode ajudar a responder sua pergunta.O(n)O(n)O(n)

Apresento dois algoritmos, o primeiro sendo um algoritmo simples com um tempo de execução de para Pop e o segundo com um O ( O(n)tempo de execução do Pop. Descrevo o primeiro, principalmente por sua simplicidade, para facilitar o entendimento do segundo.O(n)

Para dar mais detalhes: o primeiro não usa espaço adicional, possui um Push pior caso (e amortizado) e O ( n ) O pior caso (e amortizado), mas o comportamento do pior caso nem sempre é acionado. Como não usa espaço adicional além das duas filas, é um pouco "melhor" do que a solução oferecida por Ross Snider.O(1)O(n)

O segundo usa um único campo inteiro (portanto, espaço extra), possui O ( 1 ) pior caso (e amortizado) Push e O ( O(1)O(1)Pop amortizado. Portanto, o tempo de execução é significativamente melhor do que o da abordagem "simples", mas usa algum espaço extra.O(n)

O primeiro algoritmo

Temos duas filas: fila de e fila s e c o n d . f i r s t será a 'fila push', enquanto s e c o n d será a fila já na 'ordem pilha'.firstsecondfirstsecond

  • O envio é feito simplesmente enfileirando o parâmetro em .first
  • O popping é feito da seguinte maneira. Se está vazio, que simplesmente Desenfileiramento s e c o n d e devolve o resultado. Caso contrário, se inverter f i r s t , acrescentar tudo de s e c o n d a f i r s t e de troca de f i r s t e s e c o n d . Em seguida, desenfileiramos s e c ofirstsecondfEurstsecondfEurstfEurstsecond e devolver o resultado do retirar da fila.second

Código C # para o primeiro algoritmo

Isso pode ser bem legível, mesmo que você nunca tenha visto C # antes. Se você não souber o que são genéricos, substitua todas as instâncias de 'T' por 'string' em sua mente, por uma pilha de strings.

public class Stack<T> {
    private Queue<T> first = new Queue<T>();
    private Queue<T> second = new Queue<T>();
    public void Push(T value) {
        first.Enqueue(value);
    }
    public T Pop() {
        if (first.Count == 0) {
            if (second.Count > 0)
                return second.Dequeue();
            else
                throw new InvalidOperationException("Empty stack.");
        } else {
            int nrOfItemsInFirst = first.Count;
            T[] reverser = new T[nrOfItemsInFirst];

            // Reverse first
            for (int i = 0; i < nrOfItemsInFirst; i++)
                reverser[i] = first.Dequeue();    
            for (int i = nrOfItemsInFirst - 1; i >= 0; i--)
                first.Enqueue(reverser[i]);

            // Append second to first
            while (second.Count > 0)
                first.Enqueue(second.Dequeue());

            // Swap first and second
            Queue<T> temp = first; first = second; second = temp;

            return second.Dequeue();
        }
    }
}

Análise

Obviamente, o Push funciona no tempo . Pop pode tocar tudo dentro f i r s t e s e c o n d uma quantidade constante de tempos, de modo que temos S ( n ) no pior dos casos. O algoritmo exibe esse comportamento (por exemplo) se alguém colocar n elementos na pilha e executar repetidamente uma única operação Push e uma única operação Pop em sucessão.O(1)fEurstsecondO(n)n

O segundo algoritmo

Temos duas filas: fila de e fila s e c o n d . f i r s t será a 'fila push', enquanto s e c o n d será a fila já na 'ordem pilha'.fEurstsecondfEurstsecond

Esta é uma versão adaptada do primeiro algoritmo, em que não faça imediatamente 'baralhamento' o conteúdo de a s e c o n d . Em vez disso, se f i r s t contém um número suficientemente pequeno de elementos em comparação com s e c o n d (ou seja, a raiz quadrada do número de elementos em s e c o n d ), apenas reorganizamos f i r s t em ordem de pilha e não a mescle comfEurstsecondfEurstsecondsecondfEurst .second

  • A pressão ainda é feita simplesmente enfileirando o parâmetro em .fEurst
  • O popping é feito da seguinte maneira. Se está vazio, que simplesmente Desenfileiramento s e c o n d e devolve o resultado. Caso contrário, reorganizamos o conteúdo de f i r s t para que eles estejam na ordem das pilhas. Se | f i r s t | < fEurstsecondfEurstsimplesmente desenfileiramosfirsteretornamos o resultado. Caso contrário, anexamossecondemfirst, permutafirstesecond, Desenfileiramentoseconde devolve o resultado.|fEurst|<|second|fEurstsecondfEurstfEurstsecondsecond

Código C # para o primeiro algoritmo

Isso pode ser bem legível, mesmo que você nunca tenha visto C # antes. Se você não souber o que são genéricos, substitua todas as instâncias de 'T' por 'string' em sua mente, por uma pilha de strings.

public class Stack<T> {
    private Queue<T> first = new Queue<T>();
    private Queue<T> second = new Queue<T>();
    int unsortedPart = 0;
    public void Push(T value) {
        unsortedPart++;
        first.Enqueue(value);
    }
    public T Pop() {
        if (first.Count == 0) {
            if (second.Count > 0)
                return second.Dequeue();
            else
                throw new InvalidOperationException("Empty stack.");
        } else {
            int nrOfItemsInFirst = first.Count;
            T[] reverser = new T[nrOfItemsInFirst];

            for (int i = nrOfItemsInFirst - unsortedPart - 1; i >= 0; i--)
                reverser[i] = first.Dequeue();

            for (int i = nrOfItemsInFirst - unsortedPart; i < nrOfItemsInFirst; i++)
                reverser[i] = first.Dequeue();

            for (int i = nrOfItemsInFirst - 1; i >= 0; i--)
                first.Enqueue(reverser[i]);

            unsortedPart = 0;
            if (first.Count * first.Count < second.Count)
                return first.Dequeue();
            else {
                while (second.Count > 0)
                    first.Enqueue(second.Dequeue());

                Queue<T> temp = first; first = second; second = temp;

                return second.Dequeue();
            }
        }
    }
}

Análise

Obviamente, o Push funciona no tempo .O(1)

O pop trabalha em tempo amortizado. Existem dois casos: se| first| <O(n), então embaralhamosfirstna ordem da pilha emO(|first|)=O(|first|<|second|firsttempo. Se| first| O(|first|)=O(n), então devemos ter pelo menos|first||second| pede Push. Portanto, podemos apenas atingir esse caso a cadan chama para Push e Pop. O tempo de execução real para este caso éO(n), portanto, o tempo amortizado éO( n)nO(n).O(nn)=O(n)

Nota final

É possível eliminar a variável extra ao custo de tornar Pop um operação, por ter Pop reorganizarfirstem cada chamada, em vez de ter push fazer todo o trabalho.O(n)first

Alex ten Brink
fonte
Eu editei os primeiros parágrafos para que minha resposta seja formulada como uma resposta real à pergunta.
Alex ten Brink
6
Você está usando uma matriz (reversor) para reverter! Eu não acho que você tem permissão para fazer isso.
Kaveh
É verdade que uso espaço extra durante a execução dos métodos, mas achei que isso seria permitido: se você deseja implementar uma fila usando duas pilhas de maneira direta, precisa reverter uma das pilhas em um ponto e até o ponto Eu sei que você precisa de espaço extra para fazer isso; portanto, como essa pergunta é semelhante, imaginei que seria permitido o uso de espaço extra durante a execução de um método, desde que você não use espaço adicional entre as chamadas de método.
Alex10 Brink
6
"se você deseja implementar uma fila usando duas pilhas da maneira direta, você deve reverter uma das pilhas em um ponto e, tanto quanto eu sei, precisa de espaço extra para fazer isso" --- Você não precisa. Existe uma maneira de obter o custo amortizado do enfileiramento em 3 e o custo amortizado do desenfileiramento em 1 (ou seja, ambos O (1)) com uma célula de memória e duas pilhas. A parte difícil é realmente a prova, não o design do algoritmo.
Aaron Sterling
Depois de pensar um pouco mais, percebo que estou realmente trapaceando e meu comentário anterior está realmente errado. Eu encontrei uma maneira de corrigi-lo: pensei em dois algoritmos com os mesmos tempos de execução que os dois acima (embora Push agora seja uma operação demorada e Pop agora seja executado em tempo constante) sem usar espaço extra. Vou postar uma nova resposta depois de escrever tudo.
Alex10 Brink
12

Após alguns comentários na minha resposta anterior, ficou claro para mim que eu estava mais ou menos trapaceando: usei espaço extra ( espaço extra no segundo algoritmo) durante a execução do meu método Pop.O(n)

O algoritmo a seguir não usa espaço adicional entre os métodos e apenas espaço extra durante a execução de Push e Pop. Push tem um O ( O(1)amortizado tempo de execução e Pop tem umó(1)pior caso (e amortizado) tempo de funcionamento.O(n)O(1)

Nota aos moderadores: não tenho certeza se minha decisão de fazer uma resposta separada é a correta. Eu pensei que não deveria excluir minha resposta original, pois ainda pode ter alguma relevância para a pergunta.

O algoritmo

Temos duas filas: fila de e fila s e c o n d . f i r s t será a 'cache', enquanto s e c o n d será o nosso principal 'depósito'. As duas filas sempre estarão em 'ordem de pilha'. f i r s t conterá os elementos na parte superior da pilha e s e c o n d irá conter os elementos na parte inferior da pilha. O tamanho de f i rfirstsecondfirstsecondfirstsecond sempre será, no máximo, a raiz quadrada de s e c o n d .firstsecond

  • O push é feito 'inserindo' o parâmetro no início da fila da seguinte maneira: enfileiramos o parâmetro em e, em seguida, desenfileiramos e re-enfileiramos todos os outros elementos em f i r s t . Dessa forma, o parâmetro termina no início de f i r s t .firstfirstfirst
  • Se torna-se maior do que a raiz quadrada de s e c o n d , nós enfileirar todos os elementos de s e c o n d em f i r s t uma por uma e depois trocar f i r s t e s e c o n d . Dessa forma, os elementos de f i r s t (o topo da pilha) acabam no topo da s efirstsecondsecondfirstfirstsecondfirst .second
  • Pop é feito por dequeueing e devolver o resultado se f i r s t não está vazia, e de outra forma por dequeueing s e c o n d e devolver o resultado.firstfirstsecond

Código C # para o primeiro algoritmo

Esse código deve ser bem legível, mesmo se você nunca viu C # antes. Se você não souber o que são genéricos, substitua todas as instâncias de 'T' por 'string' em sua mente, por uma pilha de strings.

public class Stack<T> {
    private Queue<T> first = new Queue<T>();
    private Queue<T> second = new Queue<T>();
    public void Push(T value) {
        // I'll explain what's happening in these comments. Assume we pushed
        // integers onto the stack in increasing order: ie, we pushed 1 first,
        // then 2, then 3 and so on.

        // Suppose our queues look like this:
        // first: in 5 6 out
        // second: in 1 2 3 4 out
        // Note they are both in stack order and first contains the top of
        // the stack.

        // Suppose value == 7:
        first.Enqueue(value);
        // first: in 7 5 6 out
        // second: in 1 2 3 4 out

        // We restore the stack order in first:
        for (int i = 0; i < first.Count - 1; i++)
            first.Enqueue(first.Dequeue());
        // first.Enqueue(first.Dequeue()); is executed twice for this example, the 
        // following happens:
        // first: in 6 7 5 out
        // second: in 1 2 3 4 out
        // first: in 5 6 7 out
        // second: in 1 2 3 4 out

        // first exeeded its capacity, so we merge first and second.
        if (first.Count * first.Count > second.Count) {
            while (second.Count > 0)
                first.Enqueue(second.Dequeue());
            // first: in 4 5 6 7 out
            // second: in 1 2 3 out
            // first: in 3 4 5 6 7 out
            // second: in 1 2 out
            // first: in 2 3 4 5 6 7 out
            // second: in 1 out
            // first: in 1 2 3 4 5 6 7 out
            // second: in out

            Queue<T> temp = first; first = second; second = temp;
            // first: in out
            // second: in 1 2 3 4 5 6 7 out
        }
    }
    public T Pop() {
        if (first.Count == 0) {
            if (second.Count > 0)
                return second.Dequeue();
            else
                throw new InvalidOperationException("Empty stack.");
        } else
            return first.Dequeue();
    }
}

Análise

Obviamente, o Pop funciona no tempo no pior caso.O(1)

Push trabalha em tempo amortizado. Existem dois casos: se| first| <O(n)então Push levaO(|first|<|second|tempo. Se| first| O(n)então Push levaO(n)tempo, mas após esta operação,firstestará vazio. Vai levarO(|first||second|O(n)firsttempo antes de retomarmos este caso, portanto o tempo amortizado éO( nO(n)tempo.O(nn)=O(n)

Alex ten Brink
fonte
sobre como excluir uma resposta, consulte meta.cstheory.stackexchange.com/q/386/873 .
MS Dousti
Eu não consigo entender a linha first.Enqueue(first.Dequeue()). Você digitou algo errado?
MS Dousti
Obrigado pelo link, atualizei minha resposta original de acordo. Em segundo lugar, adicionei muitos comentários ao meu código descrevendo o que está acontecendo durante a execução do meu algoritmo, espero que isso esclareça qualquer confusão.
Alex10 Brink #
para mim, o algoritmo era mais legível e mais fácil de entender antes da edição.
Kaveh
9

Eu afirmo que temos custo amortizado por operação. O algoritmo de Alex fornece o limite superior. Para provar o limite inferior, dou a pior sequência de movimentos PUSH e POP.Θ(N)

A pior sequência de casos consiste em operações PUSH, seguidas por N PUSH operações eN operações POP, seguidas novamente porN PUSH operações eN operações POP, etc. Ou seja:N

PUSHN(PUSHNPOPN)N

Considere a situação após as operações iniciais de PUSH. Não importa como o algoritmo funcione, pelo menos uma das filas deve ter pelo menos N / 2 entradas.NN/2

Agora considere a tarefa de lidar com o (primeiro conjunto de) Operações PUSH e POP. Qualquer tática algorítmica de qualquer natureza deve se enquadrar em um dos dois casos:N

No primeiro caso, o algoritmo usará as duas filas. A maior dessas filas possui pelo menos entradas, portanto, devemos incorrer em um custo de pelo menos operações de fila N / 2 para recuperar eventualmente até mesmo um único elemento que ENQUADRAMOS e, posteriormente, DESIGAMOS desta fila maior.N/2N/2

No segundo caso, o algoritmo não usa as duas filas. Isso reduz o problema de simular uma pilha com uma única fila. Mesmo que essa fila esteja inicialmente vazia, não podemos fazer melhor do que usá-la como uma lista circular com acesso seqüencial, e parece claro que devemos usar pelo menos Operações de fila N /2em média para cada um dos2N/2 operações de pilha.2N

Nos dois casos, é necessário pelo menos (operações em fila) para lidar com 2 N/2 operações de pilha. Porque podemos repetir esse processo2N vezes, precisamosNNtempo para processar3operações de pilhaNno total, dando um limite inferior deΩ(NN/23Ntempo amortizado por operação.Ω(N)

Shaun Harker
fonte
NN
nQ1N/2Q22nn4:1+2++n+n2n
Aparentemente, a resposta de Pedro contradiz esse limite inferior?
Joe
PUSHNPOPNO(N)
O(N) operações finalmente o recuperem.
Shaun Harker
6

O(lgn)pvocêshpoppopO(lgn)pop é solicitado e a fila de saída está vazia, você executa uma sequência de embaralhamento perfeito para reverter a fila de entrada e armazená-la na fila de saída.

O(1)

Até onde eu sei, essa é uma ideia nova ...

Peter Boothe
fonte
Argh! Eu deveria ter procurado uma pergunta atualizada ou relacionada. Os artigos aos quais você vinculou em sua resposta anterior apresentavam uma relação entre k stacks e k + 1 stacks. Esse truque acaba colocando o poder das filas k entre pilhas kek + 1? Nesse caso, é uma espécie de nota lateral. De qualquer forma, obrigado por me vincular à sua resposta, para não perder muito tempo escrevendo isso para outro local.
precisa
1

Sem usar espaço extra, talvez usando uma fila priorizada e forçando cada novo push a dar uma prioridade maior que a anterior? Ainda não seria O (1).

Alfa
fonte
0

Não consigo que as filas implementem uma pilha em tempo constante amortizado. No entanto, posso pensar em uma maneira de obter duas filas para implementar uma pilha no pior dos casos, no tempo linear.

  • UMAB .
  • Cada vez que houver uma operação push, vire o bit e insira o elemento na fila que o bit agora demarca. Coloque tudo da outra fila e empurre-o para a fila atual.
  • Uma operação pop decola a frente da fila atual e não toca no bit de estado externo.

Obviamente, podemos adicionar outro estado externo que nos diz se a última operação foi um push ou um pop. Podemos atrasar a movimentação de tudo de uma fila para outra até obtermos duas operações de envio consecutivas. Isso também torna a operação pop um pouco mais complicada. Isso nos dá O (1) complexidade amortizada para a operação pop. Infelizmente, o push permanece linear.

Tudo isso funciona porque cada vez que uma operação de envio é realizada, o novo elemento é colocado no início de uma fila vazia e a fila completa é adicionada ao final da mesma, revertendo efetivamente os elementos.

Se você deseja obter operações de tempo constante amortizadas, provavelmente precisará fazer algo mais inteligente.

Ross Snider
fonte
4
Certamente, posso usar uma única fila com a mesma complexidade de pior caso e sem a complicação, essencialmente tratando a fila como uma lista circular com um elemento de fila adicional representando o topo da pilha.
Dave Clarke
Parece que você pode! No entanto, parece que mais de uma fila clássica é necessária para simular uma pilha dessa maneira.
Ross Snider
0

Existe uma solução trivial, se sua fila permitir o carregamento antecipado, que exige apenas uma fila (ou, mais especificamente, deque). Talvez esse seja o tipo de fila que o curso TA na pergunta original tinha em mente?

Sem permitir o carregamento frontal, aqui está outra solução:

Esse algoritmo requer duas filas e dois ponteiros, que serão denominados Q1, Q2, primário e secundário, respectivamente. Após a inicialização, Q1 e Q2 estão vazios, pontos primários para Q1 e pontos secundários para Q2.

A operação PUSH é trivial, consiste apenas em:

*primary.enqueue(value);

A operação POP é um pouco mais envolvida; requer colocar em spool tudo, exceto o último item da fila principal, na fila secundária, trocar os ponteiros e retornar o último item restante da fila original:

while(*primary.size() > 1)
{
    *secondary.enqueue(*primary.dequeue());
}

swap(primary, secondary);
return(*secondary.dequeue());

Nenhuma verificação de limites é feita e não é O (1).

Enquanto digito isso, vejo que isso pode ser feito com uma única fila usando um loop for no lugar de um loop while, como Alex fez. De qualquer forma, a operação PUSH é O (1) e a operação POP se torna O (n).


Aqui está outra solução usando duas filas e um ponteiro, chamados Q1, Q2 e queue_p, respectivamente:

Na inicialização, Q1 e Q2 estão vazios e queue_p aponta para Q1.

Novamente, a operação PUSH é trivial, mas requer uma etapa adicional de apontar queue_p para a outra fila:

*queue_p.enqueue(value);
queue_p = (queue_p == &Q1) ? &Q2 : &Q1;

A operação da operação POP é semelhante a antes, mas agora há n / 2 itens que precisam ser rotacionados pela fila:

queue_p = (queue_p == &Q1) ? &Q2 : &Q1;
for(i=0, i<(*queue_p.size()-1, i++)
{
    *queue_p.enqueue(*queue_p.dequeue());
}
return(*queue_p.dequeue());

A operação PUSH ainda é O (1), mas agora a operação POP é O (n / 2).

Pessoalmente, para esse problema, prefiro a ideia de implementar uma fila única (deque) dupla e chamá-la de pilha quando quisermos.

oosterwal
fonte
Seu segundo algoritmo é útil para entender o mais envolvido de Alex.
Hengxin
0

kΘ(n1/k)

k
n
O(1)

EuΘ(nEu/k)Θ(nEu/k)O(1)i+1O(n1/k)i1Θ(n1/k)

mmΩ(mn1/k)o(n1/k)Ω(n1/k)o(n2/k)ko(n)

Θ(logn)

Dmytro Taranovsky
fonte
-3

Uma pilha pode ser implementada usando duas filas, usando a segunda fila como referência. Quando os itens são empurrados para a pilha, eles são adicionados ao final da fila. Cada vez que um item é populado, os elementos n-1 da primeira fila devem ser movidos para o segundo, enquanto o item restante é retornado. classe pública QueueStack implementa ts IStack {private IQueue q1 = new Queue (); private IQueue q2 = nova Fila (); push de vazio público (E e) {q1.enqueue (e) // O (1)} público E pop (E e) {while (1 <q1.size ()) // O (n) {q2.enqueue ( q1.dequeue ()); } sw apQueues (); retornar q2.dequeue (); } pivate void swapQueues () {IQueue Q = q2; q2 = q1; q1 = Q; }}

Pradeepkumar
fonte
2
Você perdeu a parte da pergunta sobre o tempo amortizado O (1)?
David Eppstein