O que são estruturas de dados de pilha em Python?



Este artigo fornecerá a você um conhecimento detalhado e abrangente das estruturas de dados da pilha em Python, com muitos exemplos.

Estruturas de dados são uma coleção de valores de dados, os relacionamentos entre eles e as funções ou operações que podem ser aplicadas aos dados. Agora, existem muitas estruturas de dados disponíveis. Mas hoje nosso foco será em estruturas de dados de pilha. Discutirei os seguintes tópicos:

Por que estruturas de dados?

Para responder a isso, você terá que pensar em um nível amplo. Pense em como o Google Maps mostra a melhor rota em apenas uma fração de segundos, como ele retorna o resultado da pesquisa em microssegundos. Não lida com apenas 100 sites, lida com mais de um bilhão de sites e ainda mostra seus resultados com muita rapidez.





Bem, embora o algoritmo usado desempenhe um papel crucial, a estrutura de dados ou o contêiner usado é a base desse algoritmo. Em qualquer aplicação, organizar e armazenar dados de uma forma ou em uma estrutura que seja mais adequada para seu uso é fundamental para o acesso e processamento de dados eficientes.

mesclar algoritmo de classificação c ++

Tipos de estruturas de dados

Existem algumas estruturas de dados padrão que podem ser usadas para trabalhar com dados de maneira eficiente. Podemos até personalizá-los ou construir outros completamente novos para se adequar à nossa aplicação.



Tipos de estrutura de dados

O que é a estrutura de dados da pilha?

Considere alguns exemplos da vida real:

  • Embarque na carga
  • Pratos em uma bandeja
  • Pilha de moedas
  • Pilha de gavetas
  • Manobra de trens em um pátio ferroviário

plates-stacks-data-structure



Todos esses exemplos seguem um Ultimo a entrar primeiro a sair estratégia. Considere os pratos em uma bandeja. Quando você quer pegar um prato, é forçado a retirá-lo de cima, ao passo que, quando os pratos foram mantidos na bandeja, eles devem estar na ordem inversa. Exemplos acima que seguem o Último a entrar, primeiro a sair (UEPS) princípio são conhecidos como Pilha .

Além das operações complementares, posso dizer que as principais operações possíveis na pilha são:

  1. Empurre ou insira um elemento no topo da pilha
  2. Destaque ou remova um elemento do topo da pilha

Criação da estrutura de dados da pilha

class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1
  • tamanho máximo é o número máximo de elementos esperados na pilha.
  • Os elementos da pilha são armazenados na lista python.
  • Top indica o índice mais alto da pilha que é inicialmente considerado -1 para marcar a pilha vazia.

O status inicial da Pilha pode ser visto na Figura onde max_size = 5

Empurre o elemento para a pilha

Agora, se você quiser inserir ou empurrar o elemento para a pilha, você deve se lembrar que

  • O topo apontará o índice no qual o elemento será inserido.
  • E que nenhum elemento será inserido quando a pilha estiver cheia, ou seja, quando max_size = top.

Então, qual deve ser o algoritmo ??

# retorna o tamanho máximo da pilha def get_max_size (self): return self .__ max_size # retorna o valor bool se a pilha está cheia ou não, True se cheia e False caso contrário def is_full (self): return self.get_max_size () - 1 == self .__ top #pushes o elemento no topo da pilha def push (self, data): if (self.is_full ()): print ('a pilha já está cheia') else: self .__ top = self .__ top + int (1 ) self .__ elements [self .__ top] = data #Você pode usar o seguinte __str __ () para imprimir os elementos do objeto DS durante a depuração def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = '' .join (msg) msg ​​= 'Stack data (Top to Bottom):' + msg return msg

Agora, quando você executa o seguinte:

pilha1 = Pilha (4)

#Empurre todos os elementos necessários.

stack1.push (“A”)

stack1.push (“B”)

stack1.push (“C”)

stack1.push (“E”)

imprimir (stack1.is_full ())

imprimir (pilha1)

Resultado:

pilha já está cheia
Verdade
Pilha de dados (de cima para baixo): D C B A

Elementos pop da pilha

Agora, como você inseriu os elementos na pilha, deseja destacá-los, portanto, deve tomar cuidado com o seguinte:

  • A pilha não está vazia, ou seja, topo! = -1
  • Quando você exclui os dados, o topo deve apontar para o topo anterior da pilha.

Então, qual será o algoritmo ??

#retorna o valor bool se a pilha está vazia ou não, True se vazio e False, caso contrário def is_empty (self): return self .__ top == - 1 #retorna o valor exibido def pop (self): if (self.is_empty ()): print ('nothing to pop, already empty') else: a = self .__ elements [self .__ top] self .__ top = self .__ top-1 retorna a #display todos os elementos da pilha de cima para baixo def display (self): para i no intervalo (self .__ top, -1, -1): print (self .__ elements [i], end = '') print ()

Agora, considerando a pilha criada anteriormente, tente pop os elementos

imprimir (stack1.pop ())

imprimir (stack1.pop ())

imprimir (pilha1)

o que é scipy em python

imprimir (stack1.pop ())

imprimir (stack1.pop ())

imprimir (stack1.pop ())

Resultado:

D

C

system.exit (0) pode ser usado para encerrar o programa.

Empilhar dados (de cima para baixo): B A

B

PARA

nada para estourar, já vazio

Aplicações da estrutura de dados da pilha

  • Exemplo 1:

Uma pilha é usada para implementar o algoritmo de correspondência de colchetes para avaliação de expressão aritmética e também na implementação de chamadas de método.

A resposta é 5.

  • Exemplo 2:

Área de transferência no Windows usa duas pilhas para implementar operações desfazer-refazer (ctrl + z, ctrl + y). Você teria trabalhado em editores de texto do Windows, como MS-Word, Notepad, etc. Aqui está um texto escrito em MS-Word. Observe como o texto mudou com o clique de Ctrl-Z e Ctrl-Y.

Aqui está um código que simula a operação desfazer-refazer. Percorra o código e observe como a pilha é usada nesta implementação.

#creating class stack class Stack: def __init __ (self, max_size): self .__ max_size = max_size self .__ elements = [None] * self .__ max_size self .__ top = -1 def is_full (self): if (self .__ top == self .__ max_size-1): return True return False def is_empty (self): if (self .__ top == - 1): return True return False def push (self, data): if (self.is_full ()): print ('A pilha está cheia !!') else: self .__ top + = 1 self .__ elementos [self .__ top] = data def pop (self): if (self.is_empty ()): print ('A pilha está vazia! ! ') else: data = self .__ elements [self .__ top] self .__ top- = 1 dados de retorno def display (self): if (self.is_empty ()): print (' A pilha está vazia ') else: index = self .__ top while (index> = 0): print (self .__ elements [index]) index- = 1 def get_max_size (self): return self .__ max_size #Você pode usar o seguinte __str __ () para imprimir os elementos do Objeto DS durante a depuração def __str __ (self): msg = [] index = self .__ top while (index> = 0): msg.append ((str) (self .__ elements [index])) index- = 1 msg = ' '.join (msg) msg ​​=' Pilha de dados (de cima para baixo): '+ msg return ms g #função para implementar a operação de remoção ou retrocesso def remove (): área de transferência global, undo_stack data = clipboard [len (clipboard) -1] clipboard.remove (data) undo_stack.push (data) print ('Remover:', área de transferência) #função para implementar a operação desfazer def undo (): área de transferência global, undo_stack, redo_stack if (undo_stack.is_empty ()): print ('Não há dados para desfazer') else: data = undo_stack.pop () clipboard.append ( data) redo_stack.push (data) print ('Desfazer:', área de transferência) #função para implementar a operação de refazer def redo (): área de transferência global, undo_stack, redo_stack if (redo_stack.is_empty ()): print ('Não há dados para refazer ') else: data = redo_stack.pop () if (os dados não estão na área de transferência): print (' Não há dados para refazer ') redo_stack.push (data) else: clipboard.remove (data) undo_stack.push ( data) print ('Refazer:', área de transferência) área de transferência = ['A', 'B', 'C', 'D', 'E', 'F'] undo_stack = Pilha (len (área de transferência)) redo_stack = Pilha (len (área de transferência)) remove () desfazer () refazer ()

Resultado:

Remover: [‘A’, ‘B’, ‘C’, ‘D’, ‘E’]

Desfazer: [‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’]

Refazer: [‘A’, ‘B’, ‘C’, ‘D’, ‘E’]

Com isso, chegamos ao fim deste artigo sobre Estrutura de dados de pilha em Python. Se você entendeu e executou os códigos com sucesso, não é mais um novato na estrutura de dados de pilhas.

Tem alguma questão para nós? Mencione isso na seção de comentários deste artigo e entraremos em contato com você o mais breve possível.

Para obter conhecimento aprofundado sobre Python e seus vários aplicativos, você pode se inscrever para com suporte 24/7 e acesso vitalício.