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:


JSR Notes:

Video notes of arrays as stacks and queues.

*** Note *** The one thing I forgot with the video is to test empty/full stack/queue.

So, when adding to either an array being treated as a stack or queue, we first have to check to see if it's full. We will know if it's full if the array.length-1 element is not null/nothing. If the array.length-1 element is null/nothing, then that means the queue/stack must not be full yet, so we can go ahead and add to it.

When dequeuing from a queue, or poping from a stack, we have to first check to see that it's not empty. That's really easy, because we just have to check to see what's in element number [0]. If null/nothing is there, the queue/stack is empty, and so we should not try to dequeue/pop, or we will get some sort of error, such as a null pointer exception.

Loading the player...

Either another video or diagram or code/pseudocode could be added here as well, as long as not too detailed/in-depth.

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.

The code for this gets a little more involved than is likely needed for the general idea of an array as a stack and queue.