![]() Take particular care to note the pointers.ĭata is specified as being between the StartPtr and the EndPtrĪdding another element to the queue moves the EndPtr up oneĭeleting an element from the front of the queue is achieved by increasing the StartPtr by oneĪdding another element to the queue moves the EndPtr up one, it is now at the end of the bufferĪdding another element to the queue makes the EndPtr loop around to the free space at the beginning of the bufferĪdding another element to the queue moves the EndPtr up one, it is now closing in the on the StartPtrĪdding another element to the queue moves the EndPtr up one, it is now closing in the on the StartPtr. The following example shows a partially-full fixed length buffer and how it handles additions and deletions from a queue. ![]() one to point to the start of valid data.Generally, a circular buffer requires three pointers: Unlike linear queues Circular queues allow for memory to be re-used: Removing items from the front of the queue can be slow See below (note that we no longer need a front pointer as item 1 is always the front): ![]() However, if there are many items in the queue this could become very slow. Take a look at this example and the values of the two pointers storing the front of the queue (FrontPtr) and the next free memory location (NextFree).Ī better implementation would reuse memory by shifting each item one to the left, each time an item is removed from the front. The front and end pointers can only move forwards and sooner or later would reach the end of the allotted memory - at this point, no more items could be added to the queue. The most basic implementation of a linear queue would work its way through its allotted memory, without reusing memory. The linear queue you are about to see 'crawls' through memory, devouring everything it comes across. However, there is one difference, in a supermarket queue once the first person has been served the rest of the queue shuffles forward, making the previously second person now first, this is possible in a computer but very costly in terms of processing. And if you join the queue last you are going to be served last (no pushing!). The first person into the queue is the first person to be served. First In First Out (FIFO).Ī real life example of this would be queuing to pay at the supermarket. In this queue form, elements are able to join the queue at one end and can exit from the queue at the other end. There are several different types of queues such as the ones described below: When you are sharing a printer several people may send a print job to the printer and the printer can't print things instantly, so you have to wait a little while, but the items output will be in the order you sent them.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |