Compreendendo a implementação de pilha em Python

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.

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.

  O que são fones de ouvido Dolby Dimension?

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.

  12 melhores softwares e ferramentas de monitoramento de rede revisados ​​em 2020

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.

  Relógio mundial é um aplicativo que mantém o tempo visual com uma ferramenta dia / noite [Mac]

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 🙂 👨‍💻