There are things unclear in your question, but lets assume some things first.
If you want to deploy a caching mechanism you need consider the size of the cache and in what size chunks you want to cache the data.
Secondly, you need to understand the temporal and spatial locality of your data. For example, if you have a database which has a primary key and the results are sorted by the same in your website, you could prefetch some extra data along with the request to minimize the calls to your server. However if it is non-indexed data, something like hashes, then it would depend on the request, if the user scrolls down /up you may have cache hits and if its a random request you may not.
Thirdly, based on what you asked it seems like a case of the optimal page replacement algorithm(feel free to correct me), which is non implementable. You can never predict what data is going to be requested, which is why we have the locality of reference to help reach near optimality in most cases. You will have to decide cache eviction/cache replacement policy(Why is this needed? If we assume what you want is possible then eventually your whole database is going to be stored on the cache, then why would you store it on the server in the first place?). Stack based algorithms are generally used like LRU, LFU and its variations. At some point your cache will fill up and you will need to decide which existing cached data to remove.
You only need to worry about all these if you yourself are going to implement a caching mechanism. For data structures you can use anything from a simple array to a self balancing tree to a hashtable. Since caching is all about reducing the retrieval time, you need to understand that only the complexity of operations on data structures don't matter. Sometimes an operation might have a higher growth rate but may be faster at runtime.
Look up how in memory databases work, for example Redis.
