Logout

5.1.10

Explain the use of arrays as static stacks and queues.

 

Teaching Note:

Students should be able to explain push and pop operations, and test on empty/full stack.

Students should be able to explain enqueue and dequeue operations, and test on empty/full queue.


 

Sample Question:

sdfsdfsf

JSR Notes:


(backup link to video)

Note that the one thing I forgot in the video is to test empty/full stack/queue.

Video approach to Arrays as Queues vs. Diagrams below

Do note that array-as-queue dequeue algorithm seen in the video would not be very efficient for large arrays, since every time an item is dequeued, all other items need to be shifted down. A much more processing efficient way would be to simply keep track of what the head is, and it would shift to the right each time a dequeue took place. Since that would move the head increasingly to the end of the array (leaving less and less spots available for new items) you would want the "list" to continue around to the beginning of the array when the end is reached. Thus, the tail could actually be to the left of the head. This is the approach taken in the diagram below.

 

Arrays as Stacks

 

 

 

 

 

Arrays as Queues

 

 

 

Important Usage of isEmpty( ) and isFull( )

Something that is easy to forget, but which is bound to cause an error sooner or later is making sure to properly employ isEmpty( ) and isFull( ).

When adding to an array being treated as either a stack or queue, we first have to check to see if it's full, or there will be an error. See the details above for how to do this for the stack, and for the queue.

And when dequeuing from a queue, or popping from a stack, we have to first check to see that it's not empty. For an array treated as a stack, that's easy, because we just have to check to see if the default value is in element number [0]. And it's also easy for an array treated as a queue because the head will be the default value.