Resumo de Pilha (stack)
Pilha (Stack): Entenda a Estrutura de Dados LIFO e Suas Aplicações
Pilha: Uma Estrutura de Dados LIFO
No vasto universo da ciência da computação, as estruturas de dados são ferramentas essenciais para organizar e armazenar informações de maneira eficiente. Entre elas, a pilha (do inglês, stack) destaca-se por sua simplicidade e ubiquidade em diversas aplicações. Uma pilha é uma estrutura de dados linear abstrata que opera sob um princípio rigoroso: LIFO, que significa "Last-In, First-Out" (Último a Entrar, Primeiro a Sair).
Imagine uma pilha de pratos: o último prato que você coloca em cima é o primeiro que você retira quando precisa de um. Essa analogia simples captura a essência do funcionamento de uma pilha computacional.
Princípio LIFO (Last-In, First-Out)
O princípio LIFO é a característica definidora de uma pilha. Ele dita que o elemento que foi adicionado mais recentemente à pilha será o primeiro a ser acessado ou removido. Isso contrasta com outras estruturas de dados, como a fila (queue), que segue o princípio FIFO (First-In, First-Out). A pilha possui um único ponto de acesso, conhecido como "topo" (top), onde todas as operações de inserção e remoção ocorrem.
LIFO (Last-In, First-Out): O elemento inserido por último é o primeiro a ser removido.
Operações Fundamentais da Pilha
Uma pilha suporta um conjunto limitado de operações, o que contribui para sua eficiência e simplicidade. As duas operações mais importantes são push e pop.
Operação Push (Empilhar)
A operação push é utilizada para adicionar um novo elemento ao topo da pilha. Quando um elemento é empilhado, ele se torna o novo topo da pilha. Se a pilha tiver uma capacidade máxima definida (como em uma implementação baseada em array), a tentativa de empilhar um elemento em uma pilha já cheia resultará em uma condição de "estouro de pilha" (stack overflow), que é um erro. É crucial verificar se a pilha não está cheia antes de realizar um push.
Exemplo de Push: Considere uma pilha inicialmente vazia.
push(A): A pilha agora contém $[A]$. O topo é $A$.push(B): A pilha agora contém $[A, B]$. O topo é $B$.push(C): A pilha agora contém $[A, B, C]$. O topo é $C$.
Operação Pop (Desempilhar)
A operação pop é utilizada para remover o elemento que está no topo da pilha. O elemento removido é geralmente retornado pela operação. Após a remoção, o elemento que estava imediatamente abaixo do topo se torna o novo topo. Se a pilha estiver vazia e uma operação pop for tentada, ocorre uma condição de "pilha vazia" (stack underflow), que também é um erro. É importante verificar se a pilha não está vazia antes de realizar um pop.
Exemplo de Pop (continuando do exemplo anterior):
pop(): Remove $C$. A pilha agora contém $[A, B]$. O topo é $B$. O valor retornado é $C$.pop(): Remove $B$. A pilha agora contém $[A]$. O topo é $A$. O valor retornado é $B$.pop(): Remove $A$. A pilha agora está vazia $[ ]$. Não há topo. O valor retornado é $A$.
Outras Operações Comuns
Além de push e pop, outras operações úteis incluem:
peek()outop(): Retorna o elemento no topo da pilha sem removê-lo. Útil para inspecionar o próximo elemento a ser desempilhado.isEmpty(): Retorna verdadeiro se a pilha estiver vazia, falso caso contrário.isFull(): Retorna verdadeiro se a pilha estiver cheia (aplicável a implementações com capacidade fixa), falso caso contrário.
Implementação da Pilha com Array
Uma das formas mais diretas de implementar uma pilha é utilizando um array (vetor) estático ou dinâmico. Nesta abordagem, o array armazena os elementos da pilha, e uma variável inteira, geralmente chamada de topo ou topIndex, rastreia a posição do elemento mais recente no array. O topIndex geralmente aponta para o índice do último elemento adici
Regista-te para o resumo completoJá tem uma conta? Entrar
Estrutura de Dados Pilha
Klíčová slova: Estrutura de Dados Pilha, Visualização de Pilhas
Klíčové pojmy: A pilha é uma estrutura de dados LIFO (Last-In, First-Out), onde o último elemento adicionado é o primeiro a ser removido., O único ponto de acesso em uma pilha é o seu topo (top)., A operação `push` adiciona um elemento ao topo da pilha., A operação `pop` remove e retorna o elemento do topo da pilha., Outras operações comuns incluem `peek()` (ver o topo sem remover), `isEmpty()` (verificar se está vazia) e `isFull()` (verificar se está cheia)., Um *stack overflow* ocorre ao tentar adicionar a uma pilha cheia; um *stack underflow* ocorre ao tentar remover de uma pilha vazia., A implementação mais comum de uma pilha é com um array, utilizando um `topIndex` para rastrear o topo., Todas as operações básicas da pilha (`push`, `pop`, `peek`, `isEmpty`, `isFull`) possuem complexidade de tempo constante $O(1)$., Pilhas são usadas em funcionalidades 'desfazer', histórico de navegação, pilhas de chamadas de função e verificação de parênteses., Acesso aleatório a elementos que não estão no topo não é permitido em uma pilha.