Assume I have a deque somewhere in the heap. I push and pop from it a large number of times. Is the deque just going to shift across all of the heap? What happens if it goes beyond the heap?
Asked
Active
Viewed 35 times
1 Answers
0
It depends on the implementation in whatever language or library you are using. Generally, a robust implementation does not allow it grow arbitrarily in size and instead allocates/deallocates memory as needed.
The textbook implementation uses a circular array. As you push and pop items the head and tail pointers wrap around the array. If the array is full you either can't add more items or it might try to allocate a larger array and copy everything over.
A Python deque is a doubly-linked list. Each item is allocated separately so if you push and pop and an equal number of times you won't run out of memory.
How are deques in Python implemented, and when are they worse than lists?
A C++ stl deque is a vector of vectors. It allocates the deque memory in fixed sized chunks. When a chunk is no longer needed (all of the items have been removed) it can deallocate it.
Jeff
- 1,234
- 8
- 16