Olá!
Eu tenho uma dúvida com relação a complexidade de se remover um dado qualquer em um fila ou pilha.
Eu pensei o seguinte:
Se a minha pilha tem os seguintes números
1 (topo da pilha)
2
3
4
5
e desejo remover o número 3, pensei no seguinte:
Crio uma nova pilha e vou removendo até achar o numero 3:
2 (topo da segunda pilha)
1
Quando eu removo o número 3, verifico que esse é o valor desejado. Depois, desempilho a pilha nº 2, colocando os valores na pilha 1:
1
2
4
5
A complexidade de tempo seria O(n), no pior caso e O(1) no melhor caso.
A complexidade de espaço seria 2n, no pior caso, pois teria que criar uma outra pilha (2).
Para a fila:
inicio -> 1 -> 2 -> 3 -> 4 -> 5 -> fim
Insiro sempre no início e removo sempre no final.
Se eu quero remover o número 3, faço:
removo 5:
Não é 3.
Copio para a mesma fila, fazendo inicio apontar para 5.
Vou fazendo isso até chegar no número 3…
Achei o 3.
Removo o número 3. Não o coloco na fila novamente.
Continuo a remover os valores da fila e colocando no início, até dar uma volta completa na fila.
Fila ficará:
inicio -> 1 -> 2 -> 4 -> 5 -> fim
Complexidade de tempo: O(n), para achar o valor.
Complexidade de espaço: n, pois uso a mesma fila.
Está certo o que disse???