Methods for creating a queue class.
I know about the linked list approach, but was wondering why we don't just implement these using a dynamic array?
For example, let's say you have a queue of n items. Each element of the array would hold an item, so the array would be of size n, for now.
Then an item is removed. So a new array is made of size n-1, the old array is copied into this leaving out the first element. This is would be done through a for loop. The pointer's allocated memory is deleted (the old queue) and it is changed to point to the new array now.
It's been a while since I've done any C++ (was busy with schooling), so maybe I'm missing something. Is this avoided just because it is a clunky way of doing this with many places for errors and you have to allocate a whole new block of memory every time? Or is there another reason as well?
For example, let's say you have a queue of n items. Each element of the array would hold an item, so the array would be of size n, for now.
Then an item is removed. So a new array is made of size n-1, the old array is copied into this leaving out the first element. This is would be done through a for loop. The pointer's allocated memory is deleted (the old queue) and it is changed to point to the new array now.
It's been a while since I've done any C++ (was busy with schooling), so maybe I'm missing something. Is this avoided just because it is a clunky way of doing this with many places for errors and you have to allocate a whole new block of memory every time? Or is there another reason as well?
I think the main disadvantage with the way you describe is that it is slow.
std::queue uses std::deque as the underlying container by default. std::deque is good because it is fast to remove and add elements from both ends. That is true for linked lists too but the overhead of linked lists is often higher.
Another possible implementation is to use a circular buffer http://en.wikipedia.org/wiki/Circular_buffer
std::queue uses std::deque as the underlying container by default. std::deque is good because it is fast to remove and add elements from both ends. That is true for linked lists too but the overhead of linked lists is often higher.
Another possible implementation is to use a circular buffer http://en.wikipedia.org/wiki/Circular_buffer
Topic archived. No new replies allowed.