User Tools
queues
Differences
This shows you the differences between two versions of the page.
|
queues [2015/12/23 17:19] hutch |
queues [2015/12/23 17:34] (current) hutch |
||
|---|---|---|---|
| Line 6: | Line 6: | ||
| - Your queue must allow you to keep adding (pushing) new elements even after it is full. If the queue is full when you add an additional element, it must remove the oldest element and add the new one, making sure to keep the correct order of things in the queue. For example, let's say that your queue can contain 200 elements. If you add 400 elements to the queue, the queue should contain the last 200 elements that were added, in the same order that they were added. In other words, the queue will contain elements 201 through 400. When you remove an element from the queue, the elements should be removed in order, e.g., element 201, followed by element 202, etc. | - Your queue must allow you to keep adding (pushing) new elements even after it is full. If the queue is full when you add an additional element, it must remove the oldest element and add the new one, making sure to keep the correct order of things in the queue. For example, let's say that your queue can contain 200 elements. If you add 400 elements to the queue, the queue should contain the last 200 elements that were added, in the same order that they were added. In other words, the queue will contain elements 201 through 400. When you remove an element from the queue, the elements should be removed in order, e.g., element 201, followed by element 202, etc. | ||
| - You must be able to read the contents in the queue without removing them or disturbing them. In other words, your queue must provide a function that can read elements in the queue by index. For example, let's assume that the name of the function is queue_readElementAt(&q, index) and that it takes two arguments (the address of the queue, and the index of the element to read). If index = 0, this will read the oldest element in the queue. Larger values of index will successively read data that arrived later. You must print out an error message if the index-value would access elements beyond what is currently stored in the queue. | - You must be able to read the contents in the queue without removing them or disturbing them. In other words, your queue must provide a function that can read elements in the queue by index. For example, let's assume that the name of the function is queue_readElementAt(&q, index) and that it takes two arguments (the address of the queue, and the index of the element to read). If index = 0, this will read the oldest element in the queue. Larger values of index will successively read data that arrived later. You must print out an error message if the index-value would access elements beyond what is currently stored in the queue. | ||
| + | |||
| + | ---- | ||
| ===== Requirements ===== | ===== Requirements ===== | ||
| Line 12: | Line 14: | ||
| - Your queue_runTest() must do at least the following: | - Your queue_runTest() must do at least the following: | ||
| - test all of the functions listed in queue.h. | - test all of the functions listed in queue.h. | ||
| - | - perform 5 overwritePush(), followed by 3 pop(), followed by 5 overwritePush(), followed by queue_print(). Then, perform readElementAt() for each value remaining in the queue to verify that the contents are correct. Was will verify that your test code performs at least these functions. | + | - perform 5 overwritePush(), followed by 3 pop(), followed by 5 overwritePush(), followed by queue_print(). Then, perform readElementAt() for each value remaining in the queue to verify that the contents are correct. TAs will verify that your test code performs at least these functions. |
| - You must follow the same [[http://ecen330wiki.groups.et.byu.net/wiki/doku.php?id=coding_standards|coding standards]] as was done for ECEN 330. | - You must follow the same [[http://ecen330wiki.groups.et.byu.net/wiki/doku.php?id=coding_standards|coding standards]] as was done for ECEN 330. | ||
| - You are not allowed to pass off your code if it has more than 5 coding-standard infractions. | - You are not allowed to pass off your code if it has more than 5 coding-standard infractions. | ||
| - | ===== TA Passoff Notes ===== | + | ---- |
| + | |||
| + | ===== Pass-Off Requirements ===== | ||
| + | - Your code must follow the coding standard. The TAs will review your source code and not allow you to pass off if you have more than 5 infractions of the source-code standard. | ||
| + | - Staple the {{::codingstandardchecklist.pdf|source-code pass-off sheet}} to the front of your source code. Make sure to fill in the name, lab-number, and submission date. | ||
| + | - Ensure that the queue_print() function prints out the contents of the queue in order, from oldest value to newest value. | ||
| + | - Ensure that the queue_runTest() function performs the operations listed in the requirements section above. | ||
| + | |||
| + | ---- | ||
| + | |||
| + | ===== TA Pass-Off Notes ===== | ||
| - Quickly review the source code before passing off. Do not pass off if the code has more than 5 coding-standard infractions. Students whose code has many coding-standard infractions must correct their code before passing off the milestone. | - Quickly review the source code before passing off. Do not pass off if the code has more than 5 coding-standard infractions. Students whose code has many coding-standard infractions must correct their code before passing off the milestone. | ||
| - Ensure that the queue_print() function prints out the contents of the queue in order, from oldest value to newest value. | - Ensure that the queue_print() function prints out the contents of the queue in order, from oldest value to newest value. | ||
| - Ensure that the queue_runTest() function performs the operations listed in the requirements section above. | - Ensure that the queue_runTest() function performs the operations listed in the requirements section above. | ||
| + | |||
| + | ---- | ||
| ===== Notes ===== | ===== Notes ===== | ||
| Line 26: | Line 40: | ||
| 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. | ||
| + | |||
| + | ---- | ||
| ==== Malloc, Pointers and Arrays in 'C' ==== | ==== Malloc, Pointers and Arrays in 'C' ==== | ||
| Line 68: | Line 84: | ||
| } | } | ||
| </code> | </code> | ||
| + | |||
| + | ---- | ||
| ==== Using an Array to Implement a Circular Buffer ==== | ==== Using an Array to Implement a Circular Buffer ==== | ||
| Line 102: | Line 120: | ||
| 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. | ||
| - | ==== Bugs, bugs, bugs: what to do when your queue code doesn't pass the tests? ==== | + | ---- |
| + | |||
| + | ===== Bugs, bugs, bugs: what to do when your queue code doesn't pass the tests? ===== | ||
| - Make sure you implement ''queue_overwritePush()'' correctly. If the queue is full, remove an element and push the new element on the queue. If it is not full, just push the new value. | - Make sure you implement ''queue_overwritePush()'' correctly. If the queue is full, remove an element and push the new element on the queue. If it is not full, just push the new value. | ||
| - For those of you using the extra "empty space" in the queue to determine full/empty, make sure that you allocate one additional location of memory in ''queue_init()'', e.g., a queue of size 4 must be allocated with 5 locations. This does not apply to students who are using elementCount to determine full/empty. | - For those of you using the extra "empty space" in the queue to determine full/empty, make sure that you allocate one additional location of memory in ''queue_init()'', e.g., a queue of size 4 must be allocated with 5 locations. This does not apply to students who are using elementCount to determine full/empty. | ||
| - Make sure that your pointers are initialized so that the point at memory provided by malloc(). | - Make sure that your pointers are initialized so that the point at memory provided by malloc(). | ||
| - | ==== Source Code ==== | + | |
| + | ---- | ||
| + | |||
| + | ===== Source Code ===== | ||
| I have provided the source code for your ".h" file and part of the code for your ".c" file. As I said before, you are not required to implement the queue as I have shown here. However, you must implement all of the functions that are contained in the ".h" file. | I have provided the source code for your ".h" file and part of the code for your ".c" file. As I said before, you are not required to implement the queue as I have shown here. However, you must implement all of the functions that are contained in the ".h" file. | ||
| - | <code> | + | <file c queue.h> |
| /* | /* | ||
| Line 177: | Line 200: | ||
| #endif /* QUEUE_H_ */ | #endif /* QUEUE_H_ */ | ||
| - | </code> | + | </file> |
| ------------- | ------------- | ||
| - | <code C> | + | <file C queue.c> |
| /* | /* | ||
| Line 206: | Line 229: | ||
| } | } | ||
| - | </code> | + | </file> |
| ---- | ---- | ||
| Line 216: | Line 239: | ||
| - If your queue fails this test, it means that your queue_runTest() code is not very thorough. As you fix your queue code, update your queue_runTest() function so that it more fully tests your queue. | - If your queue fails this test, it means that your queue_runTest() code is not very thorough. As you fix your queue code, update your queue_runTest() function so that it more fully tests your queue. | ||
| - If your queue fails the more thorough test code that I provide, it is your responsibility to add code to your queue_runTest() code until it detects the bug. | - If your queue fails the more thorough test code that I provide, it is your responsibility to add code to your queue_runTest() code until it detects the bug. | ||
| - | |||
| - | Common Bugs: | ||
| - | |||
| <code C> | <code C> | ||
| Line 326: | Line 346: | ||
| </code> | </code> | ||
| - | |||
queues.1450916371.txt.gz · Last modified: 2015/12/23 17:19 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
