User Tools
queue_and_array
Differences
This shows you the differences between two versions of the page.
|
queue_and_array [2020/01/06 14:12] hutch |
queue_and_array [2022/02/28 13:55] (current) scott |
||
|---|---|---|---|
| Line 1: | Line 1: | ||
| ==== Using an Array to Implement a Circular Buffer ==== | ==== Using an Array to Implement a Circular Buffer ==== | ||
| - | Let's look at a a few simple examples of how an array can be used to implement a circular buffer, using the ''queue_t'' data structure that I provide below. First, to keep things simple, let's make our queue big enough to hold 3 elements (3 elements of type double, in our case). Using the code that I provided below, you would say the following: | + | Let's look at a a few simple examples of how an array can be used to implement a circular buffer using the ''queue_t'' data structure. First, to keep things simple, let's make our queue big enough to hold 4 elements. The following code initializes the queue: |
| <code C> | <code C> | ||
| #include "queue.h" | #include "queue.h" | ||
| Line 8: | Line 8: | ||
| </code> | </code> | ||
| - | One thing to note in the code above is that we pass the address of ''myQueue'' to ''queue_init''. We do this for the sake of efficiency in 'C', and this is because this is what the ''queue_init()'' code expects. Once we execute the code above, a pictorial view of ''myQueue'' would look something like right after ''queue_init()'' has been called) is shown below. Note that enough memory for 5 doubles has been allocated. But, as I said before, this queue can only hold 4 doubles. | + | One thing to note in the code above is that we pass the address of ''myQueue'' to ''queue_init()''. We do this for the sake of efficiency in 'C' and also because this is what ''queue_init()'' expects. The following figure shows what ''myQueue'' would look like right after a call to ''queue_init()''. Note that enough memory for 5 elements has been allocated. But, as I said before, this queue can only hold 4 elements. |
| {{ ::queueinit.jpg?300 |}} | {{ ::queueinit.jpg?300 |}} | ||
| Line 16: | Line 16: | ||
| {{ ::queuepushed4.jpg?300 |}} | {{ ::queuepushed4.jpg?300 |}} | ||
| - | Even though there appears to be one empty location in the queue (location 4), the queue is now considered to be full. Why is this so? Because ''indexIn'' always points to the empty location where the next "push" will store data. If we were to do another "push" when the queue is in its current state, ''indexIn'' would be wrapped around so that is back to 0, and because the queue is considered to be empty anytime ''indexIn'' and ''indexOut'' are the same value, the queue would become empty. Thus, whenever we "push" a new value onto the queue, the queue needs to do a simple test: if ''indexIn'' were incremented, would it be equal to ''indexOut''? If so, the queue is currently full and it is not possible to "push" another value onto the queue. | + | Even though there appears to be one empty location in the queue (location 4), the queue is now considered to be full. Why is this so? Because ''indexIn'' always points to the empty location where the next "push" will store data. If we were to do another "push" when the queue is in its current state, ''indexIn'' would be wrapped around so that it is back to 0, and because the queue is considered to be empty anytime ''indexIn'' and ''indexOut'' are the same value, the queue would become empty. Thus, whenever we "push" a new value onto the queue, the queue needs to do a simple test: if ''indexIn'' were incremented, would it be equal to ''indexOut''? If so, the queue is currently full and it is not possible to "push" another value onto the queue. |
| Now, let's perform two "pops" on our queue, removing two elements. After two "pops", our queue would be shown pictorially below: | Now, let's perform two "pops" on our queue, removing two elements. After two "pops", our queue would be shown pictorially below: | ||
| Line 22: | Line 22: | ||
| {{ ::queuetwopops.jpg?300 |}} | {{ ::queuetwopops.jpg?300 |}} | ||
| - | As shown, ''indexOut'' has moved up two locations. Now, let's say that we want to "push" two new values onto our queue. When "pushing" a new value, the queue would need to check if it is full. It is not because, if indexIn is incremented and wraps around to location 0, it will not be equal to ''indexOut'' because ''indexOut'' now has the value of 2. | + | As shown, ''indexOut'' has moved up two locations. Now, let's say that we want to "push" two new values onto our queue. When "pushing" a new value, the queue would need to check if it is full. If indexIn is incremented and wraps around to location 0, it will not be equal to ''indexOut'' because ''indexOut'' now has the value of 2. |
| Now, let's look at the queue after "pushing" two new values (51.5 and 49.2). | Now, let's look at the queue after "pushing" two new values (51.5 and 49.2). | ||
| Line 28: | Line 28: | ||
| {{ ::queuetwopushes.jpg?300 |}} | {{ ::queuetwopushes.jpg?300 |}} | ||
| - | ''indexIn'' now has the value of 1 and you can see that two values have been "pushed" onto the queue. Is our queue full? It must be, because the queue can only hold 4 elements. Our "empty" location is location 1 (currently showing 3.14 but remember that value was previously "popped" off). Let's try the "full test". If we were to increment ''indexIn'' it would have the same value as ''indexOut'', so the queue is currently full. | + | ''indexIn'' now has the value of 1 and you can see that two values have been "pushed" onto the queue. Is our queue full? It must be, because the queue can only hold 4 elements. Our "empty" location is location 1 (currently showing 3.14, but remember that value was previously "popped" off). Let's try the "full test". If we were to increment ''indexIn'' it would have the same value as ''indexOut'', so the queue is currently full. |
| Carefully study the example above so you can see how the circular buffer works with an array, and also so you can see why there is always an empty location in the queue when implemented this way. | Carefully study the example above so you can see how the circular buffer works with an array, and also so you can see why there is always an empty location in the queue when implemented this way. | ||
| Line 35: | Line 35: | ||
| ==== Why the Extra Location? ==== | ==== Why the Extra Location? ==== | ||
| - | Why the extra location? In the queue.c code that I provided you will note that I allocate one additional memory location. My presumption is that you will implement the queue as a circular buffer that uses an empty location to deal with the empty/full problem. Please see this web page on [[http://en.wikipedia.org/wiki/Circular_buffer|circular buffers]] as it explains this issue. You are not required to implement the queue using a circular buffer. However, it is usually about the easiest thing to debug and get running. | + | Why the extra location? In the queue.c code that I provided, you will note that I allocate one additional memory location. My presumption is that you will implement the queue as a circular buffer that uses an empty location to deal with the empty/full problem. Please see this web page on [[http://en.wikipedia.org/wiki/Circular_buffer|circular buffers]] as it explains this issue. You are not required to implement the queue using a circular buffer. However, it is usually about the easiest thing to debug and get running. |
| ---- | ---- | ||
queue_and_array.1578345161.txt.gz ยท Last modified: 2020/01/06 14:12 by hutch
Page Tools
Except where otherwise noted, content on this wiki is licensed under the following license: CC Attribution-Share Alike 3.0 Unported
