Como implementar uma fila usando duas pilhas

Escrito por rock owens | Traduzido por ingrid marçal
  • Compartilhar
  • Tweetar
  • Compartilhar
  • Pin
  • E-mail
Como implementar uma fila usando duas pilhas
Implementar uma fila usando duas pilhas é simples (Ablestock.com/AbleStock.com/Getty Images)

A fila é uma estrutura de dados dinâmica a partir da qual você pode acessar os dados em um processo "primeiro a entrar, primeiro a sair". Uma pilha é uma estrutura de dados dinâmica a partir da qual você pode acessar os dados em um processo "último a entrar, primeiro a sair". Se você implementar uma pilha, somente o último item inserido ficará disponível. Se você quiser acessar os dados que estão na base dela (o primeiro item que você colocou), então você estará tratando-a como uma fila. Para fazer isso, você deve implementar uma segunda pilha.

Nível de dificuldade:
Moderadamente desafiante

Outras pessoas estão lendo

O que você precisa?

  • Um editor de texto
  • Um compilador ou interpretador para alguma linguagem de programação

Lista completaMinimizar

Instruções

    Duas pilhas são iguais a uma fila

  1. 1

    Em seu editor de textos, escreva o código para implementar a pilha de acordo com os procedimentos e funções disponíveis na linguagem de programação que você quer usar. Chame essa pilha de Pilha_Entrada. Coloque os dados na Pilha_Entrada (muitas linguagens de programação usam o comando "push" para adicionar dados). Por exemplo, execute o comando "push" em Pilha_Entrada para entrar com os dados na seguinte ordem: "A", "B" e "C". "A" é o primeiro a entrar e está na base da pilha. Se você quiser acessar esse primeiro item, então está tratando os dados como uma fila.

  2. 2

    Escreva o código para implementar uma segunda pilha de acordo com os procedimentos e funções disponíveis na linguagem de programação que você quer usar. Chame-a de Pilha_Saida (muitas linguagens de programação usam o comando "pop" para remover dados de uma pilha).

  3. 3

    Remova cada item da pilha Pilha_Entrada e coloque-os na Pilha_Saida. Em termos gerais, você retira um item de Pilha_Entrada e o coloca em Pilha_Saida. Então você verifica se a Pilha_Entrada está vazia. Se não estiver vazia, retire o próximo item da Pilha_Entrada e coloque-o na Pilha_Saida. Repita até que Pilha_Entrada esteja vazia. Em nosso exemplo, você retira "C" de Pilha_Entrada e o coloca em Pilha_Saida. Verifique se Pilha_Entrada está vazia. Retira "B" de Pilha_Entrada e coloque-o em Pilha_Saida. Verifique se Pilha_Entrada está vazia. Retira "A" de Pilha_Entrada e coloque-o em Pilha_Saida. Verifique se Pilha_Entrada está vazia.

  4. 4

    Quando a pilha Pilha_Entrada estiver vazia, o item que estava na base de Pilha_Entrada ("A" em nosso exemplo) está agora no topo de Pilha_Saida. Retire o item de Pilha_Saida e você terá transformado sua pilha em uma fila. Seu primeiro item na pilha é agora o primeiro item a ser retirado (primeiro a entrar, primeiro a sair ou FIFO, do inglês "first in, first out").

Dicas & Advertências

  • A maioria das linguagens de programação fornece funções para tratar dados em um vetor como se fossem uma fila ou pilha. Isto é, você pode acessar tanto a última quanto a primeira posição do vetor independentemente de a partir de qual das extremidades você está inserindo os dados. Se seus dados estão em um vetor, você não precisa se preocupar em acessá-los como uma fila ou pilha. Mas se seus dados estão em uma pilha dinâmica e você quiser tratá-la como uma fila, então você deve implementar uma segunda pilha.

Não perca

Filtro:
  • Geral
  • Artigos
  • Slides
  • Vídeos
Mostrar:
  • Mais relevantes
  • Mais lidos
  • Mais recentes

Nenhum artigo disponível

Nenhum slide disponível

Nenhum vídeo disponível