Stack

Uma stack segue a regra:

LIFO — Last In, First Out

O último elemento a entrar é o primeiro a sair. Uma boa analogia é uma pilha de pratos. Quando colocamos um prato novo, ele vai para o topo da pilha. Quando retiramos um prato, também pegamos o que está no topo.

Ou seja, todas as operações acontecem apenas no topo da pilha.

Embora stacks frequentemente sejam implementadas usando arrays, o mais importante não é a estrutura subjacente, mas as regras de acesso aos dados.

Em uma stack existem apenas duas operações principais:

• push → inserir um elemento no topo
• pop → remover o elemento do topo

Também é comum existir uma operação de leitura:

• peek → visualizar o elemento do topo sem removê-lo

Essas restrições tornam a estrutura simples e eficiente.

Inserir um elemento em uma stack significa colocá-lo no topo da pilha.

Exemplo:

Após um push(40):

Nenhum elemento precisa ser deslocado, pois sempre inserimos no final da estrutura.

Complexidade: O(1)

A remoção também ocorre apenas no topo da stack.

Exemplo:

Após um pop():

O último elemento é removido diretamente, sem necessidade de mover outros elementos.

Complexidade: O(1)

A operação peek permite visualizar o elemento que está no topo da pilha sem removê-lo.

Exemplo:

peek() retorna:

Como o acesso é direto ao topo da estrutura:

Complexidade: O(1)

Stacks não são projetadas para busca eficiente.

Se for necessário procurar um elemento dentro da pilha, é preciso percorrer os elementos um a um, normalmente do topo até a base.

No pior caso, todos os elementos precisam ser verificados.

Complexidade: O(N)

Por esse motivo, stacks são utilizadas em cenários onde o acesso ocorre sempre no topo, e não quando é necessário localizar elementos no meio da estrutura.