Home Topic 5 Last Next


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

And note that the static implementations of push( ) and isEmpty( ) methods are taken to a much deeper level in the OOP Option Extension later on in D.4.9.


Arrays as Stacks

With arrays as stacks, you should use the "tail" (Whereas lists as stacks, use the "head")

So note here that it is much easier to work with the "tail" than the head, and doing so is not inefficient with arrays, since we can directly access elements of an array.

Compare this to how we most efficiently made stacks from lists; in that case, with access only to the head, we did not want to have to migrate all the way to the tail each time - both for push and pop. Rather, in the case of lists, it made sense to push and pop onto the head.

So don't confuse the most efficient ways to do each. But note that either way, both are working in a LIFO manner.






Arrays as Queues

In the case of arrays as queues, remember with queues that we have to work with opposite ends for enqueue and dequeue. So the ends that we will likely choose to work with, will be the same for both arrays as queues, and lists as queues. For enqueue we will usually use the tail, and for dequeue we will have to use the head.




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.




------------------------- NOT NECESSARY TO LOOK AT, BUT OFFERED AS AN ALTERNATIVE -------------------------


Alternative approach to Arrays as Queues vs. Diagrams above

(backup link to video)

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

And 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. The much more processing efficient way is to take the approach in the the diagrams above.