Reading material

If you use the first edition of the textbook, follow the reading material in orange. If you use the second edition, follow the reading material in brown.

(1st) pages 69-73 (Section 3.1.2), pages 80-83 (Section 3.2.2), pages 117-118 (Section 4.1.2)

(2nd) pages 140-145 (Section 4.1.2), pages 152-155 (Section 4.2.2), pages 187-188 (Section 5.1.2)

Additional material

Implementation of a stack, queue and ranked sequence with an array in pseudocode: PostScript and PDF

How the variables represent the data structure is captured by the (class) invariant. It is an assertion which should hold after initialization and which should be preserved by the operations on the data structure.

Question

In the implementation of a queue with an array, we add a boolean variable isEmpty. Does this allow us to store an element in each cell of the array? If your answer is yes, adapt the algorithms. If your answer is no, explain why it is not possible.