不定長の1次元配列を作りたいのですがうまく出来ません。

その配列には要素を加えたり、取り除いたりしたいのですが、、任意の要素を動かすわけではなく、スタックのように一番最後のものだけを加えるか取り除くかすることを想定しています。

最初から固定的な配列をメモリに確保するともともとのサイズ以上の要素を入れたい場合たとえメモリが余っていてもダメです。ちょっとしか要素を使わなかった場合にはメモリがもったいないです。

かと言ってリンクドリスト構造にすると例えば100番目の要素にアクセスするのに100個の要素を辿る必要がありオーバーヘッドが大きいです。

要素を加える時と取り除く時に新たな配列を作り、古い配列の内容を全コピーした後、古い配列を削除するというのも考えたのですが、やはりオーバーヘッドが大きいし、メモリがガベージだらけになってしまうと思います。

どうやればいいのでしょうか？