Linked Lists, Resizing Arrays and Stack Clients

A Node holds an item and a reference next to the next node; the last node's next is null. Build the list to be or, then insert a node at the beginning, remove the first node, or walk through the list. Every Step runs one line. Book pp. 571-574.

push() inserts a node at the beginning of the list, pop() removes the first node: the top of the stack is always first. There is no capacity: every push creates a node. A popped node has no reference to it any more (an orphan, dashed), and Java's garbage collector reclaims its memory. Change the words to try your own. Program 4.3.2, trace p. 576.

The array starts with length 1. push() doubles the length when the array is full, pop() halves it when the stack is down to one-quarter of the length. Each resize copies all n items into a new array, so one push can be expensive - but on average every operation costs a constant number of copies. Switch to halving at one-half and push and pop at the boundary to see why the book waits for one-quarter. Program 4.3.3, trace p. 580.

Dijkstra's two-stack algorithm (book) reads a fully parenthesized expression: it ignores (, pushes operators on one stack and numbers on the other, and at every ) pops an operator and its operands and pushes the result. Postfix (reverse Polish notation, from the CS.12 lecture) needs no parentheses and only one stack: a number is pushed, an operator pops its operands and pushes the result. Separate the tokens with spaces. Program 4.3.5, trace p. 589.

The queue keeps two references: first (the oldest item, where dequeue() removes) and last (the newest, where enqueue() links a new node). dequeue() works like the stack's pop(); enqueue() inserts at the end. Watch the two special cases: an enqueue into an empty queue sets first too, and the dequeue of the last item sets last to null. Step runs one line, Next operation a whole enqueue or dequeue. Program 4.3.6, pp. 592-595.