As estruturas de dados desempenham um papel fundamental no mundo da programação. Eles nos ajudam a organizar nossos dados de forma que possam ser usados de forma eficiente. A pilha é uma das estruturas de dados mais simples.
Vamos aprender sobre a pilha e sua implementação em Python.
últimas postagens
O que é uma Pilha?
Uma pilha é semelhante à pilha de livros, cadeiras, etc., na vida real. E segue o princípio Last-in/First-out (LIFO). É a estrutura de dados mais simples. Vamos ver o cenário com um exemplo do mundo real.
Digamos que temos uma pilha de livros da seguinte forma.
Quando queremos o terceiro livro de cima, temos que remover os dois primeiros livros de cima para tirar o terceiro livro. Aqui, o livro mais alto vai por último na pilha e vem primeiro da pilha. A pilha de estrutura de dados segue o mesmo princípio Last-in/First-out (LIFO) na programação.
Operações na Pilha
Existem principalmente duas operações em uma pilha
1. push(dados)
Adiciona ou coloca os dados na pilha.
2. pop()
Remove ou destaca o elemento mais alto da pilha.
Veja as ilustrações abaixo das operações push e pop.
Escreveremos algumas funções auxiliares que nos ajudam a obter mais informações sobre a pilha.
Vamos vê-los.
olhadinha()
Retorna o elemento mais alto da pilha.
está vazia()
Retorna se a pilha está vazia ou não.
Aspectos conceituais suficientes da estrutura de dados da pilha. Vamos pular para a implementação sem mais delongas.
Presumo que você tenha o python instalado no seu PC, caso contrário, você também pode tentar o compilador online.
Implementação de Pilha
A implementação de pilha é a mais fácil em comparação com outras implementações de estrutura de dados. Podemos implementar uma pilha de várias maneiras em Python.
Vamos ver todos eles um por um.
#1. Lista
Vamos implementar a pilha usando a lista em uma classe. Vamos ver o passo a passo da implementação da pilha.
Passo 1: Escreva uma classe chamada Stack.
class Stack: pass
Step2: Temos que manter os dados em uma lista. Vamos adicionar uma lista vazia na classe Stack com elementos de nome.
class Stack: def __init__(self): self.elements = []
Passo 3: Para colocar os elementos na pilha, precisamos de um método. Vamos escrever um método push que recebe dados como um argumento e os anexa à lista de elementos.
class Stack: def __init__(self): self.elements = [] def push(self, data): self.elements.append(data) return data
Passo 4: Da mesma forma, vamos escrever o método pop que destaca o elemento mais alto da pilha. Podemos usar o método pop do tipo de dados de lista.
class Stack: ## ... def pop(self): return self.elements.pop()
Concluímos a implementação da pilha com as operações necessárias. Agora, vamos adicionar as funções auxiliares para obter mais informações sobre a pilha.
Etapa 5: podemos obter o elemento mais alto da pilha usando o índice negativo. O código elemento[-1] retorna o último da lista. É o elemento mais alto da pilha em nosso caso.
class Stack: ## ... def peek(self): return self.elements[-1]
Etapa 6: Se o comprimento da lista de elementos for 0, a pilha está vazia. Vamos escrever um método que retorne se o elemento está vazio ou não.
class Stack: ## ... def is_empty(self): return len(self.elements) == 0
Concluímos a implementação da pilha usando o tipo de dados de lista.
Oh! espere, acabamos de implementá-lo. Mas, não vi como usá-lo. Como usar então?
Venha, vamos ver como implementá-lo. Temos que criar um objeto para a classe Stack usá-lo. Não é grande coisa. Vamos fazer isso primeiro.
class Stack: ## ... if __name__ == '__main__': stack = Stack()
Criamos o objeto de pilha e estamos prontos para usá-lo. Vamos seguir as etapas abaixo para testar as operações de pilha.
- Verifique se a pilha está vazia ou não usando o método is_empty. Deve retornar True.
- Empurre os números 1, 2, 3, 4, 5 para a pilha usando o método push.
- O método is_empty deve retornar False. Confira.
- Imprima o elemento superior usando o método peek.
- Retire o elemento da pilha usando o método pop.
- Verifique o elemento peek. Deve retornar o elemento 4.
- Agora, retire todos os elementos da pilha.
- O método is_empty deve retornar True. Confira.
Nossa implementação de pilha está concluída se passar por todas as etapas acima. Tente escrever o código para as etapas acima.
Você escreveu o código? Não, não se preocupe, verifique o código abaixo.
class Stack: def __init__(self): self.elements = [] def push(self, data): self.elements.append(data) return data def pop(self): return self.elements.pop() def peek(self): return self.elements[-1] def is_empty(self): return len(self.elements) == 0 if __name__ == '__main__': stack = Stack() ## checking is_empty method -> true print(stack.is_empty()) ## pushing the elements stack.push(1) stack.push(2) stack.push(3) stack.push(4) stack.push(5) ## again checking is_empty method -> false print(stack.is_empty()) ## printing the topmost element of the stack -> 5 print(stack.peek()) ## popping the topmost element -> 5 stack.pop() ## checking the topmost element using peek method -> 4 print(stack.peek()) ## popping all the elements stack.pop() stack.pop() stack.pop() stack.pop() ## checking the is_empty method for the last time -> true print(stack.is_empty())
Viva! concluímos a implementação da pilha do zero usando o tipo de dados de lista. Você verá a saída conforme mencionado abaixo se executar o código acima.
True False 5 4 True
Podemos usar diretamente o tipo de dados da lista como uma pilha. A implementação de pilha acima também ajuda a entender a implementação de pilha em outras linguagens de programação.
Você também pode conferir estes artigos relacionados à lista.
Vamos ver o deque integrado do módulo interno de coleções, que pode atuar como uma pilha.
#2. deque de coleções
É implementado como uma fila dupla. Uma vez que suporta a adição e remoção de elementos de ambas as extremidades. Portanto, podemos usá-lo como uma pilha. Podemos fazê-lo seguir o princípio LIFO da pilha.
Ela é implementada usando outras estruturas de dados chamadas de lista duplamente encadeada. Portanto, o desempenho da inserção e exclusão de elementos é consistente. Acessar elementos da lista encadeada do meio levou tempo O(n). Podemos usá-lo como uma pilha, pois não há necessidade de acessar os elementos do meio da pilha.
Antes de implementar a pilha, vamos ver os métodos que são usados para implementar a pilha usando a fila.
- append(data) – usado para enviar os dados para a pilha
- pop() – usado para remover o elemento mais alto da pilha
Não há métodos alternativos para peek e is_empty. Podemos imprimir toda a pilha no lugar do método peek. Em seguida, podemos usar o método len para verificar se a pilha está vazia ou não.
Vamos implementar a pilha usando deque do módulo collections.
from collections import deque ## creating deque object stack = deque() ## checking whether stack is empty or not -> true print(len(stack) == 0) ## pushing the elements stack.append(1) stack.append(2) stack.append(3) stack.append(4) stack.append(5) ## again checking whether stack is empty or not -> false print(len(stack) == 0) ## printing the stack print(stack) ## popping the topmost element -> 5 stack.pop() ## printing the stack print(stack) ## popping all the elements stack.pop() stack.pop() stack.pop() stack.pop() ## checking the whether stack is empty or not for the last time -> true print(len(stack) == 0)
É isso. Aprendemos como implementar a pilha usando o deque do módulo interno collections. Você obterá a saída mencionada abaixo se executar o programa acima.
True False deque([1, 2, 3, 4, 5]) deque([1, 2, 3, 4]) True
Até agora, vimos duas maneiras de implementar a pilha. Existem outras maneiras de implementar uma pilha? Sim! Vamos ver a forma final de implementar uma pilha neste tutorial.
#3. LifoQueue
O próprio nome LifoQueue diz que segue o princípio LIFO. Portanto, podemos usá-lo como uma pilha sem qualquer dúvida. É da fila do módulo integrado. O LifoQueue fornece alguns métodos práticos que são úteis na implementação da pilha. vamos vê-los
- put(data) – adiciona ou empurra os dados para a fila
- get() – remove ou exibe o elemento mais alto da fila
- empty() – retorna se a pilha está vazia ou não
- qsize() – retorna o comprimento da fila
Vamos implementar a pilha usando LifoQueue do módulo queue.
from queue import LifoQueue ## creating LifoQueue object stack = LifoQueue() ## checking whether stack is empty or not -> true print(stack.empty()) ## pushing the elements stack.put(1) stack.put(2) stack.put(3) stack.put(4) stack.put(5) ## again checking whether stack is empty or not -> false print(stack.empty()) ## popping all the elements print(stack.get()) print(stack.get()) print(stack.get()) ## checking the stack size print("Size", stack.qsize()) print(stack.get()) print(stack.get()) ## checking the whether stack is empty or not for the last time -> true print(stack.empty())
Você obterá a saída mencionada abaixo se executar o programa acima sem alterá-lo.
True False 5 4 3 Size 2 2 1 True
Aplicação de Pilha
Agora, você tem conhecimento suficiente sobre pilhas para aplicá-lo em problemas de programação. Vamos ver um problema e resolvê-lo usando uma pilha.
Dada uma expressão, escreva um programa para verificar se os parênteses, chaves e chaves estão balanceados corretamente ou não.
Vejamos alguns exemplos.
Entrada: “[{}]([])”
Saída: Equilibrado
Entrada: “{[}]([])”
Saída: não balanceada
Podemos usar a pilha para resolver o problema acima. Vamos ver os passos para resolver o problema.
- Crie uma pilha para armazenar os personagens.
- Se o comprimento da expressão for ímpar, a expressão não é balanceada
- Iterar através da expressão dada.
- Se o caractere atual for o colchete de abertura de ( ou { ou [, then push it to stack.
- Else if the current character is a closing bracket ) or } or ]em seguida, saia da pilha.
- Se o caractere exibido corresponder ao colchete inicial, continue, caso contrário, os colchetes não serão balanceados.
- Após a iteração, se a pilha estiver vazia, a equação será balanceada, caso contrário, a equação não será balanceada.
Podemos usar o tipo de dados definido para verificação de correspondência de colchetes.
## stack class Stack: def __init__(self): self.elements = [] def push(self, data): self.elements.append(data) return data def pop(self): return self.elements.pop() def peek(self): return self.elements[-1] def is_empty(self): return len(self.elements) == 0 def balance_check(expression): ## checking the length of the expression if len(expression) % 2 != 0: ## not balanced if the length is odd return False ## for checking opening_brackets = set('([{') pairs = set([ ('(',')'), ('[',']'), ('{','}') ]) ## stack initialization stack = Stack() ## iterating through the given expression for bracket in expression: ## checking whether the current bracket is opened or not if bracket in opening_brackets: ## adding to the stack stack.push(bracket) else: ## popping out the last bracket from the stack popped_bracket = stack.pop() ## checking whether popped and current bracket pair if (popped_bracket, bracket) not in pairs: return False return stack.is_empty() if __name__ == '__main__': if balance_check('[{}]([])'): print("Balanced") else: print("Not Balanced") if balance_check('{[}]([])'): print("Balanced") else: print("Not Balanced")
Podemos usar a pilha para resolver muitos outros problemas. O problema acima é um deles. Tente aplicar o conceito de pilha onde achar melhor.
Conclusão
Sim! Você concluiu o tutorial. Espero que tenham gostado do tutorial tanto quanto eu enquanto o fazia. Isso é tudo para o tutorial.
Boa codificação 🙂 👨💻