introdução
estruturas de dados organizam o armazenamento em computadores para que possamos acessar e mudar os dados de forma eficiente. Stacks e filas são algumas das primeiras estruturas de dados definidas na ciência da computação.
simples de aprender e fácil de implementar, seus usos são comuns e você provavelmente vai se encontrar incorporando-os em seu software para várias tarefas.
é comum que pilhas e filas sejam implementadas com uma lista ou lista vinculada. Nós estaremos confiando na estrutura de dadosList para acomodar tanto pilhas e filas.como funcionam?
Stack
Stacks, como o nome sugere, siga o princípio do último in-First-Out (LIFO). Como se empilhando moedas um em cima do outro, a última moeda que colocamos no topo é aquela que é a primeira a ser removida 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, siga o First-in-First-Out (FIFO) princípio. Como se esperando em uma fila para os bilhetes do filme, o primeiro a ficar na fila é o primeiro a comprar um bilhete e desfrutar do filme.
Para implementar uma fila, portanto, precisamos de duas operações simples:
-
enqueue– adiciona um elemento ao final da fila:
-
dequeue– remove o elemento do início da fila:
as Pilhas e Filas usando uma Lista
Python embutido List estrutura de dados vem junto com métodos para simular a pilha e fila de operações.
vamos considerar uma pilha de letras:
Podemos usar as mesmas funções para implementar uma fila. 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 fila-como o comportamento.
considere uma “fila”de frutas:
novamente, aqui usamos as operações append e pop da lista para simular as operações principais de uma fila.
pilhas e filas com a Biblioteca Deque
Python tem uma bibliotecadeque (pronunciado ‘deck’) que fornece uma sequência com métodos eficientes para trabalhar como uma pilha ou uma fila.
deque é a abreviatura para a Dupla Terminou Fila – a fila generalizada que pode obter o primeiro ou o último elemento que é armazenado:
Se você gostaria de saber mais sobre o deque biblioteca e outros tipos de coleções Python fornece, você pode ler a nossa Introdução ao Python Coleções do Módulo abaixo.
mais Rigorosas Implementações em Python
Se o seu código necessário uma pilha e você fornecer um List, não há nada que impeça um programador da chamada insertremove ou outra lista de funções que afetam a ordem de sua pilha! Isto arruína fundamentalmente o ponto de definir uma pilha, já que ela não funciona como deveria.
Há momentos em que gostaríamos de garantir que apenas operações válidas podem ser realizadas em nossos dados.
Podemos criar classes que apenas expõe os métodos necessários para cada estrutura de dados.
Para fazer isso, vamos criar um novo arquivo chamado stack_queue.py e definir duas classes:
Os programadores a utilizar o nosso Stack e Queue agora são encorajados a utilizar os métodos fornecidos para manipular os dados em vez disso.
exemplos
Imagine que você é um desenvolvedor trabalhando em um novo processador de texto. Você está encarregado de criar uma funcionalidade de desfazer-permitindo que os usuários retrocedam suas ações até o início da sessão.
uma pilha é um ajuste ideal para este cenário. Podemos gravar todas as acções que o utilizador faz empurrando-as para a pilha. Quando o usuário quer desfazer uma ação, eles vão removê-la da pilha. Nós podemos rapidamente simular a característica como esta: filas
têm usos generalizados na programação também. Pensa em jogos como Street Fighter ou Super Smash Brothers. Os jogadores desses jogos podem realizar movimentos especiais pressionando uma combinação de botões. Estas combinações de botões podem ser armazenadas em fila de espera.agora imagine que você é um desenvolvedor trabalhando em um novo jogo de luta. Em seu jogo, cada vez que um botão é pressionado, um evento de entrada é disparado. Um testador notou que se os botões são pressionados muito rapidamente o jogo só processa o primeiro e movimentos especiais não vai funcionar!
Você pode corrigir isso com uma fila. Podemos consultar 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 processarmos os movimentos, podemos retirá-los. Um movimento especial pode ser trabalhado assim:
conclusão
pilhas 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. Em uma fila, o primeiro item que entramos é o primeiro a sair.
Nós podemos adicionar itens a uma pilha usando o push operação e recuperar itens usando o pop operação. Com filas, adicionamos itens usando a operação enqueue e recuperamos itens usando a operação dequeue.
em Python, podemos implementar pilhas e filas apenas usando a estrutura de dados incorporada List. Python também tem a bibliotecadeque que pode fornecer eficientemente operações de pilha e fila em um objeto. Finalmente, fizemos nossas aulas de pilha e fila para um controle mais apertado de nossos dados.
Existem muitos casos de uso no mundo real para pilhas e filas, Entendendo-os permite-nos resolver muitos problemas de armazenamento de dados de uma forma fácil e eficaz.