Introdução

Estruturas de dados organizam o armazenamento em computadores para que possamos acessar e alterar dados de forma eficiente. Stacks and Queues são algumas das primeiras estruturas de dados definidas em informática.

Simples de aprender e fáceis de implementar, as suas utilizações são comuns e o mais provável é que se encontre a incorporá-las no seu software para várias tarefas.

É comum que Stacks and Queues sejam implementadas com um Array ou Linked List. Estaremos confiando na estrutura de dados List para acomodar tanto Pilhas como Filas.

Como funcionam?

Pilha

Pilha, como o nome sugere, siga o princípio Last-in-First-Out (LIFO). Como se empilhando moedas uma em cima da outra, a última moeda que colocamos em cima é a primeira a ser retirada da pilha mais tarde.

Para implementar uma pilha, portanto, precisamos de duas operações simples:

• push – adiciona um elemento ao topo da pilha:

• pop – remove o elemento no topo da pilha:

>

Fila

Filas, como o nome sugere, seguem o princípio First-in-First-Out (FIFO). Como se estivesse numa fila à espera dos bilhetes do filme, o primeiro a ficar na fila é o primeiro a comprar um bilhete e a apreciar o filme.

Para implementar uma fila, portanto, precisamos de duas operações simples:

• enqueue – adiciona um elemento ao final da fila:

• dequeue – remove o elemento no início da fila:

>

Escalões e Filas usando Listas

Integração do Python List estrutura de dados vem empacotada com métodos para simular tanto as operações de empilhamento como as de fila.

Vamos considerar uma pilha de letras:

Podemos usar as mesmas funções para implementar uma Fila de espera. A função pop opcionalmente toma o índice do item que queremos recuperar como argumento.

Então podemos usar pop com o primeiro índice da lista i.e. 0, para obter um comportamento semelhante a uma fila.

Considerar uma “fila” de frutas:

Ganhar, aqui usamos as operações append e pop da lista para simular as operações centrais de uma fila.

Fichas e Filas com a Deque Library

Python tem uma biblioteca deque (pronuncia-se ‘deck’) que fornece uma sequência com métodos eficientes para funcionar como uma pilha ou uma fila.

deque é a abreviação de Double Ended Queue – uma fila generalizada que pode obter o primeiro ou último elemento que está armazenado:

Se você gostaria de aprender mais sobre a biblioteca deque e outros tipos de coleções que Python fornece, você pode ler nosso artigo Introduction to Python’s Collections Module.

Aplicações mais estritas em Python

Se o seu código precisava de uma pilha e você fornece uma List, nada impede um programador de chamar insert, remove ou outras funções de lista que irão afectar a ordem da sua pilha! Isto arruína fundamentalmente o ponto de definir uma pilha, pois ela não funciona mais como deveria.

Há momentos em que gostaríamos de garantir que somente operações válidas possam ser realizadas em nossos dados.

Podemos criar classes que expõem somente os métodos necessários para cada estrutura de dados.

Para isso, vamos criar um novo arquivo chamado stack_queue.py e definir duas classes:

Os programadores que usam nossos Stack e Queue são agora encorajados a usar os métodos fornecidos para manipular os dados em seu lugar.

Exemplos

Imagine que você é um desenvolvedor trabalhando em um processador de texto novinho em folha. Você está encarregado de criar um recurso de desfazer – permitindo aos usuários retroceder suas ações até o início da sessão.

Uma pilha é um ajuste ideal para este cenário. Podemos gravar cada ação que o usuário faz empurrando-a para a pilha. Quando o usuário quiser desfazer uma ação, ele a abrirá da pilha. Podemos rapidamente simular a funcionalidade assim:

Queues também têm usos generalizados na programação. Pense em jogos como Street Fighter ou Super Smash Brothers. Jogadores nesses jogos podem executar movimentos especiais pressionando uma combinação de botões. Estas combinações de botões podem ser armazenadas em uma fila.

Agora imagine que você é um desenvolvedor trabalhando em um novo jogo de luta. Em seu jogo, toda vez que um botão é pressionado, um evento de entrada é disparado. Um testador notou que se os botões forem pressionados muito rapidamente o jogo só processa o primeiro e movimentos especiais não vão funcionar!

Você pode corrigir isso com uma fila. Nós podemos questionar todos os eventos de entrada à medida que eles entram. Desta forma não importa se os eventos de entrada vêm com pouco tempo entre eles, todos eles serão armazenados e disponíveis para processamento. Quando estamos a processar os movimentos, podemos decifrá-los. Um movimento especial pode ser trabalhado desta forma:

Conclusão

Fichas e filas são estruturas de dados simples que nos permitem armazenar e recuperar dados sequencialmente. Em uma pilha, o último item que entramos é o primeiro a sair. Numa fila, o primeiro item que entramos é o primeiro a sair.

Podemos adicionar itens a uma pilha usando a operação push e recuperar itens usando a operação pop. Com as filas, podemos adicionar itens usando a operação enqueue e recuperar itens usando a operação dequeue.

Em Python, podemos implementar pilhas e filas apenas usando a estrutura de dados List incorporada. Python também tem a biblioteca deque que pode eficientemente fornecer operações de pilha e fila em um único objeto. Finalmente, fizemos nossas classes de pilha e fila para um controle mais rigoroso dos nossos dados.

Existem muitos casos de uso do mundo real para pilhas e filas, compreendê-los permite-nos resolver muitos problemas de armazenamento de dados de uma forma fácil e eficaz.