Tutorial de estrutura de dados de pilha Python
Implemente uma pilha LIFO em Python. Execute nosso exemplo de código de pilha interativo para dominar os limites de push, pop, peek e capacidade.
Visão geral
Uma pilha é uma estrutura de dados linear que segue o princípio Last-In, First-Out (LIFO). Isto significa que o último elemento adicionado à pilha é o primeiro a ser removido, semelhante a uma pilha de pratos.
A pilha suporta duas operações principais: push (adiciona um item ao topo) e pop (remove o item adicionado mais recentemente). Além disso, uma operação peek ou top permite inspecionar o elemento superior sem removê-lo.
Em Python, as pilhas podem ser facilmente construídas usando uma lista com os métodos `.append()` e `.pop()`, ou usando o objeto `collections.deque` que oferece operações otimizadas de fila dupla em tempo O(1).
Saída de código e execução
Uma implementação de Stack personalizada usando a estrutura de lista do Python para emular funções push, pop e peek.
class Stack:
def __init__(self):
self.items = []
def is_empty(self):
return len(self.items) == 0
def push(self, item):
self.items.append(item)
print(f"Pushed: {item}")
def pop(self):
if self.is_empty():
return "Underflow: Stack is empty"
popped = self.items.pop()
print(f"Popped: {popped}")
return popped
def peek(self):
if self.is_empty():
return "Stack is empty"
return self.items[-1]
def size(self):
return len(self.items)
# Initialize stack
stack = Stack()
stack.push("Apples")
stack.push("Bananas")
stack.push("Cherries")
print(f"Current Stack Size: {stack.size()}")
print(f"Top Element (Peek): {stack.peek()}")
stack.pop()
print(f"Stack after Pop: {stack.items}")Pushed: Apples
Pushed: Bananas
Pushed: Cherries
Current Stack Size: 3
Top Element (Peek): Cherries
Popped: Cherries
Stack after Pop: ['Apples', 'Bananas']Implementação passo a passo
- Gerenciando funções de desfazer em sistemas de software
- Análise de sintaxe e verificação de parênteses em compiladores
- Rastreando pilhas de chamadas de execução durante recursão em mecanismos
Perguntas frequentes
Por que o collections.deque é preferido a uma lista normal para Stacks?
Embora as listas sejam convenientes, elas são matrizes dinâmicas subjacentes. Quando eles são redimensionados, a realocação de memória pode levar tempo O(n). O objeto deque usa uma arquitetura de lista duplamente vinculada, garantindo O(1) pushes e pops.
As pilhas podem transbordar em Python?
Uma classe de pilha padrão em Python usando matrizes de lista crescerá até consumir toda a memória disponível do sistema. A pilha de recursão em Python, entretanto, tem um limite padrão (normalmente 1000) para evitar que loops infinitos travem o interpretador.
Tópicos Relacionados
Domine as operações da fila FIFO em Python. Execute e execute nosso exemplo de fila interativa apresentando métodos de enfileiramento e desenfileiramento.
Implementação de lista vinculada individualmente em PythonAprenda como implementar uma lista vinculada individualmente em Python. Explore a alocação dinâmica de memória, operações de nó, inserção, passagem e exclusão.