6.1 Definição de pilha e suas propriedades
Pilha — é uma estrutura de dados abstrata, que representa uma coleção de elementos organizada pelo princípio "último a entrar — primeiro a sair" (Last In, First Out, LIFO). Você pode imaginar uma pilha como uma pilha de livros: o último livro adicionado está no topo da pilha e será removido/pego primeiro.
Propriedades da pilha:
- LIFO (Last In, First Out): O último elemento adicionado é o primeiro a ser extraído.
- Operações limitadas: Na pilha, são suportadas apenas adição (push), remoção (pop) e visualização (peek) do elemento no topo.
- Acesso unidirecional: O acesso aos elementos é possível apenas a partir do topo da pilha.
- Facilidade de implementação: Uma pilha pode ser facilmente implementada usando um array ou lista encadeada.
- Gerenciamento de memória: Dados ou estados temporários podem ser armazenados e extraídos na ordem inversa de sua adição.
Princípio de funcionamento LIFO:
- Adição de elemento (push): Um novo elemento é adicionado no topo da pilha.
- Remoção de elemento (pop): O último elemento adicionado é removido do topo da pilha.
- Visualização do topo (peek): Permite ver o elemento no topo da pilha sem removê-lo.
Os elementos da pilha são adicionados e removidos de um lado, chamado topo. Assim, o último elemento adicionado sempre acaba no topo e será removido primeiro.
6.2 Principais operações
Principais operações: push, pop, peek
Operação push: Adiciona um novo elemento no topo da pilha.
Complexidade temporal: O(1).
Exemplo de emulação de pilha em Python usando a classe list:
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
print(stack) # Saída: [10, 20]
Operação pop: Remove e retorna o elemento do topo da pilha.
Complexidade temporal: O(1).
Exemplo de emulação de pilha em Python usando a classe list:
stack = []
stack.append(10) # push 10
stack.append(20) # push 20
top_element = stack.pop() # pop
print(top_element) # Saída: 20
print(stack) # Saída: [10]
Operação peek: Retorna o elemento no topo da pilha sem removê-lo.
Complexidade temporal: O(1).
Exemplo de implementação:
stack = []
stack.append(10) # push 10
top_element = stack[-1] # peek
print(top_element) # Saída: 10
6.3 Exemplos de uso de pilha
Vamos dar alguns exemplos de uso da pilha:
Gerenciamento de chamadas de função
No Python, a pilha é usada para rastrear funções durante a execução do programa. Toda vez que uma função é chamada, seu endereço de retorno e variáveis locais são colocados na pilha. Quando a função termina a execução, o controle retorna para a função que a chamou, e os dados são extraídos da pilha.
Exemplo de uso da pilha de chamadas:
Neste exemplo, as chamadas recursivas da função factorial usam a pilha de chamadas para armazenar o estado de cada chamada até que a condição base seja alcançada (n == 1).
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n - 1)
print(factorial(5)) # Saída: 120
Desfazer operações (Undo)
A pilha é usada para implementar a função de desfazer ações em editores de texto e outros aplicativos. Quando o usuário realiza uma ação, ela é salva na pilha. Ao realizar a operação Undo, a última ação é extraída da pilha e desfeita.
Exemplo de uso de pilha para desfazer operações:
class TextEditor:
def __init__(self):
self.text = ""
self.history = []
def type(self, text):
self.history.append(self.text)
self.text += text
def undo(self):
if self.history:
self.text = self.history.pop()
# Exemplo de uso:
editor = TextEditor()
editor.type("Hello")
editor.type(" World")
print(editor.text) # Saída: "Hello World"
editor.undo()
print(editor.text) # Saída: "Hello"
editor.undo()
print(editor.text) # Saída: ""
GO TO FULL VERSION