Trabalhando com pilhas

Estruturas de Dados e Algoritmos em Python

Miriam Antona

Software Engineer

Pilhas

LIFO: Last-In First-Out
- O último inserido é o primeiro a ser removido

Uma pilha de livros.

Pilhas

LIFO: Last-In First-Out
- O último inserido é sempre o primeiro a ser removido
Só dá pra adicionar no topo
- Push na pilha

Uma pilha de livros com um novo livro adicionado no topo.

Pilhas

LIFO: Last-In First-Out
- O último inserido é sempre o primeiro a ser removido
Só dá pra adicionar no topo
- Push na pilha
Só dá pra retirar do topo
- Pop da pilha

Uma pilha de livros com um livro sendo retirado do topo.

Pilhas

LIFO: Last-In First-Out
- O último inserido é sempre o primeiro a ser removido
Só dá pra adicionar no topo
- Push na pilha
Só dá pra remover do topo
- Pop da pilha
Só dá pra ler o último elemento
- Peek na pilha

Uma pilha de livros com uma seta apontando para a capa do livro no topo da pilha.

Pilhas - usos reais

Função desfazer (Undo)

Uma pilha com um elemento.

Pilhas - usos reais

Função desfazer (Undo)
- push de cada tecla

Uma pilha com um novo elemento adicionado ao topo.

Pilhas - usos reais

Função desfazer (Undo)
- push de cada tecla

Uma pilha com um novo elemento adicionado ao topo.

Pilhas - usos reais

Função desfazer (Undo)
- push de cada tecla

Uma pilha com um novo elemento adicionado ao topo.

Pilhas - usos reais

Função desfazer (Undo)
- push de cada tecla

Uma pilha com um novo elemento adicionado ao topo.

Pilhas - usos reais

Função desfazer (Undo)
- push de cada tecla
- pop da última tecla inserida

Uma pilha onde um elemento foi removido do topo.

Pilhas - usos reais

Validador de símbolos: ( [ { } ] )
- push de símbolos de abertura

Uma pilha com um símbolo de abertura.

Pilhas - usos reais

Validador de símbolos: ( [ { } ] )
- push de símbolos de abertura

Uma pilha com um novo símbolo de abertura adicionado ao topo.

Pilhas - usos reais

Validador de símbolos: ( [ { } ] )
- push de símbolos de abertura

Uma pilha com um novo símbolo de abertura adicionado ao topo.

Pilhas - usos reais

Validador de símbolos: ( [ { } ] )
- push de símbolos de abertura
- checar símbolo de fechamento

Uma pilha com símbolos de abertura e a palavra "check "}"".

Pilhas - usos reais

Validador de símbolos: ( [ { } ] )
- push de símbolos de abertura
- checar símbolo de fechamento
- pop do símbolo de abertura correspondente

Uma pilha onde um símbolo de abertura foi removido do topo.

Pilhas - usos reais

Chamadas de função
- push de bloco de memória
- pop após o fim da execução

Pilhas - implementação com listas encadeadas simples

Uma pilha representada como lista encadeada.

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

Pilhas - implementação com listas encadeadas simples

Uma pilha representada como lista encadeada com os nomes das partes dos nós.

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Stack:
  def __init__(self):
    self.top = None

Pilhas - implementação com listas encadeadas simples

Uma pilha representada como lista encadeada com a palavra "TOP" apontando para o topo da pilha.

class Node:
  def __init__(self,data):
    self.data = data
    self.next = None

class Stack:
  def __init__(self):
    self.top = None

Pilhas - push

Representação de uma pilha vazia e uma pilha com elementos.

def push(self, data):

Pilhas - push

Representação de uma pilha vazia e uma pilha com elementos onde um novo nó será inserido.

def push(self, data): 
  new_node = Node(data)

  if self.top:

Pilhas - push

Representação de uma pilha vazia e uma pilha com elementos, onde o novo nó é conectado ao elemento no topo.

def push(self, data): 
  new_node = Node(data)
  if self.top:

    new_node.next = self.top

Pilhas - push

Representação de uma pilha vazia e uma pilha com elementos onde o novo nó foi inserido.

def push(self, data): 
  new_node = Node(data)
  if self.top:
    new_node.next = self.top
  self.top = new_node

Pilhas - pop

def pop(self):

  if self.top is None:

    return None

  else:

Representação de uma pilha com a palavra "TOP" apontando para o nó no topo.

Pilhas - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top

Representação de uma pilha com a palavra "popped_node" apontando para o nó no topo.

Pilhas - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next

Representação de uma pilha com a palavra "popped_node" apontando para o nó no topo e "TOP" apontando para o segundo nó.

Pilhas - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next
    popped_node.next = None

Representação de uma pilha com "popped_node" apontando para um nó desconectado e "TOP" apontando para o nó no topo.

Pilhas - pop

def pop(self):
  if self.top is None:
    return None
  else:
    popped_node = self.top
    self.top = self.top.next
    popped_node.next = None
    return popped_node.data

Representação de uma pilha com a palavra "TOP" apontando para o nó no topo.

Pilhas - peek

def peek(self):

  if self.top:

    return self.top.data

  else:

    return None

LifoQueue no Python

LifoQueue:
- Módulo queue do Python
- se comporta como uma pilha

import queue


my_book_stack = queue.LifoQueue(maxsize=0)

my_book_stack.put("The misunderstanding")
my_book_stack.put("Persepolis")
my_book_stack.put("1984")


print("The size is: ", my_book_stack.qsize())

The size is: 3

print(my_book_stack.get())
print(my_book_stack.get())
print(my_book_stack.get())

1984
Persepolis
The misunderstanding

print("Empty stack: ", my_book_stack.empty())

Empty stack: True

Vamos praticar!

Estruturas de Dados e Algoritmos em Python