what i mean is that the implementation can only allocate a small (O(1)/O(log n)) amount of memory independently - most of the queue's data must be inside the hash table.
EDIT: this data structure should support (Push,Pop,Top,Len) operations, but under the hood, instead of being a linked-list/array, it will use a hash-table. The majority O(n) memory needed will be contained in a hash-table.
Any list-like data structure can be represented by a hash table, where every element in the list is mapped to its position. So this list: [a, b, c, d] can be represented by a hash table like this:
0: a
1: b
2: c
3: d
A queue is a FIFO data structure: first in, first out. So elements are popped in the same order they were pushed. It can be modeled with an list-like data structure where we push new elements to the list by adding them to the tail and we pop elements by taking them from the head.
the implementation can only allocate a small (O(1)/O(log n)) amount of memory independently
The only necessary data to handle independently from the hash table itself are the head and tail indexes.
So, using the [a, b, c, d] example, our head points to index 0 (which corresponds to a) and our tail to index 3 (which corresponds to d).
To push a new element to the queue (e.g. e), we insert it into our hash table with key tail + 1, that is 4, and we increment our tail by 1.
To pop an element, we get the element at the head position, remove it from the hash table and increment head by 1.
After this, our hash table ends up like this:
1: b
2: c
3: d
4: e
With this implementation, top and len are trivial to implement.
This basic idea can be extended to handle more complex hash tables.