Finding lower bounds for data structures with non-standard interfaces Consider the problem of designing a data structure that provides the interface functions  $\rm{pop}, \rm{push}, \rm{findmin}$, all running in constant time. This problem may be solved by (e.g.) having the $\rm{push}$ method compute the new minimum as well, and place it on the stack together with the pushed element.

Is there any systematic approach to determining lower bounds (of time and space complexity) for data structures exposing a given set of interfaces? E.g. $\rm{push,pop,sort, insertAtIndex}$? Can you provide links to relevant literature?
Data structure lower bounds is a full-fledged area in theory of computation. The main model of computation on which the lower bounds are proved is the cell probe model, which counts the number of memory accesses, but for which computation is free. For an overview of how things stood in 2008, you can take a look at Mihai Pătraşcu's thesis. Tragically, Pătraşcu died from brain cancer in 2012 at the age of 29.