Remember, "the answer" is only half of it! Also, make sure everyone in your group can explain why.
We will use this Gradescope Online Assignment as our worksheet for in-class work. These problems are coded as being worth points for our simplicity, but will not impact your grade in the course.
It's easier to rule out the last option (E) since it is not a true statement. If the Stack were empty, top would be null. Since it being non-null is not always true, we know it's not an invariant.
The first four are a bit trickier. It turns out all of them are true statements, but not all of them would be considered an invariant. An invariant is something that is true about the state of a data structure that we rely on being true before each method is called, and make sure to preserve after each method is called. A and B describe two properties of our Stack that are true but are not statements about the state that we rely on. In some sense B is a side-effect of the fact that C is an invariant of our data structure!
Note this question is a bit of a "trick" and was meant more for discussion purposes. We don't have a pop-quiz of invariant or not, but wanted to get you in the mindset of thinking of invariants.
The state of the queue is defined by starting at front and going to back (potentially looping around to the beginning of the array). Since we specified both of these indices were inclusive, it should be front [16, 5, 7, 9, 15, 20] back.
Removing a value from the Queue removes it from the front. Our implementation of ArrayQueueV2 would increase the front each time remove is called.
front is currently at the number 16 at index 3.remove() would increase front by 1 and return the old front. So front would become 4 and return 16 since it was removed.remove() would increase front by 1 and return the old front. So front would become 5 and return 5 since it was removed.remove() would increase front by 1 and return the old front. So front would become 6, but this is out of bounds so we need to wrap front around to the beginning, so it is now 0. Return 7 since it was removed.remove() would increase front by 1 and return the old front. So front would become 1 and return 9 since it was removed.
Thinal state would have front as 1, back still being 2, and size would now be 2.Calling add when the array is full will cause a resize. We would make a new array of size 12 (it's common to double the size of the array) and copy the values over. Now that the new array is big enough, we would increase the back index for each addition adding the new number at the new back.
Since we are looking to model a system where we want to process something in the order they are received, this sounds like a line or a Queue. A Stack would not work well here since popping can only be down for the last item pushed, not the item that came first. A List could also work, but we would argue that it's better to use a more descriptive data type here rather than a broader one. Unless you had reason to believe you would need the behaviors that List provides that Queue does not, choosing the Queue as the ADT better describes what aspects of the problem any particular implementation needs to be good at.