Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Like this article? We recommend
Data Structure Analysis
Elements are added to the queue at one end and removed from the other end. For adding an element to a queue that is not empty and contains more than one item, the following three steps are required:
- Check to see whether the queue is empty.
- Update the value of endOfQueue->nextQueueElement.
- Update the value of endOfQueue.
For removing an element, the following six steps are required:
- Check to see whether the queue is empty.
- Copy the item pointed to by startOfQueue.
- Copy the next item pointed to by startOfQueue.
- Point startOfQueue->nextQueueElement at the next item in the queue.
- Update startOfQueue.
- Return the item at the top of the queue.
Interestingly, removing items is more expensive than adding new ones. This is mainly because there is less bookkeeping attached to queue additions. Regarding performance, the add() and remove() methods just manipulate pointers. Because of this, the performance should be reasonable given that memory allocation and copying occurs prior to calling the add() and remove() methods.