Can you move stuff around in your array? Something I've done in the past to keep items packed (when the exact sequence is irrelevant), is whenever you delete something out of the middle somewhere, relocate the last element of the array into the empty slot. This keeps the storage tight, so you can always add a new element at the end in O(1) time, without worrying about all kinds of holes.
Another thing you can do is add a field to the struct (assuming your array is an array of structs) to implement a singly linked list for the "empties" in the array, in this case, the new field is the array index of the next element in the list. Now, it's a singly linked list, but you use it like a stack; always add to/remove from the head end. You keep another int that indexes the first element in this free-elements list, so you can always allocate an empty slot in O(1). Whenever you free a slot, you set its next-element index to the current head of the free list, and change the head to index the just deallocated element.