Come scrivere un algoritmo che raddoppia la pila per ospitare nuovi membri in cui la spinta è in tempo costante nel peggiore dei casi?

Question

Ci viene fornito l'algoritmo che utilizza Stack per archiviare i dati (Stack è implementato tramite un array). Quando lo stack è pieno, l'algoritmo fa quanto segue:

1. Crea un nuovo array doppio di quello originale.
2. Copia tutti gli elementi del vecchio array al nuovo array, preservando l'ordine.

Regola l'algoritmo in modo che l'inserimento di un nuovo elemento sia nel tempo costante nel peggiore dei casi.

La limitazione qui è che dobbiamo usare gli array come implementazione dello stack.

Il caso peggiore è quando, ad esempio, il vecchio stack di dimensioni $ n $ è pieno e ora dobbiamo inserire un nuovo elemento. Quindi creiamo un nuovo stack $ s_2 $ di taglia $ 2n $ e vogliamo inserire il nuovo elemento a $ s_2 [n+1] $.

Sono bloccato con il requisito del tempo costante, apprezzerei qualsiasi suggerimento sulla giusta direzione.

NB: Sono consapevole che il titolo è un po 'generale, non riesco a pensare a qualcosa di più specifico, se sai in quale categoria di algoritmi rientra per favore fammelo sapere e modificherò l'intestazione.