Pilha (Stack)

Uma pilha (ou stack) é uma estrutura de dados linear que segue a abordagem LIFO (Last In, First Out), ou seja, o último elemento inserido é o primeiro a ser removido. As operações fundamentais de uma pilha são push (inserir um elemento no topo) e pop (remover o elemento do topo). A seguir, exploraremos a história, funcionamento, complexidade, implementação e comparações, além de analisar as pilhas efêmeras e persistentes.

História e Origem

O conceito de pilha foi introduzido na computação na década de 1950 e tornou-se um componente fundamental em linguagens de programação e sistemas operacionais. Um dos primeiros usos notáveis foi na execução de sub-rotinas e gerenciamento de memória em computadores de primeira geração.

Aplicações

Pilhas são amplamente utilizadas em várias aplicações, como:

Avaliação de expressões aritméticas
Implementação de chamadas de função e recursão
Navegação entre páginas da web (histórico de navegação)
Desfazer/refazer ações em editores de texto

Funcionamento

A pilha opera com duas principais operações:

push(element): Adiciona um elemento ao topo da pilha.
pop(): Remove e retorna o elemento do topo da pilha.

Exemplo de funcionamento:

push(1) -> Pilha: [1]
push(2) -> Pilha: [1, 2]
pop() -> Retorna: 2, Pilha: [1]

Complexidade

As operações de push e pop em uma pilha têm complexidade O(1), pois envolvem apenas a adição ou remoção de elementos do topo da estrutura. O uso de memória é linear, O(n), onde n é o número de elementos na pilha.

Implementação

Implementação em Python de uma Pilha Efêmera

Python

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        """Add an item to the top of the stack."""
        self.items.append(item)

    def pop(self):
        """Remove and return the top item of the stack."""
        if not self.is_empty():
            return self.items.pop()
        raise IndexError("pop from empty stack")

    def is_empty(self):
        """Check if the stack is empty."""
        return len(self.items) == 0

    def peek(self):
        """Return the top item of the stack without removing it."""
        if not self.is_empty():
            return self.items[-1]
        raise IndexError("peek from empty stack")

    def size(self):
        """Return the number of items in the stack."""
        return len(self.items)

# Example of usage:
stack = Stack()
stack.push(1)
stack.push(2)
print(stack.pop())  # Output: 2
print(stack.peek())  # Output: 1

Pilha Efêmera vs. Pilha Persistente

Pilha Efêmera

A pilha efêmera é a implementação tradicional onde o estado é mutável. Cada operação de push e pop modifica o estado da pilha diretamente, e a pilha não mantém histórico de estados anteriores.

Pilha Persistente

A pilha persistente, por outro lado, é uma estrutura de dados imutável. Cada operação retorna uma nova versão da pilha, mantendo o estado anterior intacto. Isso é útil em contextos onde é necessário rastrear versões anteriores ou operar de maneira funcional. Em uma implementação de pilha persistente, cada elemento da pilha mantém um ponteiro para a versão anterior da pilha, permitindo a criação de uma nova instância em cada operação de push e pop.

Implementação em Python de uma Pilha Persistente

Python

class PersistentStack:
    def __init__(self, head=None, tail=None):
        self.head = head
        self.tail = tail

    def push(self, item):
        """Return a new stack with the item added to the top."""
        return PersistentStack(item, self)

    def pop(self):
        """Return a new stack without the top item, and the top item."""
        if self.is_empty():
            raise IndexError("pop from empty stack")
        return self.tail, self.head

    def is_empty(self):
        """Check if the stack is empty."""
        return self.head is None

    def peek(self):
        """Return the top item of the stack without removing it."""
        if self.is_empty():
            raise IndexError("peek from empty stack")
        return self.head

    def size(self):
        """Return the number of items in the stack."""
        count = 0
        current = self
        while not current.is_empty():
            count += 1
            current = current.tail
        return count

# Example of usage:
stack = PersistentStack()
new_stack = stack.push(1)
another_stack = new_stack.push(2)
final_stack, top = another_stack.pop()
print(top)  # Output: 2
print(final_stack.peek())  # Output: 1

Comparações

Vantagens das Pilhas Efêmeras:

Mais simples e eficiente em termos de memória e velocidade.
Adequadas para a maioria das aplicações práticas.

Vantagens das Pilhas Persistentes:

Úteis em programação funcional e sistemas que requerem imutabilidade.
Facilita o suporte a paralelismo.

Melhores Práticas

Utilize pilhas efêmeras para operações simples e de alto desempenho.
Adote pilhas persistentes quando for necessário manter versões anteriores, trabalhar em um contexto funcional ou facilitar o paralelismo.

Referências

Knuth, D. E. (1997). The Art of Computer Programming, Volume 1: Fundamental Algorithms.
Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms.
Okasaki, C. (1998). Purely Functional Data Structures.

Conclusão

A pilha é uma estrutura de dados fundamental com diversas aplicações em computação. Compreender as diferenças entre pilhas efêmeras e persistentes permite escolher a melhor abordagem para cada contexto, equilibrando simplicidade, desempenho e funcionalidade.

RESUMO