Reading material

Pages 140-145 (Section 4.1.2), pages 152-155 (Section 4.2.2) pages 187-188 (Section 5.1.2), pages 209-210 (Section 5.3.3), pages 159-165 (Section 4.3), pages 167-171 (Section 4.4.2)

Additional material

Implementing data structures

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

Implementation of a vector and list with an array in pseudocode: PostScript and PDF

Implementation of a stack, queue and deque with linked lists 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.

ArrayStack
StackFullException
ArrayQueue
QueueFullException
ArrayVector
VectorFullException
VectorVector
ArrayPosition
Node
LinkedStack
LinkedQueue

To visualize how Java objects are used to implement data structures like stacks and queues you may want to use the Java package explicar.

Question

Give the constructor and the methods enqueue and dequeue of the Java implementation of a queue with a singly linked list with dummy nodes.