Data structure for efficient searching, when insertions and removals are only one-sided
Store the elements as a sequence, sorted by increasing timestamp.  Use binary search to find the location where $\tilde{t}$ would occur if it were in the array; then you can easily find the two neighboring elements.  Finding the two neighboring elements can be done in $O(\lg n)$ time.

You'll also need to be able to append to the end of the sequence and delete from the beginning.  Thus, basically you need a queue.

There are standard constructions for a queue.  For instance, you can store them in an array, with amortized $O(1)$-time insert and delete operations.  Basically, you have an array for the elements of the sequence, and a start index (for the beginning of the sequence) and an end index (for the end of the sequence).  To delete from the beginning, increment the start index.  To add to the end, increment the end index; if this runs past the end of the existing array, allocate a new array of double the size and copy into the new array.

Alternatively: you can store the elements in a balanced binary tree.  This will achieve worst-case $O(\lg n)$-time for all operations.