Datastructures existen en PHP hace tiempo, son parte del
SPL (incluso una implementacion de stack...), cuando utilizar cual depende de lo que necesites, basta con que mires un poco cada clase para ver donde la puedes aplicar, frameworks como Zend 2 lo utilizan extensivamente.