Queue e Stack são estruturas de dados bastante simples que usamos em nossa codificação diária. Na verdade, eles podem ser considerados as estruturas mais fáceis de manter dados.

Ao longo do artigo, usarei DS para me referir à Estrutura de Dados.

Queue é um DS que funciona no princípio FIFO. Os dados que chegam primeiro podem sair primeiro. Existem muitas maneiras de implementar filas. Somos livres para usar arrays, listas vinculadas e muitos outros. Mas aqui estou prestes a discutir a implementação do Queue usando outro DS chamado Stack.

Agora, todos nós sabemos, Stack é um DS que funciona com base no princípio LIFO. Sempre penso em empilhar livros um acima do outro, então fique à vontade para usar essa analogia se isso ajudar você a visualizar.

Me deparei com esta pergunta no hackerrank, onde eles exigiram que implementássemos a fila usando 2 pilhas. Parece simples, certo? Reserve um momento para pensar como poderíamos conseguir isso.

Você pode ter encontrado algumas soluções porque há muitas maneiras de fazer isso. Então por que você não tenta diretamente?

Pergunta

Agora, para quem tentou e obteve um "erro de tempo limite" e para quem não se preocupou em tentar, deixe-me explicar a solução mais simples e fácil para esse problema.

Primeiro, dê uma olhada em como a pilha pode ser implementada.

Como você pode ver, implementei a pilha usando uma lista. Inicialmente o construtor inicializa uma lista vazia. Enviamos os dados anexando-os ao final da lista. Ao aparecer, se não fornecermos um índice, ele aparecerá no final da lista. Assim, o último elemento a ser inserido é o primeiro a ser retirado.

Agora, de maneira semelhante para a fila, inicializamos duas pilhas diferentes. Um para enfileirar e outro para desenfileirar.

Usamos enqueueStack semelhante ao stack apenas para enviar dados no final da lista. Mas para dequeueStack, sabemos que a função pop da pilha remove o elemento do último, então o que fazemos é; invertemos o enqueueStack e o colocamos em dequeueStack. Assim, o primeiro elemento de enqueueStack se torna o último elemento de dequeueStack, o segundo de enqueueStack se torna o penúltimo de dequeueStack e assim por diante. Então agora, se usarmos a função pop para dequeueStack, ele removerá o primeiro elemento que enviamos, imitando a fila.

Não se preocupe se isso parece confuso agora! Depois de ver o código, você perceberá do que estou falando. Na verdade, dê uma olhada agora mesmo!

Você pode estar se perguntando para que servem essas verificações adicionais. Como verificar se o dequeueStack está vazio ou não. Se não verificarmos inicialmente. Os elementos do enqueueStack por reversão ficarão no dequeueStack e o que acontece é que o elemento Dequeue Stacks que deveria estar no primeiro agora acaba sendo o último. Portanto, primeiro dequeueStack deve ser esvaziado como mostrado no código.

Semelhante a isso, printFront imprime o item que deveria estar no início da fila.

Após esta implementação, lemos a entrada de STDIN e imprimimos a saída em STDOUT.

Nossa entrada é mais ou menos assim:

E a função principal completa é:

Tentei implementar isso da maneira mais fácil possível. Pode haver várias outras e melhores maneiras de implementar isso. Um deles é apresentado aqui!