What to benchmark on my library data structure

I have written a data structure, for example a Stack, which I want to provide as a library.

What benchmarks would be interesting for it ? If regular users are comparing my library with another one offering the same Stack data structure, what benchmark comparisons would they like to see ?