Pilha (Stack)

Uma pilha é uma estrutura de dados linear que segue o princípio LIFO (Last In, First Out), onde o último elemento inserido é o primeiro a ser removido.

Isso contrasta com uma estrutura de dados semelhante, a fila (queue), onde o primeiro elemento inserido é o primeiro a ser removido (FIFO).

Enquanto uma fila se assemelha a uma linha de pessoas esperando por atendimento, uma pilha pode ser comparada a uma pilha de pratos, onde o último prato colocado no topo é o primeiro a ser retirado.

Estrutura

Uma pilha pode ser visualizada como uma sequência vertical de elementos, onde a inserção e a remoção de elementos ocorrem na mesma extremidade, conhecida como topo. Esse comportamento segue o princípio Last-In-First-Out (LIFO), garantindo que o último elemento adicionado seja o primeiro a ser removido.

Implementação em Python e TypeScript

Pilhas podem ser implementadas de várias maneiras, sendo as mais comuns baseadas em arrays ou listas dinâmicas, dependendo da linguagem de programação utilizada.

Arrays oferecem uma implementação simples e eficiente, permitindo o acesso rápido ao topo da pilha, mas podem exigir redimensionamento conforme o número de elementos cresce.

Em linguagens como Python, listas são frequentemente usadas devido à sua flexibilidade e suporte nativo a operações de inserção e remoção no final da lista.

Outra abordagem menos comum, mas possível, é a implementação utilizando listas encadeadas, onde cada elemento (nó) aponta para o próximo. Essa abordagem pode ser útil em situações onde a alocação dinâmica de memória é preferível ou onde o tamanho da estrutura não é conhecido antecipadamente.

Para ver o código completo em Python e TypeScript, você pode acessar o repositório no GitHub.

O repositório contém exemplos práticos e código completo para ajudar na compreensão e implementação dessa estrutura de dados.

Casos de Uso

Esta estrutura de dados é amplamente utilizada em vários cenários devido à sua natureza LIFO:

• Recursão: Pilhas são utilizadas para gerenciar chamadas recursivas em linguagens de programação, armazenando o estado de cada chamada até que seja resolvida.
• Desfazer/Refazer em Aplicativos: Pilhas permitem o armazenamento de ações realizadas pelo usuário, possibilitando a funcionalidade de desfazer e refazer operações.

Operações

Uma pilha suporta várias operações que permitem a manipulação e recuperação de dados:

• Inserção (Push): Adiciona um novo elemento ao topo da pilha.
• Remoção (Pop): Remove o elemento do topo da pilha.
• Topo (Peek): Retorna o elemento no topo da pilha sem removê-lo.
• Tamanho (Size): Retorna o número de elementos presentes na pilha.

Complexidade de Tempo

• Inserção (Push): O(1) – Adicionar um elemento no topo da pilha leva tempo constante.
• Remoção (Pop): O(1) – Remover o elemento do topo da pilha leva tempo constante.
• Topo (Peek): O(1) – Acessar o elemento do topo da pilha leva tempo constante.
• Tamanho (Size): O(1) – Verificar o tamanho da pilha leva tempo constante.

Complexidade de Espaço

A complexidade de espaço de uma é O(n), onde n é o número de elementos na pilha. Cada elemento ocupa espaço adicional na memória, seja em um array, lista dinâmica ou uma lista encadeada.

Conclusão

As pilhas são uma estrutura de dados fundamental, com uma ampla gama de aplicações na ciência da computação. Compreender como pilhas funcionam e como implementar suas operações básicas é essencial para resolver uma variedade de problemas em engenharia de software e desenvolvimento de sistemas.