Material Didático de Estruturas de

Dados: Pilhas (Stacks)

Introdução: O que é uma Pilha?

No universo da ciência da computação, uma pilha (ou stack, em inglês) é uma das
estruturas de dados mais fundamentais e importantes. Ela representa uma coleção de
elementos organizados de uma maneira específica, seguindo o princípio LIFO (Last-
In, First-Out), que em português significa "o último a entrar é o primeiro a sair".

Para visualizar esse conceito, imagine uma pilha de pratos. Ao adicionar um novo
prato, você o coloca no topo da pilha. Quando precisa de um prato, você também o
retira do topo. O primeiro prato que você colocou na pilha será o último a ser retirado.
Esse comportamento é exatamente como uma pilha de dados funciona.
As pilhas são estruturas de dados lineares, o que significa que os elementos são
organizados em uma sequência. Elas são amplamente utilizadas em diversas
aplicações, desde o gerenciamento de chamadas de funções em linguagens de
programação até a implementação de funcionalidades como "desfazer" (undo) em
editores de texto.

O Princípio LIFO: Last-In, First-Out

O princípio LIFO é a característica que define uma pilha. Ele determina que o último
elemento adicionado à estrutura será sempre o primeiro a ser removido. Essa ordem
de acesso é o que diferencia as pilhas de outras estruturas de dados, como as filas
(queues), que seguem o princípio FIFO (First-In, First-Out), onde o primeiro a entrar é
o primeiro a sair.

Operações Fundamentais de uma Pilha

Existem algumas operações básicas que podem ser realizadas em uma pilha para
manipular seus elementos. As mais comuns são:

Push (Empilhar): Adiciona um novo elemento no topo da pilha.

 Pop (Desempilhar): Remove e retorna o elemento que está no topo da pilha.

Peek (Espiar): Retorna o elemento do topo da pilha sem removê-lo.

isEmpty (Está Vazia?): Verifica se a pilha está vazia.

isFull (Está Cheia?): Verifica se a pilha está cheia (relevante para

implementações com tamanho fixo).

Size (Tamanho): Retorna o número de elementos na pilha.

Complexidade de Tempo e Espaço

A eficiência de uma estrutura de dados é medida pela sua complexidade de tempo e

espaço. Para pilhas, as operações básicas são muito eficientes:
 Operação Complexidade de Tempo

Push O(1)

Pop O(1)

Peek O(1)

isEmpty O(1)

Size O(1)

A complexidade de espaço de uma pilha é O(n), onde n é o número de elementos na

pilha. Isso significa que o espaço de memória necessário para armazenar a pilha é
diretamente proporcional ao número de elementos que ela contém.

Casos de Uso e Aplicações Práticas

As pilhas são utilizadas em uma vasta gama de aplicações no mundo da computação.

Alguns dos exemplos mais notáveis incluem:

Gerenciamento de Chamadas de Funções: Quando um programa executa uma

função, o endereço de retorno e as variáveis locais são "empilhados" em uma
estrutura chamada call stack. Quando a função termina, esses dados são
"desempilhados" para que o programa possa continuar sua execução a partir do
ponto onde parou.

Analisadores Sintáticos (Parsers): Em compiladores e interpretadores, as pilhas

são usadas para verificar a sintaxe de expressões e garantir que parênteses,
colchetes e chaves estejam balanceados.

Algoritmos de Navegação: Algoritmos como o de busca em profundidade

(Depth-First Search - DFS) utilizam pilhas para manter o controle dos nós a serem
visitados em um grafo.

Funcionalidade de Desfazer/Refazer (Undo/Redo): Editores de texto,

programas de design e outras aplicações usam pilhas para armazenar o histórico
de ações do usuário, permitindo que ele desfaça e refaça operações facilmente.

Navegadores Web: O histórico de páginas visitadas em um navegador é

frequentemente implementado como uma pilha, permitindo que o usuário volte
para a página anterior pressionando o botão "voltar".
Implementações de Pilhas

Existem duas abordagens principais para implementar uma pilha: usando um array
(ou vetor) ou uma lista ligada (ou encadeada). Ambas as abordagens têm suas
vantagens e desvantagens, e a escolha entre elas depende dos requisitos específicos
da aplicação.

Implementação com Array/Vetor

Uma implementação baseada em array é a forma mais simples de criar uma pilha. Em
Python, podemos usar as listas nativas da linguagem, que são, na verdade, arrays
dinâmicos. Nessa abordagem, a pilha é representada por um array e uma variável (ou
ponteiro) que indica a posição do topo da pilha.

Vantagens:

Simplicidade: É fácil de implementar e entender.

Eficiência de Acesso: O acesso aos elementos é rápido devido à natureza

contígua da memória em arrays.

Desvantagens:
 Tamanho Fixo (em algumas linguagens): Em linguagens de programação de
mais baixo nível, os arrays têm um tamanho fixo, o que pode levar a um
desperdício de memória ou a um estouro de pilha (stack overflow) se o número
de elementos exceder a capacidade do array. Em Python, as listas são dinâmicas,
o que mitiga esse problema.

Implementação com Lista Ligada

Uma implementação baseada em lista ligada utiliza uma estrutura de nós, onde cada
nó contém um valor e um ponteiro para o próximo nó na pilha. O topo da pilha é
simplesmente o primeiro nó da lista.

Vantagens:

Tamanho Dinâmico: A pilha pode crescer e diminuir conforme necessário, sem a

necessidade de pré-alocar um tamanho fixo.

Flexibilidade: É mais flexível em termos de alocação de memória.

Desvantagens:
 Maior Consumo de Memória: Cada nó armazena um ponteiro adicional, o que
pode consumir mais memória do que uma implementação com array.

Acesso mais Lento: O acesso aos elementos pode ser mais lento, pois requer a
travessia da lista.

Exemplos Práticos em Python

Para consolidar o entendimento sobre pilhas, vamos explorar alguns exemplos

práticos que demonstram como essa estrutura de dados pode ser aplicada na
resolução de problemas reais.

Exemplo 1: Uso Básico de Pilha com Lista Nativa

Python oferece uma maneira simples de implementar uma pilha usando listas nativas.
As operações append() e pop() correspondem às operações push e pop de uma
pilha:

# Criando uma pilha vazia

pilha = []

# Operação Push (empilhar)

[Link](10)
[Link](20)
[Link](30)
print(f"Pilha: {pilha}") # [10, 20, 30]

# Operação Peek (espiar o topo)

if pilha:
topo = pilha[-1]
print(f"Elemento no topo: {topo}") # 30

# Operação Pop (desempilhar)

elemento = [Link]()
print(f"Elemento removido: {elemento}") # 30
print(f"Pilha após remoção: {pilha}") # [10, 20]

Exemplo 2: Verificação de Parênteses Balanceados

Um dos problemas clássicos que pode ser resolvido elegantemente com pilhas é a
verificação de parênteses balanceados em expressões matemáticas:
 def parenteses_balanceados(expressao):
pilha = []

for char in expressao:

if char == '(':
[Link](char) # Push
elif char == ')':
if not pilha: # Pilha vazia, mas encontrou ')'
return False
[Link]() # Pop

return len(pilha) == 0 # True se balanceado

# Testando
print(parenteses_balanceados("(())")) # True
print(parenteses_balanceados("())")) # False

Exemplo 3: Inversão de String

As pilhas são perfeitas para inverter sequências devido ao seu comportamento LIFO:

def inverter_string(texto):
pilha = []

# Push de cada caractere

for char in texto:
[Link](char)

# Pop para formar string invertida

string_invertida = ""
while pilha:
string_invertida += [Link]()

return string_invertida

print(inverter_string("Python")) # "nohtyP"

Exemplo 4: Calculadora de Expressões Pós-fixas

A notação pós-fixa (ou polonesa reversa) é uma forma de escrever expressões

matemáticas onde os operadores vêm após os operandos. Por exemplo, "3 4 +"
representa "3 + 4":
 def calcular_pos_fixa(expressao):
pilha = []
tokens = [Link]()

for token in tokens:

if [Link]():
[Link](int(token)) # Push número
else:
# Pop dois operandos
b = [Link]()
a = [Link]()

if token == '+':
resultado = a + b
elif token == '-':
resultado = a - b
elif token == '*':
resultado = a * b
elif token == '/':
resultado = a / b

[Link](resultado) # Push resultado

return pilha[0]

print(calcular_pos_fixa("3 4 +")) # 7
print(calcular_pos_fixa("3 4 + 2 *")) # 14

HANDS-ON: Implementação de Pilha com Array/Vetor

Agora, vamos colocar a mão na massa e construir nossa própria classe de Pilha em
Python, usando uma lista como base (que funciona como um array dinâmico). Este
guia passo a passo foi projetado para ser o mais didático possível, explicando cada
detalhe do processo.

O Código Completo

Abaixo está o código completo da nossa classe PilhaArray . Vamos analisá-lo em

detalhes a seguir.
 # HANDS-ON: Implementação de Pilha usando Array/Vetor
# Material Didático de Estruturas de Dados
#
# Este arquivo contém uma implementação passo a passo de uma pilha
# usando uma lista Python (que funciona como um array dinâmico).
#
# OBJETIVO: Aprender a criar uma classe Pilha do zero, entendendo
# cada operação e como ela funciona internamente.

class PilhaArray:
"""
Implementação de uma Pilha usando lista Python (array dinâmico).

Esta classe demonstra como implementar uma pilha do zero,

com todas as operações básicas explicadas passo a passo.
"""

def __init__(self, capacidade_maxima=None):

"""
Construtor da classe PilhaArray.

Parâmetros:
- capacidade_maxima: limite máximo de elementos (opcional)

O que acontece aqui:

1. Criamos uma lista vazia para armazenar os elementos
2. Definimos a capacidade máxima (se especificada)
"""
[Link] = [] # Lista que armazenará os elementos da pilha
self.capacidade_maxima = capacidade_maxima

print(f"✅ Pilha criada com capacidade máxima: {capacidade_maxima if

capacidade_maxima else 'ilimitada'}")

def push(self, elemento):

"""
Operação PUSH: Adiciona um elemento no topo da pilha.

Parâmetros:
- elemento: o valor a ser adicionado na pilha

Passos da operação:
1. Verifica se a pilha não está cheia (se há limite)
2. Adiciona o elemento no final da lista (que representa o topo)
3. Confirma a operação
"""
# Passo 1: Verificar se a pilha está cheia

cheia!")
print(f" ❌
if self.esta_cheia():
ERRO: Não é possível empilhar '{elemento}'. Pilha está

return False

# Passo 2: Adicionar elemento no topo (final da lista)

[Link](elemento)

print(f"📥
# Passo 3: Confirmar operação

{[Link]}")
PUSH: '{elemento}' adicionado. Pilha agora:

return True

def pop(self):
 """
Operação POP: Remove e retorna o elemento do topo da pilha.

Retorna:
- O elemento removido, ou None se a pilha estiver vazia

Passos da operação:
1. Verifica se a pilha não está vazia
2. Remove o último elemento da lista (topo da pilha)
3. Retorna o elemento removido
"""
# Passo 1: Verificar se a pilha está vazia

print(" ❌
if self.esta_vazia():
ERRO: Não é possível desempilhar. Pilha está vazia!")
return None

# Passo 2: Remover elemento do topo (último da lista)

elemento_removido = [Link]()

📤
# Passo 3: Confirmar operação e retornar elemento
print(f"
{[Link]}")
POP: '{elemento_removido}' removido. Pilha agora:

return elemento_removido

def peek(self):
"""
Operação PEEK: Retorna o elemento do topo sem removê-lo.

Retorna:
- O elemento do topo, ou None se a pilha estiver vazia

Esta operação é útil quando queremos apenas "espiar" o topo

da pilha sem modificá-la.
"""

print(" ❌
if self.esta_vazia():
PEEK: Pilha está vazia!")
return None

print(f"👁️
elemento_topo = [Link][-1] # Último elemento (índice -1)
PEEK: Elemento no topo é '{elemento_topo}'")
return elemento_topo

def esta_vazia(self):
"""
Verifica se a pilha está vazia.

Retorna:
- True se vazia, False caso contrário
"""
vazia = len([Link]) == 0
if vazia:
print("
return vazia
📊Status: Pilha está VAZIA")

def esta_cheia(self):
"""
Verifica se a pilha está cheia (apenas se há limite de capacidade).

Retorna:
- True se cheia, False caso contrário
"""
if self.capacidade_maxima is None:
 return False # Sem limite, nunca está cheia

cheia = len([Link]) >= self.capacidade_maxima

if cheia:
print(f" 📊Status: Pilha está CHEIA (capacidade:
{self.capacidade_maxima})")
return cheia

def tamanho(self):
"""
Retorna o número de elementos na pilha.

Retorna:
- Inteiro representando o tamanho atual da pilha
"""

print(f"
return tam
📏
tam = len([Link])
Tamanho atual da pilha: {tam}")

def limpar(self):
"""
Remove todos os elementos da pilha.

Esta operação é útil quando queremos "resetar" a pilha.

"""

print("🧹
[Link]()
Pilha limpa! Todos os elementos foram removidos.")

def mostrar_pilha(self):
"""
Exibe a pilha de forma visual, mostrando o topo claramente.

Esta função é útil para visualizar o estado atual da pilha.

"""

print("
return
📚
if self.esta_vazia():
Pilha: [ VAZIA ]")

print("
print("
📚 ┌─────────────┐")
Estado atual da pilha:")

# Mostra elementos do topo para a base

for i in range(len([Link]) - 1, -1, -1):
elemento = [Link][i]
if i == len([Link]) - 1:
print(f" │ {elemento:^9} │ ← TOPO")
else:
print(f" │ {elemento:^9} │")

print(" └─────────────┘")
print(" BASE")

Demonstração Prática

Vamos executar o código e ver como ele se comporta:

 🎯 DEMONSTRAÇÃO: Implementação de Pilha com Array/Vetor
============================================================

📋
✅ PASSO 1: Criando uma pilha com capacidade máxima de 5 elementos

📚 Pilha criada com capacidade máxima: 5

Pilha: [ VAZIA ]

📋
📥 PASSO 2: Adicionando elementos na pilha

📚 PUSH: 'A' adicionado. Pilha agora: ['A']

Estado atual da pilha:
┌─────────────┐
│ A │ ← TOPO
└─────────────┘
BASE

📥
📚 ┌─────────────┐
PUSH: 'B' adicionado. Pilha agora: ['A', 'B']
Estado atual da pilha:

│ B │ ← TOPO
│ A │
└─────────────┘
BASE

...

📋
📊 PASSO 6: Tentando exceder a capacidade

❌ Status: Pilha está CHEIA (capacidade: 5)

ERRO: Não é possível empilhar 'H'. Pilha está cheia!

📋
📤 PASSO 7: Esvaziando a pilha completamente
POP: 'G' removido. Pilha agora: ['A', 'B', 'E', 'F']
...

📋
📊 PASSO 8: Tentando remover de pilha vazia

❌ Status: Pilha está VAZIA

ERRO: Não é possível desempilhar. Pilha está vazia!

🎉 Demonstração concluída!

Exercícios Práticos

Para fixar o conhecimento, aqui estão alguns exercícios que você pode resolver
usando a classe PilhaArray :

# Exercício 1: Pilha de números e soma

# Crie uma pilha de números, adicione alguns valores e depois calcule a soma de
todos eles, removendo-os da pilha.

# Exercício 2: Verificador de palíndromo

# Crie uma função que recebe uma palavra e, usando uma pilha, verifica se ela é
um palíndromo (lê-se da mesma forma de trás para frente).
HANDS-ON: Implementação de Pilha com Lista Ligada

Agora, vamos explorar a implementação de uma pilha usando uma abordagem mais
avançada: a lista ligada. Esta implementação nos ajudará a entender melhor como os
ponteiros e a alocação dinâmica de memória funcionam.

A Classe No

Primeiro, precisamos de uma classe para representar cada nó da nossa lista:

class No:
"""
Classe que representa um nó (node) da lista ligada.
"""
def __init__(self, dados):
[Link] = dados # Valor armazenado no nó
[Link] = None # Ponteiro para o próximo nó (inicialmente
None)

O Código Completo da Pilha

Abaixo está o código completo da nossa classe PilhaListaLigada :

 class PilhaListaLigada:
"""
Implementação de uma Pilha usando Lista Ligada.
"""
def __init__(self):
[Link] = None # Ponteiro para o nó do topo (pilha vazia = None)
[Link] = 0 # Contador de elementos

def push(self, elemento):

"""
Operação PUSH: Adiciona um elemento no topo da pilha.
"""
novo_no = No(elemento)
novo_no.proximo = [Link]
[Link] = novo_no
[Link] += 1

def pop(self):
"""
Operação POP: Remove e retorna o elemento do topo.
"""
if self.esta_vazia():
return None

elemento_removido = [Link]
[Link] = [Link]
[Link] -= 1
return elemento_removido

# ... (outros métodos como peek, esta_vazia, etc.)

Demonstração Prática

Vamos ver como essa implementação se comporta na prática:

🎯 DEMONSTRAÇÃO: Implementação de Pilha com Lista Ligada
=================================================================

📋
✅ PASSO 1: Criando uma pilha vazia

📚 Pilha (Lista Ligada) criada - inicialmente vazia

Pilha: [ VAZIA ]

📋 PASSO 2: Adicionando elementos na pilha

🔄
🔗 Novo
Iniciando PUSH de 'Primeiro'...
Nó criado com dados: 'Primeiro'

📥 Tamanho
nó 'Primeiro' é o primeiro da pilha
PUSH concluído: 'Primeiro' adicionado no topo

📚 TOPO atual: 1
Estado atual da pilha (Lista Ligada):

↓
┌─────────────┐
│ Primeiro │ ← TOPO
└─────────────┘
│
NULL
BASE

...

📋
🔍 Ponteiro
PASSO 3: Visualizando a estrutura interna
Estrutura interna da lista ligada:
topo aponta para: Nó(Quarto)
Nó 0: dados='Quarto', próximo=Nó(Terceiro)
Nó 1: dados='Terceiro', próximo=Nó(Segundo)
Nó 2: dados='Segundo', próximo=Nó(Primeiro)
Nó 3: dados='Primeiro', próximo=None

...

🎉 Demonstração concluída!
Comparativo: Array vs. Lista Ligada

Implementação com
Característica Implementação com Array
Lista Ligada

Gerenciamento de Estático (em algumas linguagens) ou

Dinâmico, nó a nó
Memória dinâmico com realocação

Maior (ponteiros em
Uso de Memória Menor (sem ponteiros extras)
cada nó)

Lento (acesso
Velocidade de Acesso Rápido (acesso direto por índice)
sequencial)

Velocidade de
Rápido (O(1) amortizado) Rápido (O(1))
Inserção/Remoção

Complexidade de
Mais simples Mais complexa
Implementação

Exercícios Avançados

Para aprofundar seus conhecimentos, tente resolver estes exercícios usando a

PilhaListaLigada :

# Exercício 1: Calculadora com histórico

# Crie uma classe Calculadora que usa uma pilha para armazenar o histórico de
operações, permitindo a função "desfazer".

# Exercício 2: Verificador de expressões balanceadas (avançado)

# Crie uma função que verifica se uma expressão contém parênteses, colchetes e
chaves balanceados (ex: "([{}])").

Conclusão

Neste material, exploramos em detalhes a estrutura de dados pilha, desde seus

conceitos fundamentais até a implementação prática em Python de duas formas
diferentes: com arrays e com listas ligadas. Vimos como o princípio LIFO rege o
funcionamento das pilhas e como ele é útil em diversas aplicações do mundo real.

Esperamos que este material tenha sido claro, didático e que tenha ajudado você a
consolidar seus conhecimentos em estruturas de dados. Continue praticando,
explorando e construindo para se tornar um programador cada vez mais completo!