Pilha
C++ KotlinDefinição
A pilha é uma estrutura de dados para conter objetos obedecendo a ordem de entrada LIFO (Last In First Out). Isso significa que o primeiro elemento a ser adicionado sera o último elemento a sair. Em sua forma mais clássica ela implementa as seguintes operações:
- Top : essa operação retorna o último elemento adicionado a pilha, em alguns casos pode ser também implementada como Peek
- Push: a operação adiciona um elemento na última posição da pilha
- Pop : essa operação remove um elemento da última posição da pilha. Em algumas implementações, a operação remove e retorna o elemento que removeu
Complexidades
| Operação | Caso médio | Pior caso |
|---|---|---|
| Espaço | O(n) | O(n) |
| Busca | O(n) | O(n) |
| Top | O(1) | O(1) |
| Push | O(1) | O(1) |
| Pop | O(1) | O(1) |
Implementação
A pilha pode ser implementada de duas maneiras: através de um vetor estático com tamanho fixo onde é armazenado o índice da posição do último elemento adicionado (nesse caso a pilha tem uma capacidade fixa), ou através de uma lista encadeada (nesse tipo de implementação a capacidade da pilha é variável).
Ao se implementar com uma lista encadeada é necessário realizar algumas modifiações e manter um ponteiro para a primeira posição da lista de forma que a inserção e a remoção mantenham a complexidade O(1). Na estrutura da lista vamos adicionar um elemento no ínicio e na hora de remover também removemos o elemento do início. A diferença da fila para a pilha na implementação usando uma lista é que na fila se insere o elemento na última posição e é preciso manter um ponteiro para a mesma.