Filas e Pilhas - Estrutura de dados

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???